【atcoder】Two Sequences [arc092 D]（思维题）

　　题目传送门：https://arc092.contest.atcoder.jp/tasks/arc092_b

　　这场arc好难啊。。。这场感觉不像正常的arc。。。其实这道题还可以更早写出来的，但是蒟蒻解不等式的时候搞错解集了，一个错调了半天。。。

　　我的做法是首先按位考虑，求所有的a_i+b_j中每个数位的xor和。

　　首先我们可以想到，如果有两个数x,y，且0<x,y<=2^k，那么当0<=x+y<2^k时，x+y在2^k这一位上的贡献肯定为0。

　　但是如果2^k+1<=x+y<2^k+1+2^k，那么x+y在2^k这一位上的贡献依然为0，此时就相当于x+y在2^k这一位上的贡献被后面的数的进位抹去了。

　　于是用在计算答案的第k位时，把序列a,b中的数的最后k位算出来，设为a’,b'，然后把b'排个序，用二分的方式找a'_i+b'_j>2^k-1和2^k<=a'_i+b'_j<2^k+2^k-1的方案数，两者相减后判断一下奇偶性就行了。

　　我觉得肯定有更快的写法...这个$O(28nlog(n))$的写法巨慢……

　　代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#define ll long long

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define inf 0x3f3f3f3f

#define mod 1000000007

#define eps 1e-18

inline ll read()

{

    ll tmp=; char c=getchar(),f=;

    for(;c<''||''<c;c=getchar())if(c=='-')f=-;

    for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-'';

    return tmp*f;

}

using namespace std;

ll a[],b[];

ll tmp[];

int n;

ll find(ll k)

{

    int l=,r=n+;

    while(l<r){

        int mid=(l+r)>>;

        if(tmp[mid]>=k)r=mid;else l=mid+;

    }

    return l;

}

int main()

{

    int i,k;

    n=read();

    for(i=;i<=n;i++)a[i]=read();

    for(i=;i<=n;i++)b[i]=read();

    ll ans=;

    for(k=;k<=;k++){

        ll base=(<<k)-;

        for(i=;i<=n;i++)tmp[i]=b[i]&base;

        sort(tmp+,tmp+n+);

        ll cnt=;

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

            cnt+=n-find((<<(k-))-(a[i]&base))+;

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

            cnt-=find((<<k)+(<<(k-))-(a[i]&base))-find((<<k)-(a[i]&base));

        if(cnt&)ans+=(<<(k-));

    }

    printf("%lld\n",ans);

}

arc092 D

巴特西

【atcoder】Two Sequences [arc092 D]（思维题）

最新文章

热门文章