P8743 异或序列

Demeanor_Roy · 2022-10-27 21:52:38 · 题解

• 原题链接

• 听说考前写题解能rp++?

首先我们考虑平局的情况，一个比较自然的想法就是所有数异或和为零就平局，而这个结论确实也是对的，下面简单证明一下：

• 必要性：因为Alice和Bob最后会打成平局，自然有 a = b，所以无论如何 a \ xor \ b = 0 都成立，必要性得证。

• 充分性：因为所有数异或和为零，那么将所有数任意划分为两个非空集合，这两个集合内部的元素的异或和都应该相等，那自然无论Alice和Bob怎么选数，都会形成平局，充分性得证。

那么我们就可以首先将平局的情况判断掉，下面的情况Alice不胜则负。

因为进行的是异或运算，很容易想到贪心地从高到低一位一位地考虑。假设当然在考虑第 i 位，有 x 个数当前这一位为 1 。那么就有以下三种情况：

下附代码：

#include<bits/stdc++.h>
using namespace std;
const int M=21;
int T,n,cnt[M];
int main()
{
    scanf("%d",&T);
    while(T--)
    {       
        memset(cnt,0,sizeof cnt);
        scanf("%d",&n);
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            sum^=x;
            for(int j=0;j<M;j++)    cnt[j]+=(x>>j)&1;
        }
        if(!sum)    puts("0");
        else
        {
            for(int i=20;i>=0;i--)
            {
                if(!(cnt[i]&1)) continue;
                else if(cnt[i]==1)  puts("1");
                else if((n-cnt[i])&1)   puts("-1");
                else puts("1");
                break;
            }
        }
    }
    return 0;
}

• 完结撒花~