允许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';
}
}
}
