BZOJ2275[Coci2010]HRPA——斐波那契博弈-白红宇

BZOJ2275[Coci2010]HRPA——斐波那契博弈

阅读量：7017 次

发布时间：2019-06-28

本文共 870 字，大约阅读时间需要 2 分钟。

题目描述

N个石子，A和B轮流取，A先。每个人每次最少取一个，最多不超过上一个人的个数的2倍。

取到最后一个石子的人胜出，如果A要有必胜策略，第一次他至少要取多少个。

输入

第一行给出数字N，N<=10^15.第二行N个数字

输出

如题

样例输入

样例输出

根据齐肯多夫定理，任何一个正整数都能由若干个不连续的斐波那契数表示。

那么这个博弈就可以分成若干个斐波那契博弈(斐波那契博弈详见)。

A只要第一次取走n被表示的最小斐波那契数，那么B就变成了先手、A变成了后手。

这时B无法取到下一个最小的斐波那契数(因为表示这个数的斐波那契数不连续且后手不能取超过先手的二倍)。

所以对于剩下的每个斐波那契数都是B先取且最后一个一定被A取到。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define ll long longusing namespace std;ll f[100];int cnt;ll n;int main(){ scanf("%lld",&n); f[1]=1; f[0]=1; cnt=2; while(1) { f[cnt]=f[cnt-1]+f[cnt-2]; if(f[cnt]>=n) { break; } cnt++; } for(int i=cnt;i>=1;i--) { if(n==f[i]) { printf("%lld",n); return 0; } if(n>f[i]) { n-=f[i]; } }}