UVa 12897 - Decoding Baby Boos

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每一個主字串,接著根據一大堆規則, 依序 將字母做替換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A

Sample Output

1
2
ABBU_TUMI_CODING_PARO_NAH
CCCCBBY

Solution

由於主字串可能很長,不用針對每次詢問將每一個主字串都拿來修改。只需考量每一種字符轉換的可能,例如源頭 ‘A’ -> ‘Z’, ‘B’ -> ‘X’, ‘C’ -> ‘Z’, … 那麼,接下來遇到 ‘Z’ -> ‘W’,只需要針對 ‘A’ -> ‘W’, ‘C’ -> ‘W’ 即可。

因此,每一次詢問最多消耗 O(26) 完成。

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
#include <stdio.h>
#include <string.h>
using namespace std;
char s[1048576];
int main() {
int testcase, n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%s", s);
scanf("%d", &n);
char R[128], s1[10], s2[10];
for (int i = 0; i < 128; i++)
R[i] = i;
for (int i = 0; i < n; i++) {
scanf("%s %s", s1, s2);
for (int j = 'A'; j <= 'Z'; j++)
if (R[j] == s2[0])
R[j] = s1[0];
}
for (int i = 0; s[i]; i++)
putchar(R[s[i]]);
puts("");
}
return 0;
}
/*
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A
*/