【Game】

【问题描述】

YJQ和它的主人正在玩一个游戏:

两个人从1轮流开始报数:

如果遇到7的倍数或者遇到的这个数的十进制表示中含7,则遇到的那个人需要喊“过”。

例如:1 2 3 4 5 6 过 8 9 10 11 12 13 过 15 16 过 18……

游戏过后,它的主人提出了一个问题:

在区间[L,R]里有多少个数要喊“过”

小YJQ智商不够,请你帮它解决这个问题。

【输入格式】

第一行一个整数N,表示共有N组数据。

接下来N行,每行两个整数L和R,表示区间[L,R]

【输出格式】

共N行,每行一个整数。分别表示每一组数据的答案。

【输入样例】

3

5 10

7 30

2 100

【输出样例】

1

6

30

【数据范围】

对40%的输入数据:N≤30,L,R≤10^6

对70%的输入数据:N≤300, L,R≤10^9

对100%的输入数据:N≤3000,L,R≤10^18

40%的数据直接预处理打表即可。

70%的数据YYY神犇迷之滚动打表每隔30000打一次用sqrt(30000)的复杂度完成了?(YYY Orz)

100%的数据考虑数位DP

先处理出7的倍数有多少,再用数位DP处理不是7的倍数但含7的数有多少。

用dp[i][j][p][q]来表示考虑到了第i为第i位选了某个数之后余数为j,之前是否出现过7(p=0没有,p=1有),是否选到了当前数的上限(0没有,1有)的数有多少。

于是对于每一位只用考虑前一位是否选到了限制或者没有,上一位选的余数,这一位选哪个数即可。

实际上对于出现7有两个情况,其中p=1是用p=1来转移,当选的当前数为7时不管p=0或者1都可以转移。

最后计算dp[cnt][1~6][1][0]+dp[cnt][1~6][1][1]即为所求数大小,累加进答案即可。

(其实是看GJY神犇代码懂的)

下面是代码:

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*