LibreOJ 2683.「BalticOI 2013」非回文数

这不和萌数那题一样的吗……

显然只要没有长度为 2,32,3 的回文子串就可以了,数位 DP 记录上一位和上上位和这两位是否为前导零。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 18;
long long l,r;
int d[LEN + 5],tot;
long long f[LEN + 5][10][10][2][2];
long long dfs(int x,int num,int pre,int lead,int prelead,int top)
{
if(!x)
return 1;
if(!top && ~f[x][num][pre][lead][prelead])
return f[x][num][pre][lead][prelead];
long long ret = 0;
int bound = top ? d[x] : 9;
for(register int i = 0;i <= bound;++i)
if((lead || i != num) && (prelead || i != pre))
ret += dfs(x - 1,i,num,lead && !i,lead,top && i == bound);
if(!top)
f[x][num][pre][lead][prelead] = ret;
return ret;
}
long long solve(long long n)
{
tot = 0;
for(;n;n /= 10)
d[++tot] = n % 10;
return dfs(tot,0,0,1,1,1);
}
int main()
{
memset(f,-1,sizeof f);
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r) - solve(l - 1));
}