本文从WordPress迁移而来, 查看全部WordPress迁移文章
DFS DP
题意:略
- 序列的增长是指数级别的,所以不能模拟
从整体考虑这个问题,例如一开始给出385,经过m轮后,得到一个很长的序列,但是这个序列可以分为3块,第1块,2块,3块分别是3,5,8经过m轮后变成的。如果要查找的字符在第1块,那么就可以不去考虑5,8,只考虑3
例如3下一次变化得到479,那么就是说479经过m-1的变化和3经过m轮是一样的,那么由3变成的1块,可以看做有479变成的3块,所以可以再次定位是在这3块中的哪一块。以此类推,一直定位下去
可以留意到,我们需要一个信息,就是单个字符,经过m轮变化后,得到一个很长的序列,我们没必要知道序列的具体样子,但是我们要知道长度,这个信息,用一个dp预处理出来就行了
dp[n][m]表示单个数字n经过m轮变化后得到的序列长度
1 |
|