一、取石子：
有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？
SG[0]=0，f[]={1,3,4},
x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此类推…
x 0 1 2 3 4 5 6 7 8…
SG[x] 0 1 0 1 2 3 2 0 1…
由上述实例我们就可以得到SG函数值求解步骤，那么计算1~n的SG函数值步骤如下：
1、使用 数组f 将 可改变当前状态 的方式记录下来。
2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。
3、最后模拟mex运算，也就是我们在标记值中 搜索 未被标记值 的最小值，将其赋值给SG(x)。
4、我们不断的重复 2 - 3 的步骤，就完成了 计算1~n 的函数值。
//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[maxn],S[maxn];
void getSG(int n)
{
int i,j;
memset(SG,0,sizeof(SG));
//因为SG[0]始终等于0，所以i从1开始
for(i = 1; i <= n; i++)
{
//每一次都要将上一状态 的 后继集合 重置
memset(S,0,sizeof(S));
for(j = 0; f[j] <= i && j <= N; j++)
S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记
for(j = 0;; j++)
if(!S[j])
{ //查询当前后继状态SG值中最小的非零值
SG[i] = j;
break;
}
}
return;
}
二、kiki和cici抓牌：
----总共n张牌
----双方轮流抓
----每人每次抓的牌的个数只能是2的次幂（1，2，4，8，16……）
----最后抓完牌的人胜kiki先抓。
n 0 1 2 3 4 5 6 7 8 9 10
2n 1 2 4 8 16 32 64 128 256 512 1024
sum 1 3 7 15 31 63 127 255 511 1023 2047
发现：当牌数为3，15，63，255，1023张牌时cici赢。
大胆猜测，当牌数为3的倍数时cici赢。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
int x[12],SG[1050];
bool vis[1050];
void init(void)
{
for(int i=0;i<11;i++)
x[i]=1<<i;
SG[0]=0;
for(int i=1;i<1002;++i)
{
memset(vis,0,sizeof(vis));
for(int j=0;x[j]<=i;++j)
{
vis[SG[i-x[j]]]=true;
}
for(int j=0;;++j)
{
if(!vis[j])
{
SG[i]=j;
break;
}
}
}
return ;
}
int main(void)
{
int n;
init();
while(scanf("%d",&n)!=EOF)
{
if(SG[n]) printf("kiki\n");
else printf("cici\n");
}
return 0;
}
三、n元环：
n元环，每次取连续的m个元素，最先不能取者败。
可以考虑n＜m和n≥m两种情况，第一种情况结果显然，第二种将取过1次后剩下的n-m元链进行求SG值，前m-1个状态的SG值明显为0，m为1，之后的状态（成链之后）取走m个元素之后，会将剩下的分为2段（考虑0的情况），分别求其SG值，从而得到当前状态的一个后继SG值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=1005;
int SG[maxn];
bool vis[maxn];
bool sg(int n,int m)
{
memset(SG,0,sizeof(SG));
SG[m]=1;
for(int i=m+1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
for(int j=0;j<=i-m;j++)
vis[SG[j]^SG[i-m-j]]=true;
for(int j=0;;j++)
{
if(!vis[j])
{
SG[i]=j;
break;
}
}
}
return SG[n];
}
int main(void)
{
int t;
int n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
if(m>n) printf("hou shou sheng\n");
else if(sg(n-m,m)) printf("hou shou sheng\n");
else printf("xian shou sheng\n");
}
return 0;
}
SG函数递归写法：
memset(p,-1,sizeof(p));
int get_sg(int len)
{
if(p[len]!=-1) return p[len];
if(len<m) return p[len]=0;
bool vis[maxn];
memset(vis,0,sizeof(vis));
for(int i=0;len-m-i>=0;i++)
vis[get_sg(i)^get_sg(len-i-m)]=true;
for(int i=0;;i++)
if(!vis[i])
return p[len]=i;
}
四、三连X：
两个人轮流在1*N的格子纸上打叉，最先打出连续三个叉者获胜，问必胜者是谁。
X_X和_XX_会打出连续三个X，两个选手一定会避免走出上面的局面，当一个选手画了一个X之后，假设局面时12X34，其中数字代表空位，为了避免上面的情况出现，1234这四个位置一定不能走，如果走了的话就必输。因此我们可以等效成画了一个X之后，连通左右两边各两个格子都被拿掉了。
在第K个位置上放了一个X，即可分为两个子游戏K-3和n-K-2。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005;
int sg[1005];
int dfs(int n)
{
if(n<0) return 0;
if(sg[n]>=0) return sg[n];
bool ha[maxn]={false};
for(int i=1;i<=n;i++)
{
ha[dfs(i-3)^dfs(n-i-2)]=true;
}
for(int i=0;;i++)
if(!ha[i])
return sg[n]=i;
}
int main(void)
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(sg,-1,sizeof(sg));
if(dfs(n)) printf("1\n");
else printf("2\n");
}
return 0;
}
五、有向图走棋子：
两个人挪棋子，棋子放在棋盘上，可以有多个棋子，一个人挪动的时候可以移动到链接到的下一个点，当一个人不能挪动棋子的时候就输了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1005;
int SG[1005];
int n,m;
vector<int>G[maxn];
int dfs(int u)
{
int i;
if(SG[u]!=-1) return SG[u];
bool vis[maxn];
memset(vis,0,sizeof(vis));
for(i=0;i<G[u].size();i++)
vis[dfs(G[u][i])]=true;
i=0;
while(vis[i]) i++;
return SG[u]=i;
}
int main(void)
{
memset(SG,-1,sizeof(SG));
int k,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
if(k==0) SG[i]=0;
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
G[i].push_back(x);
}
}
int _xor=0;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
_xor^=dfs(x);
}
if(_xor) printf("1\n");
else printf("2\n");
return 0;
}
六、单行有限制性移动棋子：
一个1*M的棋盘上有N个棋子，初始位置一定，两人轮流操作，每次移动一枚棋子，要求只能向左移动且至少移动一格，而且不能到达或经过其前有棋子的格子，谁无法移动就算输。
先考虑两个棋子靠在一起的时候，这两个棋子就构成了一个奇异局势（P点）。所以可以把题目中的棋子分解为两两一对，每两对之间是不需要考虑什么的。在同一对棋子中，如果对手移动前一个，你总能对后一个移动相同的步数，所以一对棋子的前一个和前一对棋子的后一个之间有多少个空位置对最终的结果是没有影响的。每两个构成一组，而这两个之间就是一堆石子。然后就可以NIM博弈了，如果是奇数个棋子，首个棋子要跟棋盘首构成一对。
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[0]=0;
sort(a+1,a+n+1);
for(int i=n;i>0;i-=2)
sum^=(s[i]-s[i-1]-1);
if(sum) printf("1\n");
else printf("2\n");
七、先手赢第一步：
给定n个数，每一步都可以将某个数替换为它的因子，但不能替换为本身，两个人轮流走，知道某个人走不了，他就输了。如果先手赢，输出第一步。
int change(int num)
{
int ans=0;
for(int i=0;prime[i]*prime[i]<=num;i++)
{
while(num%prime[i]==0)
{
num/=prime[i];
ans++;
}
}
if(num>1) ans++;
return ans;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&temp)
a[i]=change(tamp);
sum^=a[i];
}
if(sum==0) printf("2\n");
else
{
printf("1\n");
for(int i=1;i<=n;i++)
{
if((sum^a[i])<a[i])
{
printf("%d\n",i);
break;
}
}
}
（1）对于某个局面（a1，a2，……an），若a1 xor a2 xor……xor an ！=0，一定存在某个合法移动，将ai变成_ai后满足a1 xor a2 xor…xor _ai xor…xor an =0。不妨设a1 xor a2 xor……xor an =k，则一定存在某个ai，它的二进制表示在k的最高为上是1，否在k的最高为上的那个1是怎么得到的。这时ai xor k ＜ ai一定成立。我们可以将ai改变成_ai=ai xor k。此时a1 xor a2 xor…xor _ai xor…xor an = a1 xor a2 xor……xor an xor k=0。
（2）(a1，a2，……an），若a1 xor a2 xor……xor an =0，一定不存在某个合法移动，将ai变成_ai后满足a1 xor a2 xor…xor _ai xor…xor an =0。因为异或运算满足消去率，由
a1 xor a2 xor…xor _ai xor…xor an = a1 xor a2 xor……xor an 得到ai=_ai。所以将ai变成_ai不是一个合法移动。
所以如果当前局面是必胜的话，则由性质（1）知，必定存在一个合法移动，使下一局面必败。
可利用ai xor k＜ai判断。
京公网安备 11010502036488号