Codeforces Round #379 (Div. 2) 734 F(二进制)

题目大意

F. Anton and School 给你两个数组 b,c ,让你找出一个数组 a 满足

bi=∑nj=1ai and aj ci=∑nj=1ai or aj

首先我们发现 ai and aj+ai|aj=ai+aj ,（未证明） 那就不难发现关于 ai 的公式 所以，如果有解，那么解一定是唯一的，剩下的就是判断这个解是否满足等式

bi=∑nj=1ai and aj ci=∑nj=1ai or aj

显然不能暴力的去直接计算出 ∑nj=1ai and aj 因为我们有

ai & aj=∑(ai,k & aj,k)∗2k , ai,k 表示 ai 的第 k 的bit ∑nj=1ai and aj=∑maxbitk=0(∑nj=0(ai,k& aj,k))∗2k

bi,j 表示 b 的第j位，则

bi,j=0,if ai,j=0,else bi,j=kj, kj 表示数组a中第j位为1的个数

类似的不难推出 ci 的表达式，这样就可以预处理出k数组 O(lg(max{ai})∗n) ,这样计算出全部的 bi 只需要 O(lg(max{ai}))

代码

#include <cstdio> #include <cstring> #include <queue> #include<algorithm> #include<iostream> #include<cmath> #include<vector> #define INF 0x3f3f3f3f #define maxn 200009 #define fi first #define se second using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int,int> PI; LL a[maxn],b[maxn],c[maxn],k[64]; const LL one = 1; int main() { //freopen("H:\\c++\\file\\stdin.txt","r",stdin); int n; cin>>n; LL sum = 0; for(int i=0 ; i<n ; ++i) { cin>>b[i]; sum+=b[i]; } for(int i=0 ; i<n ; ++i) { cin>>c[i]; sum+=c[i]; } int ans = 0; if(sum %(2*n)!=0)ans = -1; else sum/=(2*n); for(int i=0 ; i<n ; ++i) { if(ans == -1||b[i]+c[i]<sum || (b[i]+c[i]-sum)%n !=0){ans = -1;break;} a[i] = (b[i]+c[i]-sum)/n; } //check memset(k,0,sizeof(k)); for(int j=0 ; j<32 ; ++j) { for(int i=0 ; i<n ; ++i) { k[j]+= ((a[i]>>j)&one); } } for(int i=0 ; i<n ; ++i) { LL bi =0;LL ci = 0; for(int j=0 ; j<32 ; ++j) { if((a[i]>>j)&one){bi+=k[j]*(one<<j);ci+=n*(one<<j);} else{ci+=k[j]*(1<<j);} } if(b[i]!=bi || c[i]!=ci){ans = -1;break;} } if(ans == -1)cout<<"-1"<<endl; else{ for(int i=0 ; i<n ; ++i)cout<<a[i]<<" "; } cout<<endl; return 0; }