HDU 1846：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11241
给出 n 个物品，两个人轮流取，每次取1～ m 个，不能取的人负，输出胜利者。
巴什博弈，当 n % ( m + 1 ) = 0 时后手胜利，否则先手胜利。
1
2
3
4
5
6
7
8
9
| #include<cstdio>
int main(){
int t;scanf("%d",&t);
while(t--){
int n,m;scanf("%d%d",&n,&m);
puts(n%(m+1)?"first":"second");
}
return 0;
}
|
HDU 1847：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20980
给出 n 个物品，两个人轮流取，每次只能取2的倍数个。
巴什博弈，第一个先手的人只要能构造出3的倍数就可以必胜。对三取余判断输出结果。
1
2
3
4
5
6
7
| #include<cstdio>
int main(){
int n;
while(~scanf("%d",&n))
puts(n%3?"Kiki":"Cici");
return 0;
}
|
HDU 1848：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22378
给出三堆牌，每次去的个数只能是菲波那契数，问谁能赢。
看了解题报告才知道这是运用SG函数的尼姆博弈，去现学的，对每个输入的值求SG函数值，然后进行异或求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<cstdio>
#include<cstring>
const int maxn=1010;
int f[20]={1,1},sg[maxn];
bool h[maxn][20];
void pre(){
for(int i=2;i<20;++i) f[i]=f[i-1]+f[i-2];
memset(sg,-1,sizeof(sg));
return;
}
int Sg(int n){
int& k=sg[n];
if(k!=-1) return k;
for(int i=1;i<20;++i)
if(n-f[i]>=0) h[n][Sg(n-f[i])]=true;
k=0;
while(h[n][k]) ++k;
return k;
}
int main(){
pre();
int n,m,p;
while(~scanf("%d%d%d",&n,&m,&p)&&!(!n&&!m&&!p))
puts(Sg(n)^Sg(m)^Sg(p)?"Fibo":"Nacci");
return 0;
}
|
HDU 1849：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=10636
可以抽象成给出 n 堆牌，每次可以取一张或者全取走，问谁胜。
比上一题简单的尼姆博弈，对输入的数进行异或输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<cstdio>
int main(){
int n;
while(~scanf("%d",&n)&&n){
int ans=0,k;
while(n--){
scanf("%d",&k);
ans^=k;
}
puts(ans?"Rabbit Win!":"Grass Win!");
}
return 0;
}
|
HDU 1850：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22381
给出多堆牌，每次可以任选一堆取走任意数量，问先手第一步有多少必胜取法。
首先异或判断是否存在必胜策略求的异或后的值为 a n s 。判断当前堆中有没有足够的牌，使得取走之后 a n s ＝ 0 ，若有则方案数加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<cstdio>
int a[110],n;
int main(){
while(~scanf("%d",&n)&&n){
int ans=0,cnt=0;
for(int i=0;i<n;++i) scanf("%d",&a[i]),ans^=a[i];
if(!ans){puts("0");continue;}
for(int i=0;i<n;++i)
if(a[i]>(ans^a[i])) ++cnt;
printf("%d\n",cnt);
}
return 0;
}
|
HDU 2149：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=10637
输入土地成本 m 和每次加价最大值 n ，当出价高于或等于成本时得到该土地，输出先手必胜策略。
巴什博弈，首先判断是否存在必胜策略，然后枚举输出可行出价。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<cstdio>
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
if(n%(m+1)==0){puts("none");continue;}
bool first=true;
if(n<m){
for(int i=n;i<=m;++i){
printf("%d%c",i,i!=m?' ':'\n');
}
continue;
}
for(int i=1;i<=m;++i){
if((n-i)%(m+1)==0){
if(first) first=false;
else printf(" ");
printf("%d",i);
}
}
puts("");
}
return 0;
}
|
HDU 2188：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=26664
巴什博弈，和第一道题一样。
1
2
3
4
5
6
7
8
9
| #include<cstdio>
int main(){
int t,n,m;scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
puts(n%(m+1)?"Grass":"Rabbit");
}
return 0;
}
|
HDU 2147：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=26673
给出目标点的坐标，从原点出发，每次可以向左、向下或者向左下，问谁能赢。
当横纵坐标存在偶数时，先手赢。
1
2
3
4
5
6
7
| #include<cstdio>
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)&&!(!n&&!m))
puts(n&1&&m&1?"What a pity!":"Wonderful!");
return 0;
}
|
HDU 1079：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11243
改变月份或移到后一天会改变月份与日期和的奇偶性，除了两个特殊日期9月30日和11月30日。对特殊日期进行特判，其他情况只要判断奇偶性就可以知道。
这题还可以用SG函数做。
1
2
3
4
5
6
7
| #include<cstdio>
int main(){
int t,y,m,d;scanf("%d",&t);
while(t--&&~scanf("%d%d%d",&y,&m,&d))
puts((m+d)%2==0||((m==9||m==11)&&d==30)?"YES":"NO");
return 0;
}
|
HDU 1517：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=13014
看了题解才会的，类似于巴什博弈，每一段必胜区间都紧跟着一段必败区间，必胜区间对 n 不断除18之后的余数小于9。
这道题也可以用SG函数做。
1
2
3
4
5
6
7
8
9
| #include<cstdio>
int main(){
double n;
while(~scanf("%lf",&n)){
while(n>18) n/=18;
puts(n>9?"Ollie wins.":"Stan wins.");
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **