Training:组合博弈入门

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博客 ,格式可能有所偏差。

支付宝扫码领红包