[Codeforces #379 F. Anton and School]位运算技巧

1. 题目链接

[Codeforces #379 F. Anton and School]

2. 题意描述

给定 n ，以及两个长度为n的数组 b[] , 和数组 c[] ,找出一个数组 a[] 满足：

⎧⎩⎨bi=∑j=nj=1(ai  &  aj)ci=∑j=nj=1(ai   |   aj) 如果不存在，输出”-1”;存在就输出数组 a[] 。 (1≤n≤200000,0≤bi,ci≤109)

3. 解题思路

这道题目技巧性很强。 假设结果存在。 首先，需要利用这个公式(非常重要)：

(x&y)+(x|y)=x+y 所以：

∴bi+ci=∑j=1n(ai+aj)=n∗ai+∑j=1naj∴令SUM=∑i=1i=n(ai+bi)=2n∗∑j=1naj∴对于∀i,(1≤i≤n),可求得:ai=bi+ci−∑nj=1ajn=bi+ci−SUM2∗nn 所以，可以在 O(N) 的复杂度下求出数组 a[] ， 并且 a[] 是唯一的。 接下来，就是判断 a[] 是否合法。即通过数组 a[] ,来生成数组 b′[],c′[] 【技巧】, 然后判断 b 与b′[]、 c 与c′[]是否相等。 数组 a[] 中每一项 ai 的第 k 位，记做Ai,k。 求出数组 a1,a2,…,an ，在第 k 位1的个数，记做 cntk 。即 cntk=∑ni=1Ai,k 。 令: {Bi,k=∑nj=1(Ai,k  &  Aj,k)Ci,k=∑nj=1(Ai,k   |   Aj,k) 那么， Bi,k={0,cntk,Ai,k=0Ai,k=1Ci,k={cntk,0,Ai,k=0Ai,k=1 那么， b′i=∑k=0bits(Bi,k∗2k)c′i=∑k=0bits(Ci,k∗2k) . 这个技巧就在于将一个数字拆成多个二进制位进行考虑。 最后的复杂度为 O(N∗bits) 。

4. 实现代码

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MX = 200000 + 5; const int BITS = 32; int n; vector<LL> a, b, c; bool check() { vector<int> cnt(BITS); for(int k = 0; k < BITS; k++) { cnt[k] = 0; for(int i = 0; i < n; i++) { cnt[k] += (a[i] >> k) & 1; } } vector<vector<int> > B(n), C(n); for(int i = 0; i < n; i++) { B[i].resize(BITS); C[i].resize(BITS); for(int k = 0; k < BITS; k++) { if((a[i] >> k) & 1) { B[i][k] = cnt[k]; C[i][k] = n; } else { B[i][k] = 0; C[i][k] = cnt[k]; } } } for(int i = 0; i < n; i++) { int bi = 0, ci = 0; for(int k = 0; k < BITS; k++) { bi += B[i][k] * (1 << k); ci += C[i][k] * (1 << k); } if(bi != b[i] || ci != c[i]) return false; } return true; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif // ONLINE_JUDGE ios::sync_with_stdio(false); cin >> n; a.resize(n); b.resize(n); c.resize(n); for(int i = 0; i < n; i++) cin >> b[i]; for(int i = 0; i < n; i++) cin >> c[i]; if(n == 1) { cout << (b[0] == c[0] ? b[0] : -1) << endl; return 0; } LL sumA = 0; for(int i = 0; i < n; i++) { sumA += c[i] + b[i]; } if(sumA % (2LL * n)) { cout << -1 << endl; return 0; } sumA /= (2LL * n); for(int i = 0; i < n; i++) { a[i] = b[i] + c[i] - sumA; if(b[i] == 0 && a[i] != 0) { cout << -1 << endl; return 0; } if(a[i] % n || a[i] < 0) { cout << -1 << endl; return 0; } a[i] /= n; } if(check() == false) { cout << -1 << endl; return 0; } for(int i = 0; i < n; i++) { cout << a[i] << " \n"[i == n - 1]; } return 0; }