数位DP

数位DP用于处理一些与数位有关的问题，主要是计数问题。

P2657 [SCOI2009] windy 数

题目描述

不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 a 和 b。

int A[10];
int dp[10][100];

///
/// \param pos 当前位置
/// \param last 上一个位置的数的值
/// \param limit 当前位置的数是否可以任取
/// \param lead 当前位置之前全是0
/// \return
int dfs(int pos, int last, bool limit, bool lead) {
    if (pos <= 0) return 1; // 搜索终点
    if (!limit and last != -3 and dp[pos][last] != -1)
        return dp[pos][last];

    int ans = 0;
    for (int v = 0; v <= (limit ? A[pos] : 9); ++v) {
        // 根据是否limit决定循环上界
        if (abs(v - last) < 2) // 舍弃不合法解
            continue;
        if (lead and v == 0)ans += dfs(pos - 1, -3, limit && v == A[pos], true);
        // 当前位和前面都是0，后面的数可以任取，last赋为-3
        else ans += dfs(pos - 1, v, limit && v == A[pos], false);
    }

    if (!limit) dp[pos][last] = ans;
    return ans;
}


int solve(int x) {
    memset(A, 0, sizeof(A));
    memset(dp, -1, sizeof(dp));
    int pos = 0;
    while (x) {
        A[++pos] = x % 10;
        x /= 10;
    }
    return dfs(pos, -3, true, true);
}

signed main() {
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

//    cin >> t;

//    while (t--) {
//        solve();
//    }
    cin >> n >> m;

    print(solve(m) - solve(n - 1));
}

更一般的模板：

int A[10];
int dp[10][15][2][2];

///
/// \param pos 当前位置
/// \param last 上一个位置的数的值
/// \param limit 当前位置的数是否可以任取
/// \param lead 当前位置之前全是0
/// \return
int dfs(int pos, int last, bool limit, bool lead) {
    if (pos <= 0) return 1; // 搜索终点
    if (dp[pos][last][limit][lead] != -1)
        return dp[pos][last][limit][lead];

    int ans = 0;

    int _limit = limit ? A[pos] : 9; // 根据是否limit决定循环上界
    for (int v = 0; v <= _limit; ++v) {
        if (abs(v - last) < 2 and not lead) // 舍弃不合法解
            continue;
        ans += dfs(pos - 1, v, limit && (v == A[pos]), lead and (v == 0));
    }
    dp[pos][last][limit][lead] = ans;
    return ans;
}


int solve(int x) {
    memset(A, 0, sizeof(A));
    memset(dp, -1, sizeof(dp));
    int pos = 0, ans = 0;
    while (x) {
        A[++pos] = x % 10;
        x /= 10;
    }

    for (int i = 0; i <= A[pos]; i++) {
        ans += dfs(pos - 1, i, i == A[pos], i == 0);
    }
    return ans;
}

CF1811E

In Japan, the number 4 reads like death, so Bob decided to build a live sequence. Living sequence a contains all natural numbers that do not contain the digit 4 . a=[1,2,3,5,6,7,8,9,10,11,12,13,15,16,…] .

For example, the number 1235 is part of the sequence a , but the numbers 4321 , 443 are not part of the sequence a .

Bob realized that he does not know how to quickly search for a particular number by the position k in the sequence, so he asks for your help.

For example, if Bob wants to find the number at position k=4 (indexing from 1 ), you need to answer ak=5 .

可以用数位dp+二分解决。

int A[20];
int dp[20];

///
/// \param pos 当前位置
/// \param last 上一个位置的数的值
/// \param limit 当前位置的数是否可以任取
/// \param lead 当前位置之前全是0
/// \return
int dfs(int pos, int last, bool limit, bool lead) {
    if (pos <= 0) return 1; // 搜索终点
    if (!limit and dp[pos] != -1)
        return dp[pos];
    int ans = 0;
    int _limit = limit ? A[pos] : 9; // 根据是否limit决定循环上界
    for (int v = 0; v <= _limit; ++v) {
        if (v == 4) // 舍弃不合法解
            continue;
        ans += dfs(pos - 1, v, limit && (v == A[pos]), lead and (v == 0));
    }
    if (!limit)dp[pos] = ans;
    return ans;
}

int f(int x) {
    memset(A, 0, sizeof(A));
    memset(dp, -1, sizeof(dp));
    int pos = 0, ans = 0;
    while (x) {
        A[++pos] = x % 10;
        x /= 10;
    }
    return dfs(pos, 11, true, true);
}

bool check(int mid) {
    return f(mid) - f(0) >= n;
}

void solve() {
    cin >> n;
    int L = 1, R = 1e16;
    while (L < R) {
        int mid = (L + R) / 2;
        if (check(mid))R = mid;
        else L = mid + 1;
    }
    print(L);
}