技术教程 编程教程 博弈论练习8 Northcott Game（取石子问题） 正文

博弈论练习8 Northcott Game（取石子问题）

2023-03-18,,

题目链接在这里：I-Northcott Game_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题 (nowcoder.com)

这题是一个伪装的很好的取石子问题，可以发现，一个棋子往边上移动是没有用的，因为这一行另一个棋子可以朝同一方向移动相同数的格子，可以发现，如果所有的棋子都相邻了，这种情况下的先手一定是必败态。所以胜负与同一行棋子之间间隔的个数有关，于是就可以发现这是一个最经典的取石子问题了。

把每一行抽象成一堆石子，石子的个数为两个棋子之间的间隔空格数（这里注意是两者列的差的绝对值要再减一个1），然后异或和一下就行了。

 1 #include "bits/stdc++.h"

 2 using namespace std;

 3 const int MAX=1005;

 4 int n,m,a[MAX];

 5 int main(){

 6     int i,j,x,y,an=0;

 7     scanf("%d%d",&n,&m);

 8     for (i=1;i<=n;i++){

 9         scanf("%d%d",&x,&y);

10         a[i]=abs(x-y)-1;

11         an^=a[i];

12     }

13     if (an!=0) cout<<"I WIN!";

14     else cout<<"BAD LUCK!";

15     return 0;

16 }

博弈论练习8 Northcott Game（取石子问题）的相关教程结束。

《博弈论练习8 Northcott Game（取石子问题）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!