F. Anton and School 位运算 + 化简

http://codeforces.com/contest/734/problem/F

因为 x + y = (x & y) + (x | y)

有了这个公式后，然后应该手动模拟一下，把公式化简。一开始的时候知道有这个公式，但是自己却不动手。动手能力太差。思考能力太弱了。

如果你肯动手，这题是可以化简的，当然后面的还需要一些技巧来判断

b[i] + c[i] = (a[i] + a[j] )（1 <= j <= n）

这是根据我们的公式得来的。

所以b[i] + c[i] = n * a[i] + suma

然后对n个式子求和。(sumb + sumc - n * suma) / n = suma

所以就能得到suma = (sumb + sumc) / (2 * n)

所以就能每个每个算出a[i]

算完后，还要判断下a[i]是否合法。

比如

3

5

这样你算出来的是4，但是是不合法的

所以要检验下，检验的时候暴力是O(n * n)，要技巧。

就是，比如

10110

01110

10111

01000

把a[i]都弄成二进制。

如果是 & 操作。

对于第一个数，就是b[1]

如果当前位是0，那什么都不用说了，不贡献，

如果是1，那么，记cnt[k]表示那一位有多少个，比如cnt[1] = 3

此时的贡献是cnt[1] * (1 << j)个。

|的操作类似，不过如果当前位是1，就要加上n * (1 << j)，否则就和上面的差不多了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

const int maxn = 200000 + 20;
int b[maxn];
int c[maxn];
int a[maxn];
int t[maxn];
int n;
bool dp[maxn][32];
int cnt[32];
bool check() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 30; ++j) {
            dp[i][j] = a[i] & (1 << j);
            cnt[j] += dp[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        int tb = 0;
        int tc = 0;
        for (int j = 0; j <= 30; ++j) {
            if (dp[i][j]) {
                tc += (1 << j) * n;
            } else {
                tc += (1 << j) * cnt[j];
            }
            if (dp[i][j] == 0) continue;
            tb += (1 << j) * cnt[j];
        }
        if (tb != b[i] || tc != c[i]) {
            return false;
        }
    }
    return true;
}
void work() {
//    printf("%d
", 1 << 30);
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        sum += b[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        t[i] = b[i] + c[i];
        sum += c[i];
    }
    if (sum % (2 * n) != 0) {
        printf("-1
");
        return;
    }
    LL tsum = sum / (2 * n);
    for (int i = 1; i <= n; ++i) {
        if (t[i] - tsum < 0 || (t[i] - tsum) % n != 0) {
            printf("-1
");
            return;
        }
        a[i] = (t[i] - tsum) / n;
    }
    if (!check()) {
        cout << "-1" << endl;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
}
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}