0分求助
查看原帖
0分求助
578809
hyc12528楼主2022/12/17 14:14
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

const int SIZE = 1 << 14;
inline char getc() {
    static char buf[SIZE], *begin = buf, *end = buf;
    if (begin == end) {
        begin = buf;
        end = buf + fread(buf, 1, SIZE, stdin);
    }
    return *begin++;
}

inline int read() {
    register int ret = 0, sgn = 0;
    static char ch = getchar();
    while (!isdigit(ch)) {
        sgn |= ch == '-', ch = getchar();
    }
    while (isdigit(ch)) {
        ret = ret * 10 + ch - '0', ch = getchar();
    }
    return sgn ? -ret : ret;
}

long long bound[20], dp[20][20], big;

int dfs(long long pos, long long num, long long flag) {
    if (pos == 0) {
        return 1;
    }
    long long maxx = 9;
    if (!flag && dp[pos][num] != -1) {
        return dp[pos][num];
    }
    if (flag) {
        maxx = bound[pos - 1];
    }
    long long ret = 0;
    for (long long i = 0; i <= maxx; i++) {
        if (((abs(i - num) >= 2 || (num == 0 && pos == big))) && !((num == 0 && pos == big) && i == 0)) {
            ret += dfs(pos - 1, i, flag && (i == bound[pos]));
        }
    }
    if (!flag) {
        dp[pos][num] = ret;
    }
    return ret;
}

int main() {
    long long a = read(), b = read();
    a--;
    for (int i = 0; i <= 19; i++) {
        for (int j = 0; j <= 19; j++) {
            dp[i][j] = -1;
        }
    }
    long long ans1 = 0, ans2 = 0, op = 0;
    for (big = 0; b; big++) {
        bound[big] = b % 10;
        op = b;
        b /= 10;
    }
    big--;
    for (int j = 0; j <= op; j++) {
        ans1 += dfs(big, j, j == op);
    }

    for (big = 0; a; big++) {
        bound[big] = a % 10;
        op = a;
        a /= 10;
    }
    big--;
    for (int j = 0; j <= op; j++) {
        ans2 += dfs(big, j, j == op);
    }
    printf("%lld", ans1 - ans2);
    return 0;
}

记录

2022/12/17 14:14
加载中...