参考资料

必败点(P点)： 前一个选手将取胜的位置
必败点(N点)： 后一个选手将取胜的位置
X=0 此时为必败点

性质：

1）所有的终结点都是必败点（P点）
2）至少一步操作就进入必败点（P） 就是必胜点（N）
3）都只能进入必胜点（N），都只能走到对方赢的点，它就是必败点（P）

巴什博弈 HDU——1846 Brave Game（巴什博弈）

只有一堆 n 个物品，规定每次最少去一个，最多 m 个。 n=(m+1)*r+s 如果s>0，给对手留下(m+1)的倍数 先手就能获胜

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        int mod=n%(m+1);
        if(mod>=1) cout<<"first"<<endl;
        else cout<<"second"<<endl;
    } 
    return 0;
}

(补充) HDU-2149 Public Sale

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=-1){
        if(n<=m){
            for(int i=n;i<=m;i++)
                cout<<i<<" ";
                cout<<endl;
        }
        else if(n%(m+1)){
            printf("%d\n",n%(m+1));
        }
        else puts("none");
    }
    return 0;
}

斐波那契博弈(FIB博弈) HDU-2516 取石子游戏

一方每次取的石子数依赖于对手刚才取得石子数
每次取的物品数不能超过上一次取的物品数的二倍且至少为一件
Zeckendorf定理(齐肯多夫定理)
结论：先手胜 当n不是斐波那契数 参考资料

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,fib[50];
    fib[0] = 2;fib[1] = 3;
    for(int i=2;i<50;i++) 
        fib[i]=fib[i-1]+fib[i-2];
    while(cin>>n){
        if(n==0) break;
        int i,flag=1;
        for(int i=0;i<50;i++){
            if(fib[i]==n) flag=0,puts("Second win");
            if(fib[i]>n) break;
        }
        if(flag) puts("First win");
    }
    return 0;
}

威佐夫博弈(Wythoff Game)### POJ 取石子游戏 (威佐夫博弈)

两个人轮流从某一堆或者同时从两堆取同样多的物品，规定每次至少取一个，多者不限
奇异局势 后拿者胜
(奇异局势的第一个值(这里假设第一堆数目小于第二堆的数目)总是等于当前局势的差值乘上1.618)
结论：
若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜。
参考资料

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    while(cin>>a>>b){
        if(a>b) swap(a,b);
        c=floor((b-a)*((sqrt(5.0)+1)/2)); //向下取整 3.14==3
        if(a == c) puts("0"); 
        else puts("1");
    }   
    return 0;
}

尼姆博弈(Nimm Game)HDU 1850 Being a Good Boy in Spring Festival （博弈）

两个人轮流从某一堆取任意多的物品，规定每次至少去一个，多者不限
任何奇异局势（a，b，c）都有a（+）b（+）c =0
（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14，21，27）。
（0，0，0）为终结点必败点，拿走 12 个 走到必败点（印证性质2 ：至少有一种方法可以走到必败点）

结论：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。

https://blog.csdn.net/qq_32175379/article/details/68947824

#include <bits/stdc++.h>
using namespace std;
//每一步可以取任意个 
int main(){
    int n,a[105],ans,cnt;
    while(cin>>n){
        if(n==0) break;
        ans=cnt=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            cin>>a[i];
            ans^=a[i];
        }
        if(ans == 0 ) puts("0");
        else{
            for(int i=0;i<n;i++){
                int k=ans^a[i];
                if(k<a[i]) cnt++;
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}

SG函数 HDU 1847 Good Luck in CET-4 Everybody!

结论：SG(X)）为0 先手必败
在一个特定范围里取

sg函数参考资料 1
sg函数参考资料 2
算法笔记–sg函数详解及其模板

【实例】取石子问题
有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;

结论：mex值为0 必败点

模板：

int mex(int x){
    if(sg[x]!= -1) return sg[x];
    bool vis[1005];
    for(int i=0;i<1005;i++) vis[i]=0;
    for(int i=0;i<1005;i++) {
        int t=x-arr[i];//找后继结点 
        if(t<0) break;
        sg[t]=mex(t);
        vis[sg[t]] = 1;//找第一个非负整数 
    }
    for(int i=0;;i++)
        if(!vis[i]) {
            sg[x] = i;
            break;
        } 
        return sg[x];
} 

完整代码：

#include <bits/stdc++.h>
using namespace std;
//每一步可是一个固定的数字 
int n,arr[15],sg[1005];

int mex(int x){//返回sg值 
    if(sg[x]!=-1) return sg[x];//已经计算过了就直接返回 
    bool vis[1005];
    for(int i=0;i<1005;i++) vis[i]=0;
    for(int i=0;i<1005;i++){
        int t=x-arr[i];//剩余 
        if(t < 0) break;
        sg[t] =mex(t);
        vis[sg[t]] = 1;
    }
    for(int i=0;;i++)
        if(!vis[i]) {
            sg[x] = i;
            break;
        }
        return sg[x];
}

int main(){
    arr[0] = 1;
    for(int i = 1;i <= 10;i++)
        arr[i]=arr[i-1]*2;
    while(cin>>n){
        memset(sg,-1,sizeof(sg));//
        if(mex(n)) puts ("Kiki");//sg是0 必败 
        else puts("Cici"); 
    }
        return 0;
}

HDU 1848 – Fibonacci again and again

#include <bits/stdc++.h>
using namespace std;
int f[40];
int vis[1005];
int sg[1005];
int a,b,c;
void gets()
{
    memset(sg,0,sizeof sg);
    for(int i=1;i<=1005;i++){
        memset(vis,0,sizeof vis);
        for(int j=0;f[j]<=i&&j<=15;j++){
            vis[sg[i-f[j]]]=1;
        }
        for(int j=0;;j++){
            if(vis[j]==0){
                sg[i]=j;
                break;
            }
        }
    }
}
int main(){

    f[0]=1;
    f[1]=1;
    f[2]=2;
    for(int i=3;i<=30;i++){
        f[i]=f[i-1]+f[i-2];
    }
    gets();
    while(cin>>a>>b>>c){
        if(a==0&&b==0&&c==0) break;
        if(sg[a]^sg[b]^sg[c]){
            cout<<"Fibo"<<endl;
        }else{
            cout<<"Nacci"<<endl;
        }
    }
    return 0;
}

!(巴什博弈论写法)

#### (补充) HDOJ1536 S-Nim（博弈）

# include <bits/stdc++.h>
using namespace std;
const int N=10000+10;
int f[N],sg[N],vis[N];
int n;

void mex(){
    memset(sg,-1,sizeof(sg));
    for(int i=0;i<=10000;i++){
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n && f[j]<=i;j++){//注意j结束条件 

            int t=i-f[j];
            vis[sg[t]]=1;
        }
        for(int j=0;;j++){
            if(!vis[j]) {
                sg[i]=j;
                break;
            }
        }
    }
}

int main(){
    int m,t,a;
    while(cin>>n){  
    if(n==0) break;
    for(int i=1;i<=n;i++) cin>>f[i];
    sort(f+1,f+1+n);//要排序啊啊 
    mex();
    cin>>m;
    while(m--){
        cin>>t;
        int sum=0;
        for(int i=0;i<t;i++) {
            cin>>a;
            sum^=sg[a];
        }
        if(sum) cout<<"W"; 
        else cout<<"L";
    }cout<<endl; 
    } 



    return 0;
}