学步园

明显数位DP，一开始是用了二分+数位DP，结果T了，过不了，后面看了网上题解，发现这种题其实都可以用构造来实现，先确定位数，然后从高位从小到大枚举放什么数字即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

int t, X, Y;
ll L, R;
int bit[22], bn;

void get(ll x) {
	bn = 0;
	if (x == 0) bit[bn++] = 0;
	while (x) {
		bit[bn++] = x % 10;
		x /= 10;
	}
	for (int i = 0; i < bn / 2; i++)
		swap(bit[i], bit[bn - i - 1]);
}

ll dp[22][22][22], DP[22][22][22];

ll solve(ll num) {
	get(num);
	memset(dp, 0, sizeof(dp));
	int xnum = 0, ynum = 0, flag = 0;
	for (int i = 0; i < bn; i++) {
		for (int x = 0; x <= X; x++) {
			for (int y = 0; y <= Y; y++) {
				if (dp[i][x][y] == 0) continue;
				for (int k = 0; k < 10; k++) {
					if (k == 4) dp[i + 1][x + 1][y] += dp[i][x][y];
					else if (k == 7) dp[i + 1][x][y + 1] += dp[i][x][y];
					else dp[i + 1][x][y] += dp[i][x][y];
				}
			}
		}
		if (flag) continue;
		for (int k = 0; k < bit[i]; k++) {
			if (k == 4) dp[i + 1][xnum + 1][ynum]++;
			else if (k == 7) dp[i + 1][xnum][ynum + 1]++;
			else dp[i + 1][xnum][ynum]++;
		}
		if (bit[i] == 4) xnum++;
		else if (bit[i] == 7) ynum++;
		if (xnum > X || ynum > Y) flag = 1;
	}
	if (xnum == X && ynum == Y) dp[bn][X][Y]++;
	return dp[bn][X][Y];
}

void init() {
	DP[0][0][0] = 1;
	for (int i = 0; i <= 20; i++) {
		for (int j = 0; j <= 20; j++) {
			for (int k = 0; k <= 20; k++) {
				DP[i + 1][j + 1][k] += DP[i][j][k];
				DP[i + 1][j][k + 1] += DP[i][j][k];
				DP[i + 1][j][k] += DP[i][j][k] * 8;
			}
		}
	}
}

ll cal(ll num) {
	int len = 0;
	while (1) {
		if (DP[len][X][Y] >= num) break;
		len++;
	}
	ll ans = 0;
	int sx = X, sy = Y;
	for (int i = len; i; i--) {
		for (int x = 0; x < 10; x++) {
			int vi = i - 1;
			int vx = sx - (x == 4);
			int vy = sy - (x == 7);
			if (vx < 0 || vy < 0) continue;
			if (DP[vi][vx][vy] >= num) {
				ans = ans * 10 + x;
				sx = vx; sy = vy;
				break;
			}
			num -= DP[vi][vx][vy];
		}
	}
	return ans;
}

int main() {
	init();
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%I64d%I64d%d%d", &L, &R, &X, &Y);
		int q;
		ll k;
		scanf("%d", &q);
		printf("Case #%d:\n", ++cas);
		while (q--) {
			scanf("%I64d", &k);
			ll a = solve(L);
			if (solve(R) - a < k) {
				printf("Nya!\n");
				continue;
			}
			printf("%I64d\n", cal(a + k));
		}
	}
	return 0;
}