hdu 1851 A Simple Game 博弈论

时间:2023-11-28 14:34:14

简单博弈问题(巴什博弈-Bash Game)

巴什博弈:只有一堆n个物品,两个人轮流从这对物品中取物,规定每次至少取一个,最多取m个,最后取光着得胜。

很容易想到当n%(m+1)!=0时,先取者必胜,第一次先拿走n%(m+1)个,以后每个回合都保持两人拿走的物品总和为m+1即可。

这个游戏还可以有一种变相的玩法:两个人轮流报数,每次至少报一个,最多报10个,谁能报到100者胜。

此题可以把每堆石头的取法看作是一个BashGame,这样只需将每组石头按照BashGame的取法判断,然后将n堆石头做异或,

如果异或的结果不为0,则老师获胜,否则Agrael取胜。

代码如下:

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int main(){
int t,m,s,c,ans;
cin>>t;
while(t--){
cin>>m;
ans=;
for(int i=;i<m;i++){
scanf("%d%d",&s,&c);
ans^=s%(c+);
}
puts(ans!=?"No":"Yes");
}
return ;
}