Decibinary Numbers

允许0~9的二进制数，给出数字序号，返回数字，如下图：

Sample Input 0

5
1
2
3
4
10

Sample Output 0

0
1
2
10

小数字情况：列表

#include <iostream>
using namespace std;

int ans[] = {0, 1, 2, 10, 3, 11, 4, 12, 20, 100, 5, 13, 21, 101, 6, 14, 22, 30, 102, 110, 7, 15, 23, 31, 103, 111, 8, 16, 24, 32, 40, 104, 112, 120, 200, 1000, 9, 17, 25, 33, 41, 105, 113, 121, 201, 1001, 18, 26, 34, 42};

int main()
{
    int q, x;
    cin >> q;
    while (q--)
    {
        cin >> x;
        cout << ans[x-1] << '\n';
    }
}

显然对大的序号不起作用。

暴力求解

解出一定范围内所有的decibinary数。经过研究，序号9000的十进制数最大对应于111110，所以计算这个数以内的所有数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int val(int x)
{
    int d = 0, s = 0;
    while (x > 0)
    {
        s += (x % 10) * (1 << d);
        x /= 10;
        d++;
    }
    return s;
}

bool cmp(int a, int b)
{
    if (val(a) == val(b))
        return a < b;
    return val(a) < val(b);
}

vector<int> ans;

int main()
{
    for (int i = 0; i <= 111110; i++)
        ans.push_back(i);
    sort(ans.begin(), ans.end(), cmp);
    int q, x;
    cin >> q;
    while (q--)
    {
        cin >> x;
        cout << ans[x-1] << '\n';
    }
}

直接生成列表：递归

破解：递归的目的是将较大的解空间逐渐分解为较小的解空间，并且给出边界条件。左成云将递归叫“暴力递归”，因为动态规划也属于递归的一种，二者的不同在于动规将算过的值存下来。
对于这道题，我们可以定义一个函数gen(d,s,v)，表示用一个d位的decibinary数，表示十进制数s,现在考虑的整数v.
边界条件是：

#include <iostream>
#include <vector>
using namespace std;

vector<int> ans;

void gen(int d, int s, int v)
{
    if (s < 0 || s > 9*((1 << (d+1))-1));
    else if (s == 0 && d == -1) ans.push_back(v);
    else
    {
        for (int i = 0; i <= 9; i++)
            gen(d-1, s-i*(1 << d), v*10+i);
    }
}

int main()
{
    int val = 0, cur, q, x;
    for (int i = 0; i < 600; i++)
        gen(20, i, 0);
    cin >> q;
    while (q--)
    {
        cin >> x;
        cout << ans[x-1] << '\n';
    }
}

动态规划

破解：
定义函数f(d,s)表示为了凑成十进制数s，用一个d位decibinary数（或者说用d个数字）表示出来的所有方法。
很显然，f(0,0)=1，表示为了凑成0，用一个0位decibinary数（不需要任何数），有一种方法。或者说，前期的努力已经将目标数凑完了，而所有的位也都用完了，这时方法数+1；
f(0,s)=0, 当 s!=0，这表示还需要凑一个s，但没有可用的位数了，所以没有任何方法达成，f(0,s)=0；
f(d,s)=0,当s<0，这是因为要用0~9凑成负数是不可能的；
=\sum ^9 _{i=1} f(d-1, s-i2^{d-1}) )
表示用i放在第d位，剩下的d-1位数凑成s-i * 2^(d-1)，将i从0~9循环一遍，将f全部加起来即可。
=\left{\begin{aligned}1, & d=0,s=0 \0, & d=0,s\not=0 \0, & s<0\ & \sum ^9 _{i=1} f(d-1, s-i2^{d-1}) \end{aligned} \right)
我们再定义一个数组ai,表示凑成十进制数i的方法数，令ci = a0+a1+...ai。
这样我们就可以知道ci-1<x<ci，说明查询的第x个是为了凑成十进制数i的。
到这里，我们可以重复上面的寻找过程，但步骤要简单：

#include <ios>
#include <iostream>

long long int dp[25][300005] = {};
long long int nm[300005] = {};

long long int cnt(int d, int s)
{
    if (d == -1 && s == 0)
        return 1;
    else if (d == -1)
        return 0;
    else if (dp[d][s] == -1)
    {
        dp[d][s] = 0;
        for (int i = 0; i <= 9 && (1 << d)*i <= s; i++)
            dp[d][s] += cnt(d-1, s-((1 << d)*i));
    }
    return dp[d][s];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    for (int i = 0; i < 25; i++)
        for (int j = 0; j < 300005; j++)
            dp[i][j] = -1;
    for (int i = 0; i < 300005; i++)
        nm[i] = cnt(24, i);
    for (int i = 1; i < 300005; i++)
        nm[i] += nm[i-1];
    int q, lo, hi, ans;
    long long int x;

    std::cin >> q;
    while (q--)
    {
        std::cin >> x;
        if (x == 1)
            std::cout << 0 << '\n';
        else
        {
            lo = 0;
            hi = 300004;
            while (lo <= hi)
            {
                int mid = (lo+hi)/2;
                if (nm[mid] >= x)
                {
                    ans = mid;
                    hi = mid-1;
                }
                else
                    lo = mid+1;
            }

            long long int g = x-nm[ans-1];
            long long int s = ans;
            long long int val;
            int d;

            for (int i = -1; cnt(i, s) < g; i++)
                d = i;
            d++;

            while (d >= 0)
            {
                val = 0;
                for (int i = 0; i <= 9; i++)
                {
                    if ((s - (1 << d)*i) >= 0)
                        val += cnt(d-1, s-(1 << d)*i);
                    if (val >= g)
                    {
                        std::cout << i;
                        g -= val-cnt(d-1, s-(1 << d)*i);
                        s -= (1 << d)*i;
                        break;
                    }
                }
                d--;
            }
            std::cout << '\n';
        }
    }
}