1066 Bash游戏 【博弈】

题目链接51nod-1066


题目描述

有一堆石子共有N个。A B两个人轮流拿,A先拿。每次最少拿1颗,最多拿K颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N和K,问最后谁能赢得比赛。
例如N = 3,K = 2。无论A如何拿,B都可以拿到最后1颗石子。


思路

神奇的博弈论,Bash游戏的板子题。石子总数对(最大可取数+1)取模,若最后的结果为0,则后手必胜,否则先手必胜(两面都聪明,取最优策略)

关于博弈论的学习Blog:
1.博弈论及算法实现
2.SG函数和SG定理【详解】

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n, k;
cin >> n >> k;
if(n%(k+1) == 0)
cout<<"B"<<endl;
else
cout<<"A"<<endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------