LibreOJ 2683 「BalticOI 2013」非回文数

发表于 | 分类于 |

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

显然只要没有长度为 \(2,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));
}