当前位置：首页 > news >正文

组合博弈 sg函数 Nim游戏的板子默写

news 2026/5/12 6:47:39

简单的取子用sg(x)==0 判断不就可以了吗！！！
所有游戏单个子游戏的思想

1.sg(x)有向无环图上的棋子游戏

每个棋子和它的出边都构成单独的有向无环图
通过一个棋子的所有后继节点我们可以得到这个点的sg
ans是所有点的sg之和用于判定先后手的必胜策略

#include <bits/stdc++.h>
using namespace std;
struct node
{int v,nv;
}e[100];
int h[100];int f[100];int idx=0;void add(int u,int v)//链式前向星建边 
{e[++idx]={v,h[u]};h[u]=idx;
}int sg(int x)
{if(f[x]!=-1) return f[x];set<int>s;for(int i=h[x];i;i++)//i!=0 就是有边 所有的后继 {s.insert(sg(i));}for(int i=0;;i++){if(s.count(i)==0) return f[x]=i;//记忆化缩短时间 }
}
int main()
{memset(h,0,sizeof(h));memset(f,-1,sizeof(f));int n;cin>>n;int uu,vv;for(int i=0;i<n;i++){cin>>uu>>vv;add(uu,vv);}int ans=0;for(int i=0;i<n;i++){ans^=sg(i); //别写成+}if(ans) cout<<"先手胜"<<endl;else cout<<"后手胜"<<endl;
}

2.sg(x)集合型的Nim

和普通的nim游戏是不一样的
这个也是多堆但是有取子规则

#include <bits/stdc++.h>
using namespace std;
int k[10];int kk;//取子规则 
int f[100];
int sg(int x)
{if(f[x]!=-1) return f[x];set<int>s;//一定牢记 for(int i=0;i<kk;i++){if(x>k[i]) s.insert(sg(x-k[i]));//条件判断别漏 不然你上哪里哭去 }for(int i=0;;i++){if(s.count(i)==0) return f[x]=i;//记忆化 }
}
int main()
{memset(f,-1,sizeof(f));//革命是否胜利取决于这里 cin>>kk;for(int i=0;i<kk;i++){cin>>k[i];//题目给我们的取子规则 }int m;//堆数 int ans=0;for(int i=0;i<m;i++){int tt;cin>>tt;//每堆石子有几个 ans^=sg(i);}if(ans) cout<<"先手胜"<<endl;else cout<<"后手胜"<<endl; 
}

3.普通的nim是多堆每次从一堆中取任意个（棋盘的任意位置==一堆的个数）把替换也写一下怕自己忘了

#include <bits/stdc++.h>
using namespace std;
int main()
{int arr[100];int n;cin>>n;//有几堆 int ans=0;//0和任何数的^都是0 for(int i=0;i<n;i++){cin>>arr[i];//每堆的个数ans^=arr[i];}if(ans) cout<<"先手胜"<<endl;else cout<<"后手胜"<<endl;int count=0;for(int i=0;i<n;i++){if(ans^arr[i]<arr[i]) cout<<"可合法替换"<<endl;//做差是取出的个数 {arr[i]=ans^arr[i];count++;} } cout<<count<<endl;//合法替换的方案数目 for(int i=0;i<n;i++)//替换了之后是 {cout<<arr[i]<<" ";}}