自动搬运

查看原文

来自洛谷，原作者为

	yingxi 没咋 || 最后在线时间：2025年8月21日10时55分

搬运于2025-08-24 23:12:20，当前版本为作者最后更新于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)$

不会超时哒