AtCoder abc164_f - I hate Matrix Construction

洛谷题目页面传送门 & AtCoder题目页面传送门

给定整数\(n\)和\(4\)个长度为\(n\)的序列\(a,b,c,d\)，其中\(a_i,b_i\in\{0,1\}\)。要求构造一个\(n\times n\)的矩阵，满足以下条件：

• \(\forall i\in[1,n]\)，如果\(a_i=0\)，则第\(i\)行的与和为\(c_i\)；否则或和为\(c_i\)；
• \(\forall i\in[1,n]\)，如果\(b_i=0\)，则第\(i\)列的与和为\(d_i\)；否则或和为\(d_i\)。

或报告无解。

\(n\in[1,500],c_i,d_i\in\left[0,2^{64}\right)\)。

这是一个炒鸡毒瘤的分类讨论大题……

首先不难想到的是，各二进制位之间是独立的，不妨拆成\(64\)位，每位分别处理，最终合并答案。若有任意一位无解，那么最终无解。于是拆成的每个问题中的与和、或和限制都\(\in\{0,1\}\)了。我们继续沿用字母\(a,b,c,d\)表示，此时\(c_i,d_i\in\{0,1\}\)。

接下来考虑怎么处理每个拆成的问题。

显然，每行、每列分别有且仅有一个限制，而且都可以转化为更能直观理解的形式们之一：

1. \(a_i/b_i=0,c_i/d_i=1\)：第\(i\)行/列全是\(1\)；
2. \(a_i/b_i=0,c_i/d_i=0\)：第\(i\)行/列至少有一个\(0\)；
3. \(a_i/b_i=1,c_i/d_i=1\)：第\(i\)行/列至少有一个\(1\)；
4. \(a_i/b_i=1,c_i/d_i=0\)：第\(i\)行/列全是\(0\)。

其中限制\(1,4\)是“\(\forall\)限制”，限制\(2,3\)是“\(\exists\)限制”。

直接暴力分类讨论。

1. 行、列都存在\(\forall\)限制：此时显然只能有一种\(\forall\)限制，否则一定会发生冲突，无解。现在假设只有一种\(\forall\)限制，那么很容易想到的方案是将所有\(\forall\)限制填上之后，剩下的格子都填相反的数，这样每行/列要么是\(\forall\)限制，已满足；要么是\(\exists\)限制，按照填法此行/列显然一定\(0,1\)都有，一定满足；
2. 只有行存在\(\forall\)限制：
   1. 限制\(1,4\)都存在：容易想到，将所有\(\forall\)限制都填满，将所有行的\(\exists\)限制都随便填使得满足，完全没必要在意列的限制，因为这样显然每列一定\(0,1\)都有，能够满足所有列的\(\exists\)限制；
   2. \(\forall\)限制只存在限制\(1\)：先把所有限制\(1\)填满再说。现在我们要满足的就是行、列限制\(2,3\)。其中列限制\(3\)显然已经全部满足，难点在于列限制\(2\)。有以下几种情况：
      1. 没有列限制\(2\)：那么直接把行限制们随便满足一下即可；
      2. 存在行限制\(2\)：把任一一个行限制\(2\)填满\(0\)，此时显然所有列都有\(0\)了，所以所有列限制\(2\)都满足了，于是把其他行限制们随便满足一下即可；
      3. 至少存在\(2\)个行限制\(3\)：把其中任意\(2\)个行限制\(3\)都\(1\)格填\(1\)、其他格填\(0\)，使得填\(1\)的位置错开，这样也能实现每列都有\(0\)，剩下的跟情况\(2.2.2\)类似；
      4. 存在行限制\(3\)且至多有\(n-1\)个列限制\(2\)：将任意一个行限制\(3\) \(1\)格填\(1\)、其他格填\(0\)，使得填\(1\)的位置所在列没有列限制\(2\)，这样也能满足所有列限制\(2\)，于是再次地把其他行限制们随便满足一下即可；
      5. 情况\(2.2.1\sim2.2.4\)都不满足：无能为力，无解；
   3. \(\forall\)限制只存在限制\(4\)：与情况\(2.2\)类似；
3. 只有列存在\(\forall\)限制：与情况\(2\)类似；
4. 不存在\(\forall\)限制：
   1. \(n=1\)：有可能无解，乱搞即可；
   2. \(n>1\)：一定有解，一种可行的方案是：为每行/列挑选一个代表来满足此行/列的限制，第\(i\)行的代表是\(\begin{cases}(i,2)&i=1\\(i,1)&i>1\end{cases}\)，第\(i\)列的代表是\(\begin{cases}(1,i)&i=1\\(2,i)&i>1\end{cases}\)，这样可以保证代表们两两不重合。

时间复杂度\(\mathrm O\!\left(n^2\right)\)，乘上常数\(64\)。

The end.

下面是代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef unsigned long long ull;
const int N=500;
int n;
bool a[N+1],b[N+1];
ull c[N+1],d[N+1];
ull ans[N+1][N+1];
void sol(int x){
//	cout<<x<<"\n";
	vector<int> r0,ro0,r1,ro1,c0,co0,c1,co1;//行限制4,2,1,3、列限制4,2,1,3 
	for(int i=1;i<=n;i++){//预处理8个vector 
		if(!a[i]&&!(c[i]&1ull<<x))ro0.pb(i);
		else if(!a[i]&&c[i]&1ull<<x)r1.pb(i);
		else if(a[i]&&!(c[i]&1ull<<x))r0.pb(i);
		else ro1.pb(i);
		if(!b[i]&&!(d[i]&1ull<<x))co0.pb(i); 
		else if(!b[i]&&d[i]&1ull<<x)c1.pb(i);
		else if(b[i]&&!(d[i]&1ull<<x))c0.pb(i);
		else co1.pb(i);
	}
	if((r0.size()||r1.size())&&(c0.size()||c1.size()))//1 
		if(r0.size()&&!r1.size()&&c0.size()&&!c1.size()){
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]|=1ull<<x;
			for(int i=0;i<r0.size();i++)for(int j=1;j<=n;j++)(ans[r0[i]][j]|=1ull<<x)^=1ull<<x;
			for(int j=0;j<c0.size();j++)for(int i=1;i<=n;i++)(ans[i][c0[j]]|=1ull<<x)^=1ull<<x;
		}
		else if(!r0.size()&&r1.size()&&!c0.size()&&c1.size()){
			for(int i=0;i<r1.size();i++)for(int j=1;j<=n;j++)ans[r1[i]][j]|=1ull<<x;
			for(int j=0;j<c1.size();j++)for(int i=1;i<=n;i++)ans[i][c1[j]]|=1ull<<x;
		}
		else puts("-1"),exit(0);
	else if(r0.size()||r1.size())//2
		if(r0.size()&&r1.size()){//2.1
			for(int i=0;i<r1.size();i++)for(int j=1;j<=n;j++)ans[r1[i]][j]|=1ull<<x;
			for(int i=0;i<ro1.size();i++)ans[ro1[i]][1]|=1ull<<x;
		}
		else if(r0.size())//2.2
			if(!co1.size()||ro1.size())//2.2.1&2.2.2
				for(int i=0;i<ro1.size();i++)for(int j=1;j<=n;j++)ans[ro1[i]][j]|=1ull<<x;
			else if(ro0.size()>=2){//2.2.3
				for(int j=2;j<=n;j++)ans[ro0[0]][j]|=1ull<<x;
				for(int j=1;j<n;j++)ans[ro0[1]][j]|=1ull<<x;
			}
			else if(co1.size()<n&&ro0.size()==1){//2.2.4
				int notin=1,now=0;
				while(now<co1.size()&&co1[now]==notin)notin++,now++;
				for(int j=1;j<=n;j++)if(j!=notin)ans[ro0[0]][j]|=1ull<<x;
			}
			else puts("-1"),exit(0);//2.2.5
		else{//2.3
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]|=1ull<<x;
			if(!co0.size()||ro0.size())
				for(int i=0;i<ro0.size();i++)for(int j=1;j<=n;j++)ans[ro0[i]][j]^=1ull<<x;
			else if(ro1.size()>=2){
				for(int j=2;j<=n;j++)ans[ro1[0]][j]^=1ull<<x;
				for(int j=1;j<n;j++)ans[ro1[1]][j]^=1ull<<x;
			}
			else if(co0.size()<n&&ro1.size()==1){
				int notin=1,now=0;
				while(now<co0.size()&&co0[now]==notin)notin++,now++;
				for(int j=1;j<=n;j++)if(j!=notin)ans[ro1[0]][j]^=1ull<<x;
			}
			else puts("-1"),exit(0);
		}
	else if(c0.size()||c1.size())//3
		if(c0.size()&&c1.size()){
			for(int j=0;j<c1.size();j++)for(int i=1;i<=n;i++)ans[i][c1[j]]|=1ull<<x;
			for(int j=0;j<co1.size();j++)ans[1][co1[j]]|=1ull<<x;
		}
		else if(c0.size())
			if(!ro1.size()||co1.size())
				for(int j=0;j<co1.size();j++)for(int i=1;i<=n;i++)ans[i][co1[j]]|=1ull<<x;
			else if(co0.size()>=2){
				for(int i=2;i<=n;i++)ans[i][co0[0]]|=1ull<<x;
				for(int i=1;i<n;i++)ans[i][co0[1]]|=1ull<<x;
			}
			else if(ro1.size()<n&&co0.size()==1){
				int notin=1,now=0;
				while(now<ro1.size()&&ro1[now]==notin)notin++,now++;
				for(int i=1;i<=n;i++)if(i!=notin)ans[i][co0[0]]|=1ull<<x;
			}
			else puts("-1"),exit(0);
		else{
			for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]|=1ull<<x;
			if(!ro0.size()||co0.size())
				for(int j=0;j<co0.size();j++)for(int i=1;i<=n;i++)ans[i][co0[j]]^=1ull<<x;
			else if(co1.size()>=2){
				for(int i=2;i<=n;i++)ans[i][co1[0]]^=1ull<<x;
				for(int i=1;i<n;i++)ans[i][co1[1]]^=1ull<<x;
			}
			else if(ro0.size()<n&&co1.size()==1){
				int notin=1,now=0;
				while(now<ro0.size()&&ro0[now]==notin)notin++,now++;
				for(int i=1;i<=n;i++)if(i!=notin)ans[i][co1[0]]^=1ull<<x;
			}
			else puts("-1"),exit(0);
		}
	else//4
		if(n==1)//4.1
			if(ro0.size()&&co0.size());
			else if(ro1.size()&&co1.size())ans[1][1]|=1ull<<x;
			else puts("-1"),exit(0);
		else{//4.2
			for(int i=0;i<ro1.size();i++)ans[ro1[i]][ro1[i]==1?2:1]|=1ull<<x;
			for(int j=0;j<co1.size();j++)ans[co1[j]==1?1:2][co1[j]]|=1ull<<x;
		}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=0;i<64;i++)sol(i);//拆位分别处理 
	for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<ans[i][j]<<" ";puts("");}
	return 0;
}

AtCoder abc164_f - I hate Matrix Construction

原文：https://www.cnblogs.com/ycx-akioi/p/AtCoder-abc164-f.html