P4862猜数（题解）

· · 题解

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