首页 > 代码库 > hdu 3943

hdu 3943

数位dp

#include <cstdio>#include <cstdlib>#include <cmath>#include <stack>#include <vector>#include <sstream>#include <cstring>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <iostream>#define maxn 105#define INF 0x3f3f3f3f#define inf 10000000#define MOD 100000000#define ULL unsigned long long#define LL long long#define _setm(houge) memset(houge, INF, sizeof(houge))#define _clear(houge) memset(houge, 0, sizeof(houge))using namespace std;LL dp[25][25][25], p, q;int dig[25], x, y;void init() {    _clear(dp);    dp[0][0][0] = 1;    for(int i = 1; i <= 20; ++ i) {        for(int j = 0; j <= i; ++ j) {            for(int k = 0; k+j <= i; ++ k) {                dp[i][j][k+1] += dp[i-1][j][k];                dp[i][j+1][k] += dp[i-1][j][k];                dp[i][j][k] += dp[i-1][j][k]*8;            }        }    }}int getdig(LL nx) {    _clear(dig);    int cnt = 0;    while(nx) {        dig[++cnt] = nx%10;        nx /= 10;    }    return cnt;}LL countid(LL nx) {    int cnt = getdig(nx);    LL ans = 0;    int cx = x, cy = y;    for(int i = cnt; i > 0; -- i) {        for(int j = 0; j < dig[i]; ++ j) {            if(j == 4 && cx) ans += dp[i-1][cx-1][cy];            else if(j == 7 && cy) ans += dp[i-1][cx][cy-1];            else if(j != 4 && j != 7) ans += dp[i-1][cx][cy];         }        if(dig[i] == 4) cx --;        if(dig[i] == 7) cy --;        if(cx < 0 || cy < 0) break;    }    return ans;}LL findd(LL k) {    int len = 1;    while(!(dp[len-1][x][y] < k && dp[len][x][y] >= k)) ++ len;    long long res = 0;    int cx = x, cy = y;    for(int i = len; i > 0; -- i)        for(int j = 0; j < 10; ++ j) {            int tx = cx, ty = cy;            if(j == 4) {                -- tx;                if(tx < 0)                    continue;            }            if(j == 7) {                -- ty;                if(ty < 0)                    continue;            }            if(dp[i-1][tx][ty] >= k) {                res = res*10+j;                cx = tx;                cy = ty;                break;            }            k -= dp[i-1][tx][ty];        }    return res;}int main(){    int t, ca = 0;    init();    scanf("%d", &t);    while(t --) {        scanf("%I64d%I64d%d%d", &p, &q, &x, &y);        LL a = countid(p+1), b = countid(q+1);        int n;        scanf("%d", &n);        printf("Case #%d:\n", ++ ca);        while(n --) {            LL k;            scanf("%I64d", &k);            if(k > b-a) puts("Nya!");            else printf("%I64d\n", findd(k+a));        }    }    return 0;}