HDU 4764 Stone (巴什博弈)

时间:2023-04-05 14:22:44

题意

Tang和Jiang玩石子游戏,给定n个石子,每次取[1,k]个石子,最先取完的人失败,Tang先取,问谁是赢家。

思路

比赛的时候想了不久,还WA了一次= =……后来看题解才发现是经典的巴什博弈,博弈什么的什么都不会= =……

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

分析:显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

结论】n % (m+1) == 0,后手必胜;否则先手必胜。

变形】如果规定最后取光者输,结果如何?(n-1)%(m+1) == 0,后手必胜。

分析:先手会重新决定策略,所以不是简单的相反行的。我们这样想:如果保证最后给先手只留一个,那么后手就能必胜了。问题就化为取n-1个的子问题,而最后是后手取走的,所以对应的是巴什博弈后手必胜即(n-1) % (m+1) == 0的情况。

代码

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#define MID(x,y) ((x+y)/2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define REP(i, begin, end) for (int i = begin; i <= end; i ++)
using namespace std;

int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int n, k;
while(scanf("%d %d", &n, &k) != EOF){
if (n + k == 0) break;
if ((n-1) % (k+1) == 0){
puts("Jiang");
}
else{
puts("Tang");
}
}
return 0;
}
[/cpp]