允許0~9的二進(jìn)制數(shù)拓瞪，給出數(shù)字序號溶锭，返回數(shù)字，如下圖：
Sample Input 0
5
1
2
3
4
10
Sample Output 0
0
1
2
10
小數(shù)字情況：列表
#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';
}
}
顯然對大的序號不起作用乘综。
暴力求解
解出一定范圍內(nèi)所有的decibinary數(shù)憎账。經(jīng)過研究，序號9000的十進(jìn)制數(shù)最大對應(yīng)于111110卡辰，所以計算這個數(shù)以內(nèi)的所有數(shù)鼠哥。
#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';
}
}
直接生成列表：遞歸
破解：遞歸的目的是將較大的解空間逐漸分解為較小的解空間熟菲，并且給出邊界條件。左成云將遞歸叫“暴力遞歸”朴恳，因為動態(tài)規(guī)劃也屬于遞歸的一種抄罕，二者的不同在于動規(guī)將算過的值存下來。
對于這道題于颖，我們可以定義一個函數(shù)gen(d,s,v)呆贿，表示用一個d位的decibinary數(shù)，表示十進(jìn)制數(shù)s,現(xiàn)在考慮的整數(shù)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';
}
}
動態(tài)規(guī)劃
破解：
定義函數(shù)f(d,s)表示為了湊成十進(jìn)制數(shù)s森渐，用一個d位decibinary數(shù)（或者說用d個數(shù)字）表示出來的所有方法做入。
很顯然，f(0,0)=1同衣，表示為了湊成0竟块，用一個0位decibinary數(shù)（不需要任何數(shù)），有一種方法耐齐±嗣兀或者說，前期的努力已經(jīng)將目標(biāo)數(shù)湊完了埠况，而所有的位也都用完了耸携，這時方法數(shù)+1；
f(0,s)=0, 當(dāng) s!=0辕翰，這表示還需要湊一個s夺衍，但沒有可用的位數(shù)了，所以沒有任何方法達(dá)成喜命，f(0,s)=0沟沙；
f(d,s)=0,當(dāng)s<0，這是因為要用0~9湊成負(fù)數(shù)是不可能的壁榕；
=\sum ^9 _{i=1} f(d-1, s-i2^{d-1}) )
表示用i放在第d位尝胆，剩下的d-1位數(shù)湊成s-i * 2^(d-1)，將i從0~9循環(huán)一遍护桦，將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)
我們再定義一個數(shù)組ai,表示湊成十進(jìn)制數(shù)i的方法數(shù)，令ci = a0+a1+...ai二庵。
這樣我們就可以知道ci-1<x<ci贪染，說明查詢的第x個是為了湊成十進(jìn)制數(shù)i的。
到這里催享，我們可以重復(fù)上面的尋找過程杭隙，但步驟要簡單：
#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';
}
}
}
