学步园

思路：先求出一个DP数组，dp[i][j]表示最多i位时，开头为j有几种，然后在由题目的字符串，从第一位往后构造出是第几个数字，然后在通过是第几个构造出相应的答案

代码：

#include <cstdio>
#include <cstring>

typedef long long ll;
int n;
ll k;
char str[25];

ll dp[25][4];

void init() {
	for (int i = 1; i <= 20; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				if (j == k) continue;
				dp[i][j] += dp[i - 1][k];
			}
			dp[i][j]++;
		}
	}
}

int main() {
	init();
	while (~scanf("%d%lld", &n, &k)) {
		scanf("%s", str);
		int len = strlen(str);
		ll r = 0, sn = n;
		for (int i = 0; i < len; i++) {
			int bid;
			if (i == 0) bid = 0;
			else bid = str[i - 1] - '0';
			for (int j = 0; j < str[i] - '0'; j++) {
				if (j == bid) continue;
				r += dp[sn][j];
			}
			r++;
			sn--;
		}
		r -= k;
		int pre = 0;
		sn = n;
		while (r) {
			for (int i = 0; i <= 3; i++) {
				if (i == pre) continue;
				if (dp[sn][i] >= r) {
					pre = i;
					printf("%d", i);
					break;
				}
				r -= dp[sn][i];
			}
			r--;
			sn--;
		}
		printf("\n");
	}
	return 0;
}