首页 > 代码库 > 【POJ】2234 Matches Game（博弈论）
【POJ】2234 Matches Game（博弈论）
http://poj.org/problem?id=2234
博弈论真是博大精深orz
首先我们仔细分析很容易分析出来，当只有一堆的时候，先手必胜；两堆并且相同的时候，先手必败，反之必胜。
根据博弈论的知识（论文 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》）
局面可以分解，且结果可以合并。
局面均是先手
当子局面是 胜 和 败，那么局面则为胜
当子局面是 败 和 胜，那么局面则为胜
当子局面是 败 和 败，那么局面则为败
当子局面为 胜 和 胜，那么局面为不确定
而这些性质一一对应二进制的异或运算。
我们设局面表示为S，败的局面就表示为#S=0，胜的局面就表示为#S!=0
设二进制a和b
当a!=0 && b==0时， a^b!=0
当a==0 && b!=0时，b^a!=0
当a==0 && b==0时，a^b=0
当a!=0 && b!=0时，a^b可能=0也可能!=0
而又设函数f(x)=#x #x表示为x的二进制
那么就可以根据上边的运算，合并局面成最终局面
还是看论文吧，，我也不熟，今晚上还要仔细地研究，太博大精深了。orz
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=30;int n;int main() { int ans; while(~scanf("%d", &n)) { ans=0; rep(i, n) ans^=getint(); ans?(puts("Yes")):(puts("No")); } return 0;}
Description
Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.
Input
The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.
Output
For each test case, output "Yes" in a single line, if the player who play first will win, otherwise output "No".
Sample Input
2 45 453 3 6 9
Sample Output
NoYes
Source
POJ Monthly,readchild
【POJ】2234 Matches Game（博弈论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。