【題意】：略

【題解】：比較經(jīng)典的DP加計數(shù)問題模型，可以算這類問題里比較簡單的一個例子。只要實現(xiàn)str2id和id2str兩個函數(shù)就好了。DP只是簡單的sum{3^i}，而計數(shù)部分，也就是str2id和id2str這兩個函數(shù)，也和最經(jīng)典的那種求第k個C(n, m)組合的算法一樣。PS: 題目所描述的集合其實是相當(dāng)于是給一個深度為n的三叉樹的每個節(jié)點(diǎn)進(jìn)行遍歷標(biāo)號。 

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 25
26 ll dp[maxn];
27 
28 ll id(int n, char c, char *s) {
29     if(*s == 0) return 0;
30     ll tmp = 1;
31     for(char i = '0'; i < *s; i++) {
32         if(i == c) continue;
33         tmp += dp[n-1];
34     }
35     tmp += id(n - 1, *s, s + 1);
36     return tmp;
37 }
38 
39 void dfs(int n, ll k, char c, char *s) {
40     if(k == 0) {
41         *s = '\0';
42     } else {
43         k--;
44         for(*s = '0'; ; (*s)++) {//++*s
45             if(*s == c) continue;
46             if(k < dp[n-1]) {
47                 dfs(n - 1, k, *s, s + 1);
48                 break;
49             } else k -= dp[n-1];
50         }
51     }
52 }
53 
54 int main() {
55     int n;
56     ll k;
57     char s[maxn];
58     dp[0] = 1;
59     for(int i = 1; i < maxn; i++) dp[i] = dp[i-1] * 3;
60     for(int i = 1; i < maxn; i++) dp[i] += dp[i-1];
61     while(~scanf("%d%lld%s", &n, &k, s)) {
62         k = id(n, '0', s) - k;
63         dfs(n, k, '0', s);
64         puts(s);
65     }
66     return 0;
67 }
68