组合游戏略述——浅谈SG游戏的若干拓展及变形

Anti-SG 游戏
桌子上有 N 堆石子,游戏者轮流取石子。
每次只能从一堆中取出任意数目的石子,但不能不取。
取走最后一个石子者败。
 Anti-SG 游戏规定,决策集合为空的游戏者赢。
 Anti-SG 其他规则与 SG 游戏相同。
[结论](SJ 定理)
先手必胜当且仅当:( SG(i)=i )
(1)游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1;
(2)游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。

https://vjudge.net/problem/HDU-2509

#include <cstdio>
using namespace std;
int main()
{
       int n,m;
   while(scanf("%d",&n)!=EOF)
   {
       int ans=0,flag=0;
       for(int i=0;i<n;i++)
       {
           scanf("%d",&m);
           ans^=m;
           if(m>1) flag=1;//当所有数据都为1时的特判
       }
       if(flag){
        if(ans==0) puts("No");
        else puts("Yes");
       }
       else
       {
           if(n&1) puts("No");
           else puts("Yes");
       }
   }
}

Every-SG 游戏

待补充

翻硬币游戏
一般的翻硬币游戏的规则是这样的:
 N 枚硬币排成一排,有的正面朝上,有的反面朝上。我们从左开
始对硬币按 1 到 N 编号。
 游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者每
次只能翻连续的几枚),但他所翻动的硬币中,最右边的必须是
从正面翻到反面。
 谁不能翻谁输。
有这样的结论:局面的 SG 值为局面中每个正面朝上的棋子单一存在
时的 SG 值的异或和。

#include<cstdio>
#include<string.h>
#include<set>
using namespace std;
//const int maxn=1010;
//int fx[maxn],g[maxn];
//void getSG()
//{
//    memset(fx,0,sizeof(fx));
//    for(int i=0;i<=100;i++)
//    {
//        memset(g,0,sizeof(g));
//
//        g[0]=1;//翻一个硬币，先手必赢
//
//        for(int j=0;j<i;j++)//翻两个硬币
//        {
//            g[fx[j]]=1;
//        }
//
//        for(int j=0;j<i;j++)//翻三个硬币
//        {
//            for(int k=0;k<j;k++)
//            {
//                g[fx[j]^fx[k]]=1;
//            }
//        }
//
//        for(int j=0;;j++)
//        {
//            if(!g[j])
//            {
//                fx[i]=j;
//                break;
//            }
//        }
//        printf("i:%d SG(): %d\n",i,fx[i]);
//    }
//}
int sumOfOne(int x)
{
    int sum=0;
    while(x)
    {
        if(x&1) sum++;
        x>>=1;
    }
    return sum;
}
int main()
{
   int n,tmp,res;
   while(scanf("%d",&n)!=EOF)
   {
       set<int> ss;
       res=0;
       for(int i=0;i<n;i++)
       {
           scanf("%d",&tmp);
           if(ss.find(tmp)==ss.end())
           {
               if(sumOfOne(tmp)&1) res^=tmp*2;
               else res^=(tmp*2+1);
               ss.insert(tmp);
           }
       }
       if(res) printf("No\n");
       else printf("Yes\n");

   }
    return 0;
}