暑假将尽,趁此时机将各种基础做一下整体(顺路骗来访~~^_^~~)
开头先引用他人的总结:传送门
首先,一般博弈都有三个基础形式(巴什博弈、威佐夫博奕和尼姆博弈)
首先是巴什博弈:
hdu1846
在一堆中取石子,谁取到最后一个谁赢。
按巴什博奕的理论写一下就出来了
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <list> #include <map> using namespace std; int n,m; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); if(n % (m + 1) == 0) { printf("second\n"); } else { printf("first\n"); } } return 0; }
coj1703
把棋盘的x,y轴转化成两堆石子就变成了威佐夫博奕,直接求之。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <list> #include <map> using namespace std; using namespace std; bool s[200][200]; void change(int x,int y) { for(int i=1;i+x<150;i++) { s[x+i][y] = 1; } for(int i=1;i+y<150;i++) { s[x][y+i] = 1; } for(int i=1;i+x<150&&i+y<150;i++) { s[x+i][y+i] = 1; } } void get() { memset(s,0,sizeof(s)); for(int i=1;i<150;i++) { for(int j=1;j<150;j++) { if(s[i][j] == 0) { change(i,j); } } } } int main() { get(); int n; int a,b; cin>>n; while(n--) { cin>>a>>b; if(s[a][b] == 1) { cout<<"Alice"<<endl; } else { cout<<"Bob"<<endl; } } return 0; }
hdu2509
一道很标准的尼姆博弈,按照公式写就行了。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <list> #include <map> using namespace std; int n; int s; int ans,shu; int main() { while(scanf("%d",&n) != EOF) { ans = shu = 0; for(int i=0;i<n;i++) { scanf("%d",&s); if(s > 1) shu++; ans = ans ^ s; } if(!shu) { if(ans) printf("No\n"); else printf("Yes\n"); } else { if(!ans) printf("No\n"); else printf("Yes\n"); } } return 0; }
很多人说,博弈的本质的游戏,事实也正是如此,而被总结出来的三大博弈形式也就是大量人做游戏的方式。
当我们遇到与这三大类无关的题目,就需要些其他的方法了,比如找规律
hdu2147
只能向左向下或者斜向下走一格,就算按两堆来算也和和几种博弈有所差别。
通过找规律我们发现只有n%2==1&&m%2==1时后手赢,这样就简单了。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <list> #include <map> using namespace std; int n,m; int main() { while(scanf("%d%d",&n,&m)) { if(n == 0&&m == 0) break; if(n%2==1&&m%2==1) printf("What a pity!\n"); else printf("Wonderful!\n"); } return 0; }
每次做题都找规律本身是一个很麻烦的事,于是伟大的先人创造了一种泛用的可以随意使用的找规律方法,也就是SG函数
上面这些题目按照SG函数的方法都可求,特别是在和尼姆博弈结合的时候用途很广泛。
SG函数的关键是mex算法,把这个弄懂并学会调用我们就能解决大多数基础博弈了
poj2960
S—Nim游戏
求所有点的SG函数值,然后对这些值进行尼姆博弈(也就是异或一下)就可以了,很简单的一道题
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <list> #include <map> using namespace std; #define N 105 int k,m,l; int ans[N],si[N],hi[N],sg[N*N]; int cmp(int a ,int b ) { return a < b; } int mex(int x) { int i; if(sg[x]!=-1) return sg[x]; bool vis[N]; memset(vis,false,sizeof(vis)); for(i=0; i<k; i++) { int temp=x-si[i]; if(temp<0) break; sg[temp]=mex(temp); vis[sg[temp]]=true; } for(i=0;; i++) { if(!vis[i]) { sg[x]=i; break; } } return sg[x]; } int main() { while(scanf("%d",&k) != EOF) { if(!k) break; for(int i=0; i<k; i++) scanf("%d",&si[i]); sort(si,si + k,cmp); memset(sg,-1,sizeof(sg)); sg[0]=0; memset(ans,0,sizeof(ans)); scanf("%d",&m); for(int i=0; i<m; i++) { scanf("%d",&l); for(int j=0; j<l; j++) { scanf("%d",&hi[i]); ans[i]^=mex(hi[i]); } } for(int i=0; i<m; i++) { if(ans[i]==0) printf("L"); else printf("W"); } printf("\n"); } return 0; }
这里写的都是一些很基础的东西,博弈整体很深奥的
有意者可以去其他人的博客找资源传送门