题解：P6487 [COCI 2010/2011 #4] HRPA

这道题目是一个经典的博弈论问题，需要找出Mirko第一次至少取多少石子才能保证获胜。

问题分析

游戏规则简述：

两位玩家轮流取石子,Mirko先行
Mirko第一次可以取任意数量的石子
之后每次取石子的数量必须在1到上一次取的数量的2倍之间
取走最后一颗石子的玩家获胜

我们需要找到Mirko第一次最少取多少石子才能确保胜利，假设双方都采用最优策略。

解题思路

这个问题的关键是发现它与斐波那契数列的紧密联系。通过分析可以发现，当石子数量是某个斐波那契数时，后行者有必胜策略；而当石子数量不是斐波那契数时，先行者有必胜策略。

解法的核心思想是：

生成所有不超过 $n$ 的斐波那契数
从最大的斐波那契数开始，不断从 $n$ 中减去，直到 $n$ 变为0
最后一次减去的斐波那契数就是答案

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    long long n;
    cin >> n;
    // 生成斐波那契数列，直到超过n
    vector<long long> fib;
    fib.push_back(1);
    fib.push_back(1);
    while(fib.back() < n)
    {
        int size = fib.size();
        fib.push_back(fib[size-1] + fib[size-2]);
    }
    long long ans = n;
    // 不断减去最大可能的斐波那契数
    while(n) 
	 {
        for(int i = fib.size() - 1; i >= 0; i--) 
		{
            if (fib[i] <= n) 
			{
                ans = fib[i];
                n -= fib[i];
                break;
            }
        }
        if (n == 0) break;
        // 移除数列中大于当前n的数
        while(fib.back() > n) 
		{
            fib.pop_back();
        }
    }
    
    cout << ans << endl;
    return 0;
}

题解：P6487 [COCI 2010/2011 #4] HRPA

文章操作

问题分析

解题思路

代码

相关推荐

评论

题解：P6487 [COCI 2010/2011 #4] HRPA