【题解】HackerRank - Decibinary Numbers

题目

https://www.hackerrank.com/challenges/prime-xor

题意

定义一种新的数值表示方法,每一位权值和二进制一样,但是每一位都可以是 0~9。问第 k 大的数是几(如果表示的数值一样大的话,再看做十进制比较)。

题解

dp[i][j] 表示 i 用不超过 j 位表示的方案数

先估计一下范围,但是开一维 dp 做会有这样的问题:表示同样的值的数没法按数值大小排序。

1
2
3
4
5
6
7
8
9
10
FOR(i, 2, 1000000) {
FOR(j, 0, 10)
if ((i - j) % 2 == 0) dp[i] += dp[(i - j) / 2];
// cerr << i << ' ' << dp[i] << endl;
s += dp[i];
if (s > 1E16) {
cerr << dp[i] << ' ' << i << endl; // 114928788468 285112
break;
}
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int maxn = 285112 + 5, maxm = 20;
LL dp[maxn][maxm], s[maxn] = {1};
LL T, n;

void go(LL n, LL rank, LL pos, bool leading) {
// cerr << n << ' ' << rank << ' ' << pos << ' ' << leading << endl;
if (!pos) return;
assert(n >= 0 && rank >= 0);
LL t = 1 << (pos - 1);
LL s = 0;
FOR(i, 0, 10) {
if (s + dp[n - i * t][pos - 1] <= rank) s += dp[n - i * t][pos - 1];
else {
if (!leading || i) cout << i;
go(n - i * t, rank - s, pos - 1, leading && !i);
return;
}
}
}

int main() {
FOR(i, 0, maxm) dp[0][i] = 1;
FOR(i, 1, maxn) {
s[i] = s[i - 1] + dp[i - 1][maxm - 1];
FOR(j, 1, maxm) {
dp[i][j] = dp[i][j - 1];
LL t = 1 << (j - 1);
FOR(k, 1, 10)
if (t * k <= i) dp[i][j] += dp[i - t * k][j - 1];
else break;
}
}
cin >> T;
while (T--) {
cin >> n;
LL k = upper_bound(s, s + maxn, n) - s - 1;
go(k, n - s[k], maxm, 1);
puts("");
}
}