题解：P12036 [USTCPC 2025] 摩拉

yingxi · 2025-04-06 14:30:43 · 题解

题面传送门

分析题目

这道题目描述了一个特殊的赚钱序列：

• 第一天赚 p 摩拉
• 第二天赚 p+1 摩拉
• 从第三天开始，每天赚的钱是前两天赚的钱之和

给定第 a 天赚的钱 x ，问第 b 天能赚多少钱。如果不存在这样的 p ，使得第 a 天赚 x 摩拉，则输出 -1 。

解题思路

序列生成规则：这个序列类似于斐波那契数列，但是前两项是 p 和 p+1 。我们可以预计算所有可能的 a 和 b 组合对应的关系。

推导：对于第 n 天赚的钱，可以表示为关于 p 的式子：f(n) = k[n] * p + c[n]

• f(1) = p = 1 * p + 0
• f(2) = p + 1 = 1 * p + 1
• f(3) = f(1) + f(2) = 2 * p + 1
• f(4) = f(2) + f(3) = 3 * p + 2
• f(5) = f(3) + f(4) = 5 * p + 3

可以看出系数 k 和 c 都遵循斐波那契数列的规律

预处理系数：我们可以预先计算出对于每个 a 和 b ，对应的 k 和 c 系数，这样在处理查询时可以快速计算。

解方程求 p ：对于给定的 a 和 x ，我们有方程 k[a] * p + c[a] = x。需要解这个方程得到整数 p 且在 1 ≤ p ≤ 10^6 范围内。

验证并计算答案：如果找到合法的 p ，就用这个 p 计算第 b 天的值；否则返回 -1 。

知道了这些，我们就可以开始敲代码了！

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> k(21), c(21);
signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // 预计算系数 k 和c
    k[1] = 1;
    k[2] = 1;
    c[1] = 0;
    c[2] = 1;
    for (int i = 3; i <= 20; i++)
    {
        k[i] = k[i-1] + k[i-2];
        c[i] = c[i-1] + c[i-2];
    }
    int T;
    cin >> T;
    while (T--)
    {
        int a, b, x;
        cin >> a >> x >> b;
        // 解方程 k[a] * p + c[a] = x
        int num1 = x - c[a];
        int num2 = k[a];
        if (num1 <= 0 || num2 == 0)
        {
            cout << "-1\n";
            continue;
        }
        if (num1 % num2 != 0)
        {
            cout << "-1\n";
            continue;
        }
        int p = num1 / num2;
        if (p < 1 || p > 1000000)
        {
            cout << "-1\n";
            continue;
        }
        // 计算第 b 天的值
        int res = k[b] * p + c[b];
        cout << res << '\n';
    }
    return 0;
}

时间复杂度：

1. 预处理 O(20)
2. 每个查询 O(1) ， T 次就是 O(T) 所以总复杂度 O(20*T) ，省略常数就是 O(T)

不会超时哒