luogu P1748题解

H数?Hentai数?
作为一名实际上已退役的前选手,这是近一段时间里做的第一题,当然要发题解了。
曾经也算有点水平(2=水平还好意思说),但现在这种水题都错了半天。
如果打过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数即可。
说了半天,其实是水题。现在我也做不动难题了,咸鱼辣……

原文地址:https://www.cnblogs.com/FaceMoe/p/8205828.html