[洛谷 4301][CQOI2013]新Nim游戏

题目链接

https://www.luogu.org/problem/P4301

题解

根据 Nim 游戏的结论，我们不能给对手留下任何一个异或和为 0 的子集，否则对手就可以取走不属于这个子集的其他石子，从而给我们留下必败局面。

考虑使用线性基。我们先对所有火柴按从大到小的顺序排序。先尝试插入最大的数字，如果不能插入这个数字，就把这个数字累加到答案中。

#include <iostream>
#include <algorithm>
using namespace std;
int a[105],p[35];
bool cmp(int a,int b)
{
 return a>b;
}
bool find(int x)
{
 for(int i=30;i>=0;i--)
  if((x>>i)&1)
  {
   if(!p[i])break;
   else x^=p[i];
  }
 return x>0;
}
void add(int x)
{
 for(int i=30;i>=0;i--)
  if((x>>i)&1)
  {
   if(p[i])x^=p[i];
   else
   {
    p[i]=x;
    break;
   }
  }
}
int main()
{
 long long k,ans=0;
 cin>>k;
 for(int i=1;i<=k;i++)
  cin>>a[i];
 sort(a+1,a+k+1,cmp);
 for(int i=1;i<=k;i++)
  if(find(a[i]))add(a[i]);
  else ans+=a[i];
 cout<<ans<<endl;
 return 0;
}