夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
Luogu P3413 SAC#1 – 萌数 题解

Describe

题目链接

定义“萌数”: 存在长度至少为$2$的回文子串。

问$[L,R]$中共有多少个萌数字?

对于$100\%$的数据$0\leq L\leq R \leq {10}^{1000}$。

Solution

数位$dp$裸题。

$$DFS(x,las,lasqr,has,lim,st)$$

分别表示第$x$位,上一个数字是$las$,再上一个数字是$lasqr$,是否到达上限$lim$,是否前导$0$。

萌数一定是形如$11$或$101$式的,所以只要判断$las==i||lasqr==i$即可。

注意$L,R$都需要高精

Code

暂无评论

发送评论 编辑评论


				
上一篇
下一篇