题解报告:hdu 2516 取石子游戏(斐波那契博弈)

时间:2023-03-08 16:56:14

Problem Description

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

Input

输入有多组.每组第1行是2<=n<2^31. n=0退出.

Output

先取者负输出"Second win". 先取者胜输出"First win". 参看Sample Output.

Sample Input

2
13
10000

Sample Output

Second win
Second win
First win
解题思路:斐波那契博弈。斐波那契博弈模型,大致上是这样的:有一堆个数为 n 的石子,游戏双方轮流取石子,满足:

1. 先手不能在第一次把所有的石子取完;
2. 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。
约定取走最后一个石子的人为赢家,求必败态。
我们简单举几个栗子:

当n=2时,后手必赢;

当n=3时,后手必赢;

当n=4时,只要先手取1个,剩下3个,无论后手取多少个,先手必赢;

当n=5时,①若先手先取1个,剩下4个,此时后手掌握n=4这种局面,则后手必赢;②若先手取2个,根据规则,后手可以一次性取完剩下的3个,则后手必赢;所以先手无论怎么取,此时后手必赢。

当n=6时,先手只要取1个,先手就掌握了n=5这种局面,即先手必赢;

当n=7时,先手只要取2个,先手就掌握了n=5这种局面,即先手必赢;

当n=8时,①若先手取1个时,后手就掌握了n=7这种局面,即后手必赢;②若先手取2个时,后手就掌握了n=6这种局面,即后手必赢;③若先手取3个,根据规则,后手可以一次性取走剩下的5个,剩下的情况都是后手必赢;所以无论先手怎么取,此时后手必赢。

......

继续推导下去,我们可以发现,只要n满足斐波那契数列2,3,5,8,13......,则后手必赢,否则先手必赢。相关证明看这:斐波那契博弈

由于n在int范围内,且fib[45]刚好超过int范围,所以fib数组长度只需为44即可。
AC代码:
 #include<bits/stdc++.h>
using namespace std;
int main()
{
int n,fib[]={,};bool flag;
for(int i=;i<;++i)//只需枚举44个fib数即可
fib[i]=fib[i-]+fib[i-];
while(cin>>n && n){
flag=false;
for(int i=;i<;++i)
if(fib[i]==n){flag=true;break;}
if(flag)cout<<"Second win"<<endl;//如果满足斐波那契数列,则后手必赢
else cout<<"First win"<<endl;//否则先手必赢
}
return ;
}