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]是否合法。

比如

这样你算出来的是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 =  + ;

int b[maxn];

int c[maxn];

int a[maxn];

int t[maxn];

int n;

bool dp[maxn][];

int cnt[];

bool check() {

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= ; ++j) {

            dp[i][j] = a[i] & ( << j);

            cnt[j] += dp[i][j];

        }

    }

    for (int i = ; i <= n; ++i) {

        int tb = ;

        int tc = ;

        for (int j = ; j <= ; ++j) {

            if (dp[i][j]) {

                tc += ( << j) * n;

            } else {

                tc += ( << j) * cnt[j];

            }

            if (dp[i][j] == ) continue;

            tb += ( << j) * cnt[j];

        }

        if (tb != b[i] || tc != c[i]) {

            return false;

        }

    }

    return true;

}

void work() {

//    printf("%d\n", 1 << 30);

    cin >> n;

    LL sum = ;

    for (int i = ; i <= n; ++i) {

        cin >> b[i];

        sum += b[i];

    }

    for (int i = ; i <= n; ++i) {

        cin >> c[i];

        t[i] = b[i] + c[i];

        sum += c[i];

    }

    if (sum % ( * n) != ) {

        printf("-1\n");

        return;

    }

    LL tsum = sum / ( * n);

    for (int i = ; i <= n; ++i) {

        if (t[i] - tsum <  || (t[i] - tsum) % n != ) {

            printf("-1\n");

            return;

        }

        a[i] = (t[i] - tsum) / n;

    }

    if (!check()) {

        cout << "-1" << endl;

        return;

    }

    for (int i = ; i <= n; ++i) {

        cout << a[i] << " ";

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

F. Anton and School 位运算 + 化简

最新文章

热门文章