首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。