codeforces 734F Anton and School

题目链接

题目大意

给出两个长度为N的序列Bi,Ci(N<=2*10^{5)。所有数均是<=10}9的自然数。
已知：
B[i]=∑[1<=j<=N] (A[i] and A[ j ])
C[i]=∑[1<=j<=N] (A[i] or A[ j ])
求解序列Ai，输出任意一组解，无解输出-1。

解答

一开始我用(a or b)-(a and b)=(a xor b)的公式，得到C[i]-B[i]的序列，画样例画不出来。最后弃疗，看大神代码，发现使用的正确公式是：(a or b)+(a and b)=a+b。利用这个公式，把所有的Bi和Ci求和，就得到了2N×∑[1<=i<=N] (A[i])。除以2N得到Ai的和(记为sum)，然后由B[i]+C[i]=N*A[i]+sum解出所有的A[i]。

但问题还没有结束，这样求出的A[i]是经过B[i]+C[i]的推导求出的，不一定满足题目已知的两个条件，只是唯一的可能解。因此，我们还要用A[i]推一遍B[i]和C[i]，看是否满足条件。这个只要拆位处理一下就可以了。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))

const int maxn=200000+100;
int N,B[maxn],C[maxn];
int A[maxn];

bool check()
{
    static int g[32];
    Mem(g,0);
    For(j,0,30)
        For(i,1,N)
            g[j]+=(A[i]>>j&1);
    For(i,1,N)
    {
        long long b=0,c=0;
        For(j,0,30)
        {
            if (A[i]>>j&1) b+=(bll)g[j]*(1<<j);
            if (A[i]>>j&1) 
                c+=(bll)N*(1<<j);
            else
                c+=(bll)g[j]*(1<<j);
        }
        if (b!=B[i] || c!=C[i]) return 0;
    }
    return 1;
}

bool Done()
{
    long long sum=0;
    For(i,1,N) sum+=B[i];
    For(i,1,N) sum+=C[i];
    if (sum%(2*N)) return 0;
    sum/=2*N;
    For(i,1,N)
    {
        int tt=B[i]+C[i]-sum;
        if (tt%N) return 0;
        A[i]=tt/N;
    }
    if (!check()) return 0;
    return 1;
}

int main(int argc, char* argv[])
{
    for (; scanf("%d",&N)!=EOF; )
    {
        For(i,1,N) scanf("%d",&B[i]);
        For(i,1,N) scanf("%d",&C[i]);
        if (Done())
        {
            For(i,1,N) 
            {
                printf("%d",A[i]);
                if (i<N) printf(" ");
            }
            printf("\n");
        }
        else printf("-1\n");
    }
    return 0;
}