样例过不了 9pts 求助
查看原帖
样例过不了 9pts 求助
362750
TernaryTree楼主2022/7/18 15:53
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 21;
const int maxd = 21;
const int maxs = 2;

int l, r;
int dp[maxn][maxd][maxd][maxs];
int num[maxn], cnt;

int dfs(int dig, int lala, int la, bool flag, bool lim) {
    // printf("%lld %lld %lld %d %d\n", dig, lala, la, flag, lim);
    if (dig == 0) {
        return flag;
    }
    if (!lim && ~dp[dig][lala][la][flag]) {
        return dp[dig][lala][la][flag];
    }
    int n = (lim ? num[dig] : 9);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += dfs(dig - 1, la, i, (i == lala || i == la) || flag, (i == n));
    }
    if (!lim) {
        dp[dig][lala][la][flag] = ans;
    }
    return ans;
}

int solve(int x) {
    cnt = 0;
    while (x) {
        num[++cnt] = x % 10;
        x /= 10;
    }
    int ans = 0;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i < cnt; i++) {
        for (int j = 1; j < 10; j++) {
            ans += dfs(i - 1, 10, j, 0, 0);
        }
    }
    for (int i = 1; i <= num[cnt]; i++) {
        ans += dfs(cnt - 1, 10, i, 0, i == num[cnt]);
    }
    return ans;
}

signed main() {
    cin >> l >> r;
    cout << (r - l + 1) - (solve(r) - solve(l - 1)) << endl;
    return 0;
}

2022/7/18 15:53
加载中...