uva 12596 Recursive Texting

本文从WordPress迁移而来, 查看全部WordPress迁移文章

DFS DP

题意：略

  1. 序列的增长是指数级别的，所以不能模拟

  2. 从整体考虑这个问题，例如一开始给出385，经过m轮后，得到一个很长的序列，但是这个序列可以分为3块，第1块，2块，3块分别是3,5,8经过m轮后变成的。如果要查找的字符在第1块，那么就可以不去考虑5,8，只考虑3

    例如3下一次变化得到479，那么就是说479经过m-1的变化和3经过m轮是一样的，那么由3变成的1块，可以看做有479变成的3块，所以可以再次定位是在这3块中的哪一块。以此类推，一直定位下去

  3. 可以留意到，我们需要一个信息，就是单个字符，经过m轮变化后，得到一个很长的序列，我们没必要知道序列的具体样子，但是我们要知道长度，这个信息，用一个dp预处理出来就行了

dp[n][m]表示单个数字n经过m轮变化后得到的序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 25
#define MAX 110
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

const char NUM[15][8] = {"ZERO","ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
const char KB[15][8] = { "!","$","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};

LL LEN[10][N]; // TOT[n][m]: 单独一个数字n，在经过m轮后长度为多少
char str[MAX]; 
char ANSCHAR;

int find(char ch){
	for(int i = 2; i <= 9; i++)
		for(int k = 0; KB[i][k]; k++)
			if(KB[i][k] == ch) return i;
}

void dfs(int num,int m){
	if(LEN[num][m] != -1) return ;
	LEN[num][m] = 0;
	for(int k = 0; NUM[num][k]; k++){
		char ch = NUM[num][k];
		int __num = find(ch);
		dfs(__num,m-1);
		LEN[num][m] += LEN[__num][m-1];
	}
}

void init(){
	cl(LEN,-1);
	for(int i = 0 ; i < 10; i++)
		LEN[i][1] = strlen(NUM[i]);
	for(int m = 20; m >= 2; m--)
		for(int num = 0; num < 10; num++)
			dfs(num,m);
	/*
	for(int m = 1; m <= 20; m++){
		for(int num = 0; num < 10; num++)
			printf("[%d][%d] = %lld\n",num,m,LEN[num][m]);
		puts("");
	}
	*/
}

void DFS(int *num,int len,int m,LL kth){
	if(m == 1){
		for(int i = 0; i < len; i++){
			int wl = strlen(NUM[num[i]]);
			if(kth > wl) kth -= wl;
			else{
				ANSCHAR = NUM[num[i]][kth-1];
				break;
			}
		}
		return ;
	}
	LL sum = 0;
	int __num[MAX],__len,n = num[len-1];
	for(int i = 0 ; i < len; i++){
		if(sum + LEN[num[i]][m] >= kth){
			n = num[i]; break;
		}
		sum += LEN[num[i]][m];
	}
	cl(__num,0); __len = 0;
	for(int k = 0; NUM[n][k]; k++){
		__num[__len++] = find(NUM[n][k]);
	}
	DFS(__num,__len,m-1,kth-sum);
}

int main(){
	init();
	int T;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas++){
		int nth; LL kth;
		scanf("%s%d%lld",str,&nth,&kth);
		int len = strlen(str);
		int num[MAX];
		for(int i = 0; i < len; i++){
			num[i] = find(str[i]);
		}
		DFS(num,len,nth,kth);
		printf("Case %d: %c\n",cas,ANSCHAR);
	}
	return 0;
}