P11016 XOR Pairs 题解

· · 题解

可能没人能想到我这只蒟蒻会来写这题题解吧。

赛时打了个暴力（因为太菜了），只拿了 13pts。赛后求助机构老师，老师给出了代码，我自己边打边研究了下，有些没写注释的地方我自己看懂了。感谢老师的指导！

因为数据量比较大，O(n^2) 的时间复杂度肯定会超。

那我们该怎么办呢？

想让 x \oplus y > \max(x,y)（注：\oplus 代表异或），那么 x 的最高位 1 一定对应 y 位置的 0 ，所以统计最高位的 1 和每个位置的 0，再使用排列组合实现。（注：这篇题解所有最高位的 1 和每一位的 0 都是二进制下的！别搞错了！！！！！）

所以，每输入一个数，我们都需要求这个数最高位的 1 和每一位的 0。

这一部分的代码如下：

void find1(int x,int v)
{
    int a=1;
    int n=-1;
    while(x)//如果 x>0，那就判断 x 的最后一位是不是 1
    {
        if((x&1)==1)//如果是，n 就变成 a
        {
            n=a;
        }
        a++;
        x>>=1;
        //a 增加 1，x>>=1 的效果与 x/=2 差不多，部分童鞋可以检查下这部分是不是脑子混掉然后直接写上 x/=10 捏~
    }
    b1[n]+=v;//b1[n] 要加上 v。
}//查找最高位的 1。
void find0(int x,int v)
{
    int a=1;
    while(x)//如果 x>0，那就判断 x 的最后一位是不是 0 
    {
        if((x&1)==0)//如果是，b0[a] 就要加上 v。
        {
            b0[a]+=v;
        }
        a++;
        x>>=1;
    }
}//查找每一位的 0。
//这段虽然和上面那个查找最高位的 1 差不多，但是功能上还是有差异的。这个是查找每一位的 0 的。

下面的主函数实现方式也很简单，我们可以边输入边统计最高位的 1 和每一位的 0，然后每次询问（更改）都要清空数组里与原数字相应的位置，再统计新数字最高位的 1 和每一位的 0（有点儿啰嗦，其实写到这里我自己满脑子也都是最高位的 1 和每一位的 0 了 hhh）。

上代码（除了老师的注释，我自己也加了很多注释，有很多关于自己对代码的解读，如果有问题，可以帮我纠正捏~）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long b1[105],b0[105],a[N],n,q;
long long ans;
void find1(int x,int v)
{
    int a=1;
    int n=-1;
    while(x)//如果 x>0，那就判断 x 的最后一位是不是 1
    {
        if((x&1)==1)//如果是，n 就变成 a
        {
            n=a;
        }
        a++;
        x>>=1;
        //a 增加 1，x>>=1 的效果与 x/=2 差不多，部分童鞋可以检查下这部分是不是脑子混掉然后直接写上 x/=10 捏~
    }
    b1[n]+=v;//b1[n] 要加上 v。
}//查找最高位的 1。
void find0(int x,int v)
{
    int a=1;
    while(x)//如果 x>0，那就判断 x 的最后一位是不是 0 
    {
        if((x&1)==0)//如果是，b0[a] 就要加上 v。
        {
            b0[a]+=v;
        }
        a++;
        x>>=1;
    }
}//查找每一位的 0。
//这段虽然和上面那个查找最高位的 1 差不多，但是功能上还是有差异的。这个是查找每一位的 0 的。
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        find1(a[i],1);
        find0(a[i],1);
        //这里可以边输入边找最高位的 1 和每一位的 0。
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        find1(a[x],-1);
        find0(a[x],-1);
        find1(y,1);
        find0(y,1);
        a[x]=y;
        //因为 a[x] 被更改了，所以这里需要清掉 b1 和 b0 两个数组原本因为 a[x] 造成的改变，并重新统计 y 的最高位的 1 和每一位的 0，存进 b1 和 b0。
        ans=0;
        for(int i=1;i<=32;i++)
        {
            ans+=b1[i]*b0[i];//求修改后数组中合法二元组的个数。
        }
        cout<<ans<<endl;//输出！
    }
    return 0;//华丽结束~~~
}

求管理大大通过捏~