题解 P1748 【H数】

· · 题解

作为一名实际上已退役的前选手，这是近一段时间里做的第一题，当然要发题解了。

曾经也算有点水平，但现在这种水题都错了半天。

如果打过cf的话应该挺熟悉这种题，Div2的AB题都可能是这类，基本就是构造。

对于本题而言，只需要在之前的所有H数上各乘上2、3、5或7，取未出现的最小值就可以，但很明显，有很多多余的计算。

我们设立4个变量a,b,c,d，初始时都为1，a记录上一个被2乘所得到的H数的序号，b记录上一个被3乘所得到的H数的序号，以此类推，那么H[1]=1，之后的每个H[i]都等于min(a×2,b×3,c×5,d×7)，随时更新a、b、c、d，一重循环即可求出H(n)。

由于本题多组数据，所以很自然地想到在程序开头预处理出10000个H数，之后读入后直接输出对应的H数即可。

说了半天，其实和楼下的方法一样，放上C++代码，或许可供后来者借鉴。

    #include<bits/stdc++.h>
    using namespace std;
    int n,a=1,b=1,c=1,d=1;
    long long w[10090];
    int main(){
        w[1]=1;
        for(int i=2;i<=10000;++i){
            w[i]=w[a]*2;
            if(w[i]>w[b]*3)w[i]=w[b]*3;
            if(w[i]>w[c]*5)w[i]=w[c]*5;
            if(w[i]>w[d]*7)w[i]=w[d]*7;
            if(w[i]==w[a]*2)a++;
            if(w[i]==w[b]*3)b++;
            if(w[i]==w[c]*5)c++;
            if(w[i]==w[d]*7)d++;
        }
        while(scanf("%d",&n)!=EOF)
            cout<<w[n]<<"\n";
        return 0;
}