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

superman__ · 2025-09-17 18:47:38 · 题解

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

问题分析

游戏规则简述：

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

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

解题思路

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

解法的核心思想是：

1. 生成所有不超过n的斐波那契数
2. 从最大的斐波那契数开始，不断从n中减去，直到n变为0

3. 最后一次减去的斐波那契数就是答案

   代码

   #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;
   }