题意

求区间 \([L,R]\) 内满足相邻两位的差 \(\ge 2\) 的数的个数。

分析

这道题目的前导 \(0\) 有点难处理。

\(f[i][j][k][m]\) 表示处理到第 \(i\) 位,第 \(i\) 位上的数为 \(j\) ,\(k=0/1\) 前 \(i\) 位是否于上限一致,\(m=0/1\) 是否有前导 \(0\) 。

直接转移可以得到区间 \([1,x]\) 的总数,查分并检验下限是否满足要求即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注