【题解】HackerRank - Decibinary Numbers

Posted on Edited on In Disqus:

题目

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("");
    }
}