F - 取石子游戏 HDU - 2516(斐波那契博弈+证明)_综合

分析

题意

有一堆 N 个石子，两个人轮流取石子，每个最少取一个石子，最多取任意个石子，
规定第一个人在第一次取得时候，不能把 N 个石子全部取完。
问先手是否获胜

思路

结论：
当 N == 1 时，先手必败
当 N != 1 时，如果 n 为斐波那契数，先手必败，否则必胜

结论证明

斐波那契数： $1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 。。。$

首先结论的证明是建立在一个定理上：任何一个不是斐波那契数的数字都可以写为，许多个不相邻的斐波那契的数字的和，如：7 = 5 + 2、27 = 21 + 5 + 1（注意：这里的数字的分解要要尽量往接近当前数字且比当前数字小的斐波那契数上分解）
2. 我们考如如果如果 N 是某个斐波那契数 f [n] 的时候，此时拆分 f [n] = f [n - 1] + f [n - 2], 此时我们可以将一堆 n 个大石子堆，看出两小堆石子 f [n-1]、 f [n - 2]
1. 如果先手第一个去走的石子的数量大于 f [n - 2], 那么后手可以直接将剩下的石子取完，
2. 如果先手第一次去走的石子的数量 y >= 1/3 * f [n - 2] 那么后手可以直接将 f [n - 2] 这一小堆的剩下的石子直接去玩，剩下的石子的数量为：x = f [n - 2] - y <= 2/3 * f [n - 2], 此时我们观察 2/3f [n-2] 与 1/2f [n - 1] 的数量关系化简 -> 4*f [n - 2] 与 3 * f [n - 1] , 由数学归纳的得，后置更大，
3. 所以此后先手无法一次取完 f [k - 1] 小堆中的石子，此时双方继续进行取石子的时候，取石子的规则不变，所以后手一定可以取完最后一课石子，
4. 当 n 为斐波那契数的时候，所以后手必胜
如果 n 不是斐波那契数，那么我们可以将 n 分解成由若干个不相邻的斐波那契额数加，n = f [a1] + f [a2] + f [a3] + … + f [ap], 因为分解的数不连续，所以易得 $f[a_x]=f[a_{x-1} + f[a_{x-2}]>2*f[a_{x-1}]$
1. 如果此时先手直接将 f [ap] 直接取完，那么因为 f [ap-1] > 2*f [ap], 所以后手无法取完 f [ap-1] 这个子堆中石子，那么后有永远面面对的就是 f [ap-1] 这个必败态（为什么 f [ap-1] 是必败态，这里我们引用了 ?上面之前证明的结论 “n 为斐波那契数的一堆石子，那么这堆石子就是必败态”），
2. 所以 n 不是斐波那契的时候，先手必胜，

参考链接

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <bitset>
#include <vector>
#include <stack>
#include <map>
/* #include <unordered_map> */
#include <sstream>
void fre() {
     system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() {
     system("clear"), freopen("A.txt", "r", stdin);}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define db double
#define ll long long
#define ull unsigned long long
#define Pir pair<int, int>
#define m_p make_pair
#define INF 0x3f3f3f3f
#define esp 1e-7
#define mod (ll)(1e9 + 7)
#define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
#define sc scanf
#define pr printf
#define sd(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
using namespace std;const int mxn = 1e5;
ll ar[mxn];int main()
{
    /* fre(); */ar[1] = 1, ar[2] = 1;for_(i, 3, 50)ar[i] = ar[i - 1] + ar[i - 2];int n; while(~ sd(n) && n){
    int idx = lower_bound(ar, ar + 50, n) - ar;if(ar[idx] == n)pr("Second win\n");elsepr("First win\n");}return 0;
}