题干1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出Se 题干 1堆石子有n个,两人轮流取.先取
题干
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2 Output 先取者负输出"Second win". 先取者胜输出"First win". 参看Sample Output. Sample Input 213100000 Sample Output Second winSecond winFirst win 解题报告 关于Fibonacci博弈的证明这里用的是数学归纳法 斐波那契博弈Fibonacci Nim 结论就是如果这个数是Fibonacci数则先手败后手胜。 代码很简单至于为什么二分比暴力枚举慢我就不知道了。一个15ms一个0ms。 AC代码 #includeusing namespace std;int f[46];int main(){int n;f[1]1;f[2]2;for(int i 3; i<45; i) {f[i] f[i-1] f[i-2];}while(~scanf("%d",1,f461,n) 1) puts("Second win");else puts("First win");}return 0 ;}