BZOJ 2275: [Coci2010]HRPA

Description

N个石子，A和B轮流取，A先。每个人每次最少取一个，最多不超过上一个人的个数的2倍。
取到最后一个石子的人胜出，如果A要有必胜策略，第一次他至少要取多少个。(nleqslant 10^{15})

Solution

博弈。

这是一个斐波拉契博弈问题...

其实跟巴什博弈差不多...

根据**定理

根据“Zeckendorf定理”(齐肯多夫定理)：任何正整数可以表示为若干个不连续的(Fibonacci)数之和.

有了这个定理因为你取了一个(Fibonacci)数，另一个人一定取不了下一个的下一个(Fibonacci)数，一定是先手取到。

所以先手只需要取最小的那个(Fibonacci)数即可...

当(n)为(Fibonacci)数时，先手必败。

Code

/**************************************************************
    Problem: 2275
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1288 kb
****************************************************************/
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 88;
 
LL n,k;
LL stk[N],p;
LL f[N];
 
int main() {
    cin>>n;
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]+f[i-2];
//  for(int i=0;i<N;i++) cout<<f[i]<<endl;
    for(int i=N-1;~i;--i) if(f[i]<=n) {
        if(f[i]==n) return printf("%lld
",f[i]);
        k=i;break;
    }
    while(n && k>=0) {
        while(f[k]>n) k--;
        stk[++p]=f[k],n-=f[k],k--;
    }
//  for(int i=1;i<=p;i++) cout<<stk[i]<<endl;
    printf("%lld
",stk[p]);
    return 0;
}

　　

/**************************************************************
    Problem: 2275
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1288 kb
****************************************************************/
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 88;
 
LL n,k;
LL stk[N],p;
LL f[N];
 
int main() {
    cin>>n;
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]+f[i-2];
//  for(int i=0;i<N;i++) cout<<f[i]<<endl;
    for(int i=N-1;~i;--i) if(f[i]<=n) {
        if(f[i]==n) return printf("%lld
",f[i]);
        k=i;break;
    }
    while(n && k>=0) {
        while(f[k]>n) k--;
        stk[++p]=f[k],n-=f[k],k--;
    }
//  for(int i=1;i<=p;i++) cout<<stk[i]<<endl;
    printf("%lld
",stk[p]);
    return 0;
}