【题意】:略

【题解】:比较经典的DP加计数问题模型,可以算这类问题里比较简单的一个例子。只要实现str2id和id2str两个函数就好了。DP只是简单的sum{3^i},而计数部分,也就是str2id和id2str这两个函数,也和最经典的那种求第k个C(n, m)组合的算法一样。PS: 题目所描述的集合其实是相当于是给一个深度为n的三叉树的每个节点进行遍历标号。 

【代码】:
 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<intint> 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