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;
}