2018年全国多校算法寒假训练营练习比赛 G 送分啦-QAQ【斐波那契博弈】

链接：https://www.nowcoder.com/acm/contest/77/G
来源：牛客网

题目描述
幼儿园开学了，为了让小盆友们能尽可能的多的享受假期。校长大人决定让小盆友分批到校，至于每批学生来多少人由一个小*和一个小仙女负责，两个人轮番负责，校长会在最后的时候去查看工作进度，小*不想被别人嘲笑自己傻，小仙女要证明自己比小*聪明。所以她们回去争抢安排最后一名小盆友。每次安排的小盆友至少为1，至多为上一次安排的2倍。小仙女抢到了先手的机会。第一次安排小盆友不能直接安排所有的小盆友一起回校。
输入描述:

单组测试数据
输入一个整数n——n代表小盆的个数（n>=2&&n<=1e9)

输出描述:

输出获胜人的名字——“Xian”或者“Sha”

示例1
输入

输出

Sha

说明

（Fisrt）1 -> (Second) 2 || 2 - > 1 无论小仙女先送一个还是两个都会被小*获胜

示例2
输入

输出

Xian

说明

1 -> 2 -> 1 || 1 -> 1 -> 2 小仙女先送一个，小*无论送一个或者两个都会被小仙女取胜。

题目分析：一开始不知道是斐波那契博弈，自己写了几个递推关系，就是没有想到得到的数列是斐波那契数列。
下面写一下证明过程

根j据数学归纳法
当i=2时,先手只能送1个，先手必败
假设当i<=k时成立，

i=k+1时 f[i]=f[k]+f[k-1]，此时对于先手来说，如果先送的孩子的个数大于等于f[k-1]时，由于f[k] $<$ f[k-1]*2此时后手必然可以全部送完，先手就会失败，所以，先手先送的个数必然小于f[k-1]，根据假设可知，此时无论先手送多少个，后手必能送完f[k-1]这些孩子。此时我们来分析一下后手最后送的孩子的个数x;

假设先手送的孩子个数 $y > \frac{1}{3}$ f[k-1] ,那么后手可以一次送完 k-1这一群孩子，x=f[k-1]-y;
即 x $\leq \frac{2}{3}$ f[k-1]

由于 $\frac{2}{3}$ f[k-1] $- \frac{1}{2}$ f[k]即3f[k-1] $-$ 4f[k] $= -$ 3f[k-2] $-$ f[k] $< 0$

所以x $< \frac{1}{2}$ f[k]

因此，此时先手无法送完f[k]个小朋友，根据假设，无论先手如何送，后手定能送完最后一个小朋友，因此 i=k+1时成立

若先手一开始送的小朋友的个数y $\leq \frac{1}{3}$ f[k-1],那么后手如果要送走最后一个小朋友，最后一次送的孩子的个数x一定小于之前的x，因此结论显然成立；

所以当i是斐波那契数的时候，后手胜

当i不是斐波那契数列的时候呢，根据齐肯多夫定理，任何正整数都可以表示位若干个不连续的Fibonacci数之和，分解时对于每一个数，我们尽量取大的Fibonacci数

例如 17 介于 13和21之间 17=13+4 ，4介于3和5之间 17=13+3+1；

这样对于一个数n
n=f[a1]+f[a2]+…+f[ap] ( $a 1 > a 2 > a 3 > \dots > a p$ )

我们让先手先送完f[ap]，由于n不是斐波那契数，所以每个F都不连续， $a (p - 1) > a p + 1$
即 f[ap-1] $>$ 2f[ap]

因此后手只能送f[ap-1]这群小朋友中的一部分，根据之前的定理，先手能送完这一群
同理可知，这种情况下先手必胜

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
typedef long long ll;
ll f[maxn];
int main()
{
    f[1]=1;
    f[2]=1;

for(int i=3;i<=50;i++)
    {
        f[i]=f[i-1]+f[i-2];
    }
int n;
cin>>n;
for(int i=1;i<=50;i++)
    {
if(f[i]==n)
        {
puts("Sha");
return 0;
        }
    }
puts("Xian");
return 0;
}

秒客网

2018年全国多校算法寒假训练营练习比赛 G 送分啦-QAQ【斐波那契博弈】

相关文章