CF734F Anton and School (构造)

$ solution $ :

这道题做法很巧妙，需要对位运算有足够了解：

1. $ ( a $ & $ b ) $ $ + $ $ ( a $ | $ b ) $ $ = $ $ a+b $ ，所以有 $ Σb+Σc=2nΣa $

2. 看下面代码里的数位优化，可以将复杂度由 $ O(n^2) $ 降为 $ O(n) $

知道了这两点就可以开始构造了！

首先我们根据性质1,求出每个 $ a_i $ 的值，然后检验此时的a数组是否满足题目所给的等式（要用性质2降复杂度），然后输出即可！

$ code: $

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
#define end {puts("-1");exit(0);}//这个要看一眼

using namespace std;

ll tot;
int n,s[33];
int a[200001];
int b[200001];
int c[200001];//如题

inline int qr(){ char ch; //（加速）
	while((ch=getchar())<'0'||ch>'9');
	int res=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
		res=res*10+(ch^48);
	return res;
}

int main(){ n=qr();
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	for(rg i=1;i<=n;++i)
		tot+=(b[i]=qr());
	for(rg i=1;i<=n;++i){
		tot+=(c[i]=qr());
		if(c[i]<b[i])end //剪枝（加速）
	}
	if(tot%(n<<1))end //剪枝（必须有！）
	else tot/=n<<1;
	for(rg i=1;i<=n;++i){
		a[i]=b[i]+c[i]-tot;
		if(a[i]%n)end //剪枝（必须有！）
		else a[i]/=n;
	} rg m,j,x,y;  //至少洛谷数据不会爆 long long
	for(rg i=1;i<=n;++i)
		for(m=a[i],j=1;m;m>>=1,++j)
		    if(m&1)++s[j]; //数位优化
	for(rg i=1;i<=n;++i){ x=y=0;
	    for(m=a[i],j=1;j<=30;m>>=1,++j)
			if(m&1)x+=s[j]<<j-1,y+=n<<j-1;//这个if看仔细了
			else y+=s[j]<<j-1;  
		if(x!=b[i]||y!=c[i])end //最有效的剪枝！（不得不有！）
	}
	for(rg i=1;i<=n;++i)
		printf("%d ",a[i]);
	return 0;
}