题意：T个例子，n堆,然后对应 堆的个数 a, b c .... 还是alice先拿再bob ，游戏规则相对Nim博弈有些不一样。这次是将每堆分成两堆，且所分堆的个数必须大于等于1 . 问谁能赢;
思路：根据sg函数结论求值
1.最终局面sg值为0则先手必输
2.所有子游戏的sg值异或后等于原游戏的sg值
所以利用这两个结论对模板进行修改求值；
以前总结的模板：
#define maxn 1e4+10//maxn为堆中最大个数 #define cmax 1005//cmax为取个数的方法总数 using namespace std; int sg[maxn];//记录sg[n]（n为堆的个数）sg值 int mex[maxn];//模拟mex运算 int get[cmax];// void get_sg() { // 例如有三种情况的取石子方法 get[1] = 1,get[2] = 2,get[3] = k; // 然后注意如果题目所要求堆个数过大即要找规律，不能直接用sg函数运算 memset(sg,0,sizeof(sg)); //i小于需要求的sg范围：默认堆最大个数maxn内 for(int i=1;i<=maxn;i++) { memset(mex,0,sizeof(mex)); //条件为get[j]必须小于i才合法&&总类数小于cmax //要根据不同题目要求来写对应的取法 for(int j=1;get[j]<=i&&j<=cmax;j++) mex[sg[i-j]]=1;//状态转移（注意根据不同题要求来写） //比如：此题分堆问题，mex[sg[j]^sg[i-g]]=1; for(int j=0;j<=maxn;j++)//j小于等于堆中最大个数 { if(!mex[j]) { sg[i]=j; break; } } //找规律输出 // printf("sg[%d]:%d ",i,sg[i]); } }
此题完整题解：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> const int maxn=1e4+10; //const int maxn=105; const int mod=1e9+7; using namespace std; int sg[maxn]; int mex[maxn]; void getsg() { for(int i=1;i<=maxn;i++) { memset(mex,false,sizeof(mex)); for(int j=1;j*2<i;j++) { if(i!=j*2) { mex[sg[j]^sg[i-j]]=1;//（利用子堆状态转移：子堆异或值等于原堆） } } for(int j=0;j<maxn;j++) { if(!mex[j]) { sg[i]=j; break; } } // printf("sg[%d]:%d ",i,sg[i]); } return; } int main(){ int T,cnt=0; getsg(); cin>>T; while(T--){ int n,ans=0; cin>>n; for(int i=0;i<n;i++){ int m; cin>>m; ans^=sg[m]; } cout<<"Case "<<++cnt<<": "; if(ans) cout<<"Alice"<<endl; else cout<<"Bob"<<endl; } }