题解 P1660 【数位平方和】

2018-09-22 14:58:20


题解好少qwq

仔细看题。

发现 $S(i)$ 可以在常数时间内求出。预处理出 $s[1]$ ~ $s[9]$ 会跑的更快。

然后将 $H(n)$ 展开,发现 $H(n)=min\{n,S(n),S(S(n)),S(S(S(n))),...\}$ 。

然后就可以递归搞,但是边界不好找。

仔细一想,发现这个东西会出现环。

那么在一个数访问两次时,说明成环了,直接返回即可。

然后再加上记忆化,即可AC本题。

代码见蒟蒻的blog