思路:数位DP+构造,先dp[i][j]表示i位总和为j的情况数,然后两种情况分别去进行数位DP,按高位往低位放去构造即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int q, x, y, b, m, k; int bit[35], bn, dp[35][305]; void get(int x) { bn = 0; if (!x) bit[bn++] = 0; while (x) { bit[bn++] = x % b; x /= b; } } int cal1(int x) { if (x == -1) return 0; get(x); int ans = 0, sum = m; for (int i = bn; i; i--) { for (int x = 0; x < bit[i - 1]; x++) { if (sum - x < 0) continue; ans += dp[i - 1][sum - x]; } sum -= bit[i - 1]; if (sum < 0) break; } return ans; } int cal2(int x) { int len = 0; while (dp[len][m] < x) len++; int ans = 0; for (int i = len; i; i--) { for (int j = 0; j < b; j++) { if (m - j < 0) break; if (dp[i - 1][m - j] >= x) { m -= j; ans = ans * b + j; break; } x -= dp[i - 1][m - j]; } } return ans; } int main() { int cas = 0; while (~scanf("%d%d%d%d%d", &q, &x, &y, &b, &m)) { printf("Case %d:\n", ++cas); if (x > y) swap(x, y); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < 33; i++) { for (int j = 0; j <= m; j++) { if (!dp[i][j]) continue; for (int x = 0; x < b; x++) { if (j + x > 300) continue; dp[i + 1][j + x] += dp[i][j]; } } } if (q == 1) printf("%d\n", cal1(y + 1) - cal1(x)); else { scanf("%d", &k); int a = cal1(x); if (cal1(y + 1) - a < k) printf("Could not find the Number!\n"); else printf("%d\n", cal2(k + a)); } } return 0; }