POJ3208 Apocalypse Someday 数位DP经典绝世好题

代码来自 《算法竞赛进阶指南》，品一品。

重点：试除法。

#pragma warning(disable:4996)

#include<iostream>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include <assert.h>
#define pb push_back
#define INF 0x3f3f3f3f
#define inf 1000000007
#define moD 1000000003
#define pii pair<int,int>
#define eps 1e-6
#define equals(a,b) (fabs(a-b)<eps)
#define bug puts("bug")
#define re  register
#define fi first
#define se second
typedef  long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
const int maxn = 1e6 + 5;
const double Inf = 10000.0;
const double PI = acos(-1.0);
using namespace std;

ll mul(ll a, ll b, ll m) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res % m;
}

ll quickPower(ll a, ll b, ll m) {
    ll base = a;
    ll ans = 1ll;
    while (b) {
        if (b & 1) ans = mul(ans, base, m);
        base = mul(base, base, m);
        b >>= 1;
    }
    return ans;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll Lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int readint() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

ll readll() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void Put(ll x) {
    if (x > 9) Put(x / 10);
    putchar(x % 10 + '0');
}


ll f[21][4];
int n, m;

void init() {
    f[0][0] = 1;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 3; j++) {
            f[i + 1][j + 1] += f[i][j];
            f[i + 1][0] += f[i][j] * 9;
        }
        f[i + 1][3] += f[i][3] * 10;
    }
}

int main() {
    init();
    int T = readint();
    while (T--) {
        n = readint();
        for (m = 3; f[m][3] < n; m++);
        for (int i = m, k = 0; i; i--) {
            for (int j = 0; j <= 9; j++) {
                ll cnt = f[i - 1][3];
                if (j == 6 || k == 3) for (int l = max(3 - k - (j == 6), 0); l < 3; l++) cnt += f[i - 1][l];
                if (cnt < n) n -= cnt;
                else {
                    if (k < 3) if (j == 6) k++; else k = 0;
                    printf("%d", j);
                    break;
                }
            }
        }
        puts("");
    }
}