UVA 12596 Recursive Texting 預處理+dfs

UVA 12596 Recursive Texting 預處理+dfs

題目鏈接：點擊打開鏈接

題意：

給定一個字符串，

操作一次：

1、先把字符串按照上面的圖變成數字。

2、再把數字按照上面的圖變成字母。

輸出操作n次後第k位的字母。

先預處理每個一個字母操作i次後產生的長度，然後遞歸搜索答案。

#include 
#include 
#include 
#include 
#include 
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<>T; getchar();
	while(T-- > 0) {
		scanf("%s", a);cin>>n>>k;
		cout<<"Case "<