P4862猜数（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 14k | 阅读时长 ≈ 13 分钟

这里有一篇题解。

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{O(n}^\texttt{2}\texttt{)}$，只能骗来$\texttt{70}$分。

30 point

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
2
3
4
5
6
7
8
9
1-10	1
2-22	2
3-33	3
4-54	5
6-85	8
9-13 6	13
..
..
..

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

Coding.

有SB特判，有注释版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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特判，无注释版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}