题解21 毒瘤XOR

前言：题别看错了，最初我看成是要求异或完后结果的最大值，然后写了代码，最后发现答案怎么都是0+31个1。 一看题，原来是求所有异或结果的最大值，那么只要让所有数每一位的1尽可能多就行了，那么就是求所有事每一个二进制位1的个数，1多x那一位就是0，0多x那一位就是1一样多就无所谓了（因为二进制转化成十进制其实是2的（对应位数-1）次方）,所以只要每一位所有数那一位1的个数和尽可能多就行。然后看到要不停的查询（最多1e5），那就利用前缀和和差分。 AC代码&思路：

#include<iostream>
using namespace std;
int a[100005];
int sum[100005][35]={0,0};//全局int变量好像默认初始化为0，这里是为了在算第一个前缀和是把前一个数看成0
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int i;
    for (int i=1; i<=n; ++i) 
    {
        cin>>a[i]; 
        for (int j=0; j<=30; ++j)
        {
            sum[i][32-j]=sum[i-1][32-j];//不要把这句写到底下去了，因为求前缀和无论怎么样都要加前面的
            if (((a[i]>>j)&1)==1) {++sum[i][32-j];}
        }
    }
    int q,l,r;
    cin>>q;
    while(q--)
    {
        cin>>l>>r;
        int res=0;
        for(int k=2; k<=32; k++)
        {	//即sum[r][k]-sum[l-1][k]<=(r-l+1/*植树原理*/)-(sum[r][k]-sum[l-1][k])
            if((sum[r][k]-sum[l-1][k])*2 <= r-l+1){res |= 1<<(32-k);}//防溢出用|=代替+=
        }
        cout<<res<<'\n';
    }
    return 0;
}

PS:用32-k是为了把第1-32位正向保存在数组中，符合直觉些 下附不用32-k,逆向保存的代码：

#include<iostream>
using namespace std;
int a[100005];
int sum[100005][35]={0,0};//全局int变量好像默认初始化为0，这里是为了在算第一个前缀和是把前一个数看成0
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int i;
    for (int i=1; i<=n; ++i) 
    {
        cin>>a[i]; 
        for (int j=0; j<=30; ++j)
        {
            sum[i][j]=sum[i-1][j];//不要把这句写到底下去了，因为求前缀和无论怎么样都要加前面的
            if (((a[i]>>j)&1)==1) {++sum[i][j];}
        }
    }
    int q,l,r;
    cin>>q;
    while(q--)
    {
        cin>>l>>r;
        int res=0;
        for(int k=0; k<=30; k++)
        {	//即sum[r][k]-sum[l-1][k]<=(r-l+1/*植树原理*/)-(sum[r][k]-sum[l-1][k])
            if((sum[r][k]-sum[l-1][k])*2 <= r-l+1){res |= 1<<k;}//防溢出用|=代替+=
        }
        cout<<res<<'\n';
    }
    return 0;
}