传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。
本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。
如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。
【输入格式】
第一行为整数k。即火柴堆数。第二行包含k个不超过109的正整数，即各堆的火柴个数。
【输出格式】
输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1。
【输入输出样例】
nim.in
nim.out
6
5 5 6 6 5 5
21
nim.in
nim.out
3
1 2 3
1
【数据范围】
编号
1-5
6-10
k
<=10
<=100
现场考这个题的时候，我看到这个题就笑了（原来做过类似的（BJOI2010元素）），本弱就是靠这个题进了省队啊。
还是简单的说一下吧
本题就是选一个最大的集合，使该集合的所有子集异或起来都不得0。用拟阵证明这个题用贪心算法是对的，然后用类似高斯消元解异或方程的的东西就解决了。
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>using namespace std;typedef long long LLint;const LLint MAXN=220;LLint Data[MAXN],n,Ans[MAXN],Cnt,Sum,WDY;LLint Matrix[MAXN][MAXN];void Solve(){ memset(Matrix,0,sizeof(Matrix)); LLint N=0,M=0; for(LLint i=1;i<=n;++i){ LLint x=Data[n-i+1],Ret=0; while(x){ Matrix[i][++Ret]=x%2; x/=2; } M=max(M,Ret); } N=n; for(LLint i=1,j=1;i<=N&&j<=M;++i,++j){ LLint Flag=0,k=j; while(k<=M){ if(Matrix[i][k]) { Flag=1; break; } ++k; } if(!Flag){ j--; continue; } Sum+=Data[n-i+1]; for(LLint Pos=1;Pos<=N;++Pos) swap(Matrix[Pos][j],Matrix[Pos][k]); for(LLint w=i+1;w<=N;++w){ if(Matrix[w][j]){ for(LLint z=j;z<=M;++z) Matrix[w][z]^=Matrix[i][z]; } } }}int main(){ freopen("nim.in","r",stdin); freopen("nim.out","w",stdout); cin>>n; for(LLint i=1;i<=n;++i){ cin>>Data[i]; WDY+=Data[i]; } sort(Data+1,Data+1+n); Solve(); cout<<WDY-Sum; //fclose(stdin); //fclose(stdout);}
转载于:https://www.cnblogs.com/Return-0/archive/2013/04/01/2994242.html
