首页 > 代码库 > 阶梯博弈
阶梯博弈
由于bestcoder的一道题，去学习了一下阶梯博弈。
大概理解如下：有n层的阶梯，每一层上都有若干的石子，可以将任何一层的石子，拿出至少一个，放到它的上一层上去，最后一个不能进行操作的人输。
那么，必胜策略是怎么样的呢？首先，我们令最高层为0层，依次为1，2，...，n-1层。那么，结论就是奇数层的石子做nim即可。
为什么这样是可行的呢？解释如下：对于偶数层，2，4，6...等，从这里移动石子，下一个人可以模仿着这动作将这么多的石子移动到下一层，例如，对方移动x个石子从2到1，那么我模仿他将x个石子从1移动到0即可，其他同理。然后我们就发现，其实这一轮操作相当于将x个石子从偶数层移动到偶数层，奇数层的石子都没有改变。所以，对奇数层做nim是成立的。——因为，如果从奇数层拿走任意个到偶数层，由于偶数层的移动是不影响奇数层的，那么奇数层上的石子移动就相当于nim游戏中拿走一堆石子中的若干个。至此，得证。
然后看下下面三题：
1.首先是，bc的B题，hdu5996，很显然只要把奇数层的节点的个数都做nim即可。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 const int N = 100000 + 100; 7 8 int a[N]; 9 vector<int> G[N]; 10 int ans; 11 void dfs(int u,int dep) 12 { 13 if(dep % 2) ans ^= a[u]; 14 for(int i=0;i<G[u].size();i++) 15 { 16 int v = G[u][i]; 17 dfs(v,dep+1); 18 } 19 } 20 21 int main() 22 { 23 int T;scanf("%d",&T); 24 while(T--) 25 { 26 int n;scanf("%d",&n); 27 for(int i=0;i<n;i++) G[i].clear(); 28 for(int i=1;i<n;i++) 29 { 30 int fa;scanf("%d",&fa); 31 G[fa].push_back(i); 32 } 33 for(int i=0;i<n;i++) scanf("%d",a+i); 34 ans = 0; 35 dfs(0,0); 36 puts(ans ? "win" : "lose"); 37 } 38 return 0; 39 }
2.poj1704，一条线段上有若干个棋子，每个棋子都在一个坐标位置上，然后每次轮到操作者时，可以将任何一个棋子，向左移动，但是最左到1或者到前面有棋子了停止。最后不能够操作的算输。问先手能否赢。
我们把间隔当作石子，那么很显然，一个棋子向左边移动以后，这个棋子左边的间隔减少，右边的棋子增加，相当于石子的移动，然后，就理所当然的得到了阶梯博弈的模型。注意最后一个棋子的右边的无限的间隔是当作第0层的，然后题目有个坑点是，一开始给出的棋子坐标并非递增的，需要排序一下。
代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 7 int num[10000+5]; 8 9 int main() 10 { 11 int T;scanf("%d",&T); 12 while(T--) 13 { 14 int n;scanf("%d",&n); 15 for(int i=1;i<=n;i++) scanf("%d",num+i); 16 sort(num+1,num+1+n); 17 vector<int> v; 18 for(int i=1;i<=n;i++) 19 { 20 v.push_back(num[i]-num[i-1]-1); 21 } 22 int sz = v.size(); 23 int ans = 0; 24 for(int i=sz-1;i>=0;i-=2) ans ^= v[i]; 25 puts(ans ? "Georgia will win" : "Bob will win"); 26 } 27 return 0; 28 }
3.hdu3389，有1~n个盒子，每个盒子内都放有若干石子，如果盒子A和盒子B满足，A和B的序号和是3的倍数，且是奇数，那么可以从序号大的那个盒子内取若干石子到序号小的那个盒子里面。
不难发现，1，3，4是没办法往前转移石子的，算其0层，然后打表发现，如果序号%6结果是2，5，0的，那么总是处于奇数层，否则处于偶数层。然后愉快的阶梯博弈即可。
代码如下（包含了打表代码）：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 6 int main() 7 { 8 int kase = 1; 9 int T;scanf("%d",&T); 10 while(T--) 11 { 12 int n;scanf("%d",&n); 13 int ans = 0; 14 for(int i=1;i<=n;i++) 15 { 16 int x;scanf("%d",&x); 17 if(i%6 == 2 || i%6 == 5 || i%6 == 0) ans ^= x; 18 } 19 printf("Case %d: ",kase++); 20 puts(ans ? "Alice" : "Bob"); 21 } 22 return 0; 23 } 24 /* 25 #include <stdio.h> 26 #include <algorithm> 27 #include <string.h> 28 using namespace std; 29 30 int a[100]; 31 32 int main() 33 { 34 memset(a,-1,sizeof(a)); 35 a[1] = a[3] = a[4] = 0; 36 // 1,3,4 37 // %3 = 0-0,1-2 这些是可以互相转移的 38 for(int i=1;i<100;i++) 39 { 40 if(a[i] != -1) continue; 41 int show = 0; 42 int flag = -1; 43 for(int j=1;j<i;j++) 44 { 45 if((i+j)%2==1 && (i+j)%3==0) 46 { 47 if(flag == -1) flag = a[j] % 2; 48 else if(a[j] % 2 != flag) show = 1; 49 } 50 } 51 a[i] = flag + 1; 52 printf("show is %d -- %d -- %d\n",show,i,a[i]); 53 } 54 return 0; 55 } 56 */
阶梯博弈