自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 22:04:41，当前版本为作者最后更新于2019-09-08 15:45:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P4862猜数（题解）

PS.

讲一下个人对于这道题的心路历程吧。
这道题就是一道硬生生把两道题合并成一道的经典例子。
首先，看到这道题时，没有看到数据范围，然后这道题就被放置了很久。
后来才发现最后几个$\texttt{n}$特别大的测试数据点的$\texttt{a=2}$与$\texttt{b=1}$。
然后，即使$\texttt{a=2}$且$\texttt{b=1}$，我仍然不会做 我就是菜
于是，我想骗一下$\texttt{70}$分的做法，然后想到了递推。
然后，过了很久，又想到去把$\texttt{a=2}$与$\texttt{b=1}$去带入递推式，打表找一下规律。
突然发现答案有关菲波那切数列，就做出来了。
借此我想告诉大家，我也不知道为什么答案是这样的

Solution.

70 point

首先，引进一个感性理解定理：
在m在S中并且S的元素数目不变的前提下，Iris选择的数m以及S的元素对答案是没有影响的。
所以，我们可以设$\texttt{f(n)}$表示在$\texttt{[1,n]}$，问出答案的最优策略花费的金额。

$$\texttt{f(x)}=\left\{\begin{aligned}\texttt{0}\quad\texttt{(x==1)}\\\texttt{min\{max(f(i)+a,f(x-i)+b)\}}\quad\texttt{(x!=1)}\end{aligned}\right. $$

然鹅这个递推式的复杂度是$\texttt{O(n}^\texttt{2}\texttt{)}$，只能骗来$\texttt{70}$分。

30 point

但是，我们把$\texttt{a=2}$和$\texttt{b=1}$带入上式，然后打表找一下规律。
我打出了这个表

1 ans=0
2 ans=2
3 ans=3
4 ans=4
5 ans=4
6 ans=5
7 ans=5
8 ans=5
9 ans=6
10 ans=6
11 ans=6
12 ans=6
13 ans=6
14 ans=7

经过整理后是这样的

1-1  0	1
2-2  2	2
3-3  3	3
4-5  4	5
6-8  5	8
9-13 6	13
.    .
.    .
.    .

我们发现，最右端是斐波那契数列，然后再打一通表，就发现$\texttt{f(100)>10}^\texttt{18}$。
所以复杂度是$\texttt{O(max(100,t))}$，能过。
至此，这道题终于做完了。

Coding.

有SB特判，有注释版本

#include<bits/stdc++.h>		//我爱用万能头
using namespace std;
typedef long long ll;
const int N=2000,M=100;		//N表示前7个点的范围，M表示后3个点的范围
int a,b,t;ll n,f[N+5];
inline void work1()		//处理前7个点。
{
	memset(f,0x3f,sizeof(f)),f[1]=0;	//要求最大值的最小值，初始值INF
	for(int i=1;i<=N;i++)
		for(int j=1;j<i;j++)
			f[i]=min(f[i],max(f[j]+a,f[i-j]+b));	//由上面的递推式得到
	while(t--) scanf("%lld",&n),printf("%lld\n",f[n]);	//回答询问
}
inline void work2()		//处理后3个点。
{
	f[0]=1,f[1]=1;
	for(int i=2;i<=M;i++) f[i]=f[i-1]+f[i-2];	//预处理斐波那契数列
	while(t--)
	{
		scanf("%lld",&n);
		if(n==1) {puts("0");continue;}	//SB特判
		for(int i=1;i<=M;i++) if(n<=f[i]) {printf("%d\n",i);break;}		//打表找出的规律
	}
}
int main()
{
	scanf("%d%d%d",&a,&b,&t);
	if(a!=2||b!=1) work1();		//处理前7个点
	else work2();	//处理后3个点
	return 0;
}

不用SB特判，无注释版本：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000,M=100;
int a,b,t;ll n,f[N+5];
inline void work1()
{
	memset(f,0x3f,sizeof(f)),f[1]=0;
	for(int i=1;i<=N;i++)
		for(int j=1;j<i;j++)
			f[i]=min(f[i],max(f[j]+a,f[i-j]+b));
	while(t--) scanf("%lld",&n),printf("%lld\n",f[n]);
}
inline void work2()
{
	f[0]=1,f[1]=1;
	for(int i=2;i<=M;i++) f[i]=f[i-1]+f[i-2];
	while(t--)
	{
		scanf("%lld",&n);
		for(int i=0;i<=M;i++) if(n<=f[i]) {printf("%d\n",i);break;}
	}
}
int main()
{
	scanf("%d%d%d",&a,&b,&t);
	if(a!=2||b!=1) work1();
	else work2();
	return 0;
}