题目链接：点击打开链接

题意：

给定一个字符串，

操作一次：

1、先把字符串按照上面的图变成数字。

2、再把数字按照上面的图变成字母。

输出操作n次后第k位的字母。

先预处理每个一个字母操作i次后产生的长度，然后递归搜索答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
#define int ll
char str[11][11] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
ll cnt[2][30], t[30][30];
char a[1005];
int idx(char c){
	if('A'<=c && c<='C')return 2;
	if('D'<=c && c<='F')return 3;
	if('G'<=c && c<='I')return 4;
	if('J'<=c && c<='L')return 5;
	if('M'<=c && c<='O')return 6;
	if('P'<=c && c<='S')return 7;
	if('T'<=c && c<='V')return 8;
	return 9;
}
void ADD(ll *p, char ch, ll num) {
	if(ch == 'A' || ch == 'B' || ch == 'C') {
		p['T'-'A']+=num; p['W'-'A']+=num; p['O'-'A']+=num;
	}
	else if(ch == 'D' || ch == 'E' || ch == 'F') {
		p['T'-'A']+=num; p['H'-'A']+=num; p['R'-'A']+=num; p['E'-'A']+=num*2;
	}
	else if(ch == 'G' || ch == 'H' || ch == 'I') {
		p['F'-'A']+=num; p['O'-'A']+=num; p['U'-'A']+=num; p['R'-'A']+=num;
	}
	else if(ch == 'J' || ch == 'K' || ch == 'L') {
		p['F'-'A']+=num; p['I'-'A']+=num; p['E'-'A']+=num; p['V'-'A'] += num;
	}
	else if(ch == 'M' || ch == 'N' || ch == 'O') {
		p['S'-'A']+=num; p['I'-'A']+=num; p['X'-'A']+=num;
	}
	else if(ch == 'P' || ch == 'Q' || ch == 'R' || ch == 'S') {
		p['S'-'A']+=num; p['E'-'A']+=num*2; p['V'-'A']+=num; p['N'-'A']+=num;
	}
	else if(ch == 'T' || ch == 'U' || ch == 'V' ) {
		p['E'-'A']+=num; p['I'-'A']+=num; p['G'-'A']+=num; p['H'-'A']+=num; p['T'-'A']+=num;
	}
	else if(ch == 'X' || ch == 'Y' || ch == 'Z'|| ch == 'W') {
		p['N'-'A']+=num*2; p['I'-'A']+=num; p['E'-'A']+=num;
	}
}
void pre() {
	for(int i = 0; i < 26; i ++) {
		t[i][0] = 1;
		int ne = 0, old = 1;
		memset(cnt, 0, sizeof cnt);
		cnt[ne][ i ] = 1;
		for(int j = 1; j <= 20; j ++) {//
			ll sum = 0;
			swap(ne, old);
			memset(cnt[ne], 0, sizeof cnt[ne]);
			for(int tt = 0; tt < 26; tt ++) {
				ADD(cnt[ne], tt+'A', cnt[old][tt]);
			}
			for(int tt = 0; tt < 26; tt++)sum+=cnt[ne][tt];
			t[i][j] = sum;
		}
	}
}
char dfs(int deep, ll k){
	if(deep == 0)
		return a[k-1];

	int len = strlen(a);
	for(int i = 0; i < len; i++)
		if(t[a[i]-'A'][deep] >= k)
		{
			char cc = a[i]; a[0] = 0;
			strcpy(a, str[idx(cc)]);
	//		cout<<a;
            return dfs(deep-1, k);
		}
		else k -= t[a[i]-'A'][deep];
}
#undef int
int main() {
#define int ll
	pre();
	int T, n, Cas = 1; ll k;
	cin>>T; getchar();
	while(T-- > 0) {
		scanf("%s", a);cin>>n>>k;
		cout<<"Case "<<Cas++<<": ";printf("%c\n", dfs(n, k));
	}
	return 0;
}

UVA 12596 Recursive Texting 预处理+dfs