P6754 题解

EuphoricStar · 2021-08-04 18:19:18 · 题解

我只会发屑题的题解实锤了

思路

一道非常基础的数位 dp，不知道为什么是紫题。

首先要知道一个非常重要的性质：如果一个字符串不含有长度大于 1 的回文子串，那么这个字符串的每个字符都不会和前两个字符相同。

于是记搜时我们添加两个状态 \text{pre1} 和 \text{pre2}，表示当前数位的前两个数字，往下搜的时候判断一下当前数位是否不等于 \text{pre1} 和 \text{pre2}。初始时设 \text{pre1} 和 \text{pre2} 为 -1，表示没有前两位。注意判断状态是否访问过时 \text{pre1} 和 \text{pre2} 要 +1，否则 -1 可能会越界。还有一点要注意：\text{pre1} 转移时，如果当前数位为前导零，则要设为 -1 而不是 0，否则会 WA 78pts。

之后就是套模板了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll l, r, f[25][15][15], a[25];

ll dfs(ll pos, bool limit, bool lead, ll pre1, ll pre2) {
    if (!pos) {
        return 1;
    }
    ll ans = 0;
    if (!limit && !lead && f[pos][pre1 + 1][pre2 + 1] != -1) {
        return f[pos][pre1 + 1][pre2 + 1];
    }
    ll up = limit ? a[pos] : 9;
    for (ll i = 0; i <= up; ++i) {
        if (i != pre1 && i != pre2) {
            ans += dfs(pos - 1, limit && i == up, lead && !i, (!lead || i) ? i : -1, pre1);
        }
    }
    if (!limit && !lead) {
        f[pos][pre1 + 1][pre2 + 1] = ans;
    }
    return ans;
}

ll solve(ll x) {
    ll cnt = 0;
    while (x) {
        a[++cnt] = x % 10;
        x /= 10;
    }
    memset(f, -1, sizeof(f));
    return dfs(cnt, 1, 1, -1, -1);
}

int main() {
    scanf("%lld%lld", &l, &r);
    printf("%lld", solve(r) - solve(l - 1));
    return 0;
}