[C++知识库]蓝桥杯真题：异或数列

?

输入输出样例

示例 1

输入

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

输出

1
0
1
1

评测用例规模与约定

对于所有评测用例，1≤T≤200000，1≤i=1∑T?ni?≤200000,0≤Xi?<2020?。?

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

这题是很巧妙的一道位运算题目，参考：

蓝桥杯2021年第十二届省赛-异或数列_zy98zy998的博客-CSDN博客_蓝桥杯异或数列

如果是平局，A^B=0其实等价于所有输入的数异或等于0

再来看先手后手：

?代码如下所示：

#include <bits/stdc++.h>
using namespace std;
int num[23];
long long a;
void pre(long long a)
{
  int cnt=1;
  while(a)
  {
    if(a&1) num[cnt]++;
    a>>=1;
    cnt++;
  }
}
int main()
{
  // 请在此输入您的代码
  int T;
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>T;
  while(T--)
  {
    memset(num,0,sizeof(num));
    int n,sum=0;
    cin>>n;
    for(int i=0;i<n;++i)
    {
      cin>>a;
      pre(a);
      sum^=a;
    }
    if(!sum) printf("0\n");
    else 
    {
      for(int i=20;i>0;--i)
      {
        if(num[i]==1)
        {
          printf("1\n");
          break;
        }
        else if(num[i]%2==1)
        {
          if(n%2==1)
          {
            printf("1\n");
            break;
          }
          else if(n%2==0)
          {
            printf("-1\n");
            break;
          }
        }
      }
    }
  }
  return 0;
}