题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3930

题目大意:

数位DP,输出第n个不包含4和13的数字。

题解:

范围太大要用unsigned long long,具体题解代码有详细的注释。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <ctime>
#include <cfloat>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

/* quick input */
template <class T>
bool scan_d(T &ret){
    char c;
    int sgn;
    T bit = 0.1;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && c != '.' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret*10 + (c - '0');
    if (c == ' ' || c == '\n') {
        ret *= sgn;
        return 1;
    }
    while (c = getchar(), c >= '0' && c <= '9') {
        ret += (c - '0')*bit;
        bit /= 10;
    }
    ret *= sgn;
    return 1;
}
/* end - quick input */

const int N = 18;
const int A = 4, B0 = 1, B1 = 3;
unsigned long long f[N + 5][3];
/*
 f[i][0] 不包含4和13
 f[i][1] 不包含4和13最高位为3
 f[i][2] 包含4或13
 */
int bit[N + 5];

void init() {
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        f[i][0] = f[i - 1][0]*9 - f[i - 1][1]; // 最高位加除4以外的9个数字并减去在3前面加1的情况
        f[i][1] = f[i - 1][0]; // 在不包含4和13的情况前加3
        f[i][2] = f[i - 1][2]*10 + f[i - 1][0] + f[i - 1][1]; // 包含4和13前加任意数字,在不包含4和13前加4,在不包含4和13最高位为3前加1
    }
}

unsigned long long solve(unsigned long long n) {
    int len = 0;
    unsigned long long tn = n;
    while (tn) {
        bit[++len] = tn % 10;
        tn /= 10;
    }
    bit[len + 1] = 0;
    unsigned long long ans = 0;
    bool flag = false;
    for (int i = len; i; --i) {
        ans += f[i - 1][2]*bit[i]; // 低位包含4和13的情况
        if (flag) ans += f[i - 1][0]*bit[i]; // 高位已经出现4或13的情况
        else {
            if (bit[i] > A) ans += f[i - 1][0]; // 当前位出现4考虑低位不包含4或13的情况
            if (bit[i + 1] == B0 && bit[i] > B1) ans += f[i][1]; // 高位为1考虑当前位为2的情况
            if (bit[i] > B0) ans += f[i - 1][1]; // 当前位出现1考虑低位为2的情况
        }
        if (bit[i] == A || (bit[i + 1] == B0 && bit[i] == B1)) flag = true; // 高位出现4或13的情况
    }
    return n - ans;
}

int main() {
    init();
    unsigned long long n;
    while (scanf("%llu", &n) != EOF) {
        unsigned long long l = 0, r = (unsigned long long)1000000000000000000*18, ans = 1;
        while (l <= r) {
            unsigned long long m = l/2 + r/2 + (l % 2 + r % 2)/2;
            if (solve(m) <= n) {
                l = m + 1;
                ans = m;
            } else r = m - 1;
        }
        printf("%llu\n", ans);
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/6488 - 海胖博客