【题解】 CF734F 【Anton and School】

题解 CF734F 【Anton and School】

传送门

这种将位运算和普通运算结合起来的题目要拆位来考虑，可以得到\(log_{2}(\)值域\()\)的算法，甚至将值域看成常数。

根据

\(a|b+a \& b=a+b\)

得到

\(b_i+c_i=\Sigma a_i+na_i\)

于是

\(a_i=\frac{b_i+c_i- \Sigma a_i}{n}\)

根据这个式子，直接得到\(a_i\)，注意在除的时候判断整除以免非法情况出现。

此时，我们要判断\(b_i\)和\(c_i\)是否真的合法，考虑到位运算的性质，我们开个\(cnt[x]\)，记录所有\(a_i\)在二进制第\(x\)位出现的次数，此时，我们只需要检验——

\(b_i=2^k \times cnt[k]\)

\(c_i=\Sigma a_i+2^k \times (n-cnt[k])\)

这里的\(k\)满足

\(a_i\&(1<<(k-1))\)

总复杂度\(O(nlog(\)值域\())\)，相当于\(O(n)\)，但理论上会爆\(unsigned\) \(long\) \(long\) 但是它没有爆。

极其丑陋的代码

#include<bits/stdc++.h>

#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)

#define qit return puts("-1"),0

using namespace std;typedef unsigned long long ll;

template<class ccf> inline ccf qr(ccf k){

    char c=getchar();

    ccf x=0;

    int q=1;

    while(c<48||c>57)q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

const int maxn=200005;

ll a[maxn];

ll b[maxn];

ll c[maxn];

ll cnt[65];

ll n;ll sum;

int main(){

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);

    RP(t,1,n)

	b[t]=qr(1ll);

    RP(t,1,n)

	c[t]=qr(1ll);

    RP(t,1,n)

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

    if(sum%(n<<1))

	qit;

    sum/=(n<<1);

    RP(t,1,n){

	a[t]=b[t]+c[t]-sum;

	if(a[t]%n)

	    qit;//宏

	else

	    a[t]/=n;

	RP(i,1,63)

	    if((a[t]&(1ll<<(i-1))))

		cnt[i]++;

    }

    ll temp=0;

    RP(t,1,n){

	temp=0;

	RP(i,1,63)

	    if(a[t]&(1ll<<(i-1)))

		temp+=cnt[i]*(1ll<<(i-1));

	if(temp!=b[t])

	    qit;//宏

	temp=sum;

	RP(i,1,63)

	    if(a[t]&(1ll<<(i-1)))

		temp+=(n-cnt[i])*(1ll<<(i-1));

	if(temp!=c[t])

	    qit;//宏

    }

    RP(t,1,n)

	cout<<a[t]<<' ';

    puts("");

    return 0;

}

巴特西