【GESP】C++四级练习 luogu-B3927 [GESP202312 四级] 小杨的字典
GESP C++四级2023年12月真题。本题为一维数组和键值对的应用练习，难度⭐⭐★☆☆。本题在洛谷评定为普及-。
键值对在使用效果上和哈希表很相似，但是哈希表在GESP中是七级考纲的内容，在C++对应的数据结构是
unordered_map，因此特意没有使用。但是键值对在C++对应的数据结构是map，而GESP考纲中好像没有明确说明属于哪个级别，但是从三级真题来开个别题目的解法其实已经可以涉及该部分内容，因此个人认为键值对应该是GESP三级-四级应该掌握的内容，故本题给出两种解法，且在后续题目求解中会将键值对作为可选技能之一。
luogu-B3927 [GESP202312 四级] 小杨的字典
题目要求
题目描述
在遥远的星球，有两个国家 A 国和 B 国，他们使用着不同的语言：A 语言和 B 语言。小杨是 B 国的翻译官，他的工作是将 A 语言的文章翻译成 B 语言的文章。
为了顺利完成工作，小杨制作了一本字典，里面记录了 $N$ 个 A 语言单词对应的 B 语言单词，巧合的是，这些单词都由地球上的 26 个小写英文字母组成。
小杨希望你写一个程序，帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号
!()-.[].{}\|;:'",./?<>和一些 A 语言单词构成，每个单词之间必定由至少一个标点符号分割，你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地，如果遇到不在字典中的单词，请使用大写 UNK 来替换它。
例如，小杨的字典中包含 $2$ 个 A 语言单词 abc 和 d，它们的 B 语言翻译分别为 a 和 def，那么我们可以把 A 语言文章 abc.d.d.abc.abcd. 翻译成 B 语言文章 a.def.def.a.UNK. 其中，单词 abcd 不在词典内，因此我们需要使用 UNK 来替换它。
输入格式
第一行一个整数 $N$，表示词典中的条目数。保证 $N \le 100$。
接下来 $N$ 行，每行两个用单个空格隔开的字符串 $A$， $B$ ,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有 $A$ 不重复；保证 $A$ 和 $B$ 的长度不超过 $10$。
最后一行一个字符串 $S$ ，表示需要翻译的 A 语言文章。保证字符串 $S$ 的长度不超过 $1000$，保证字符串 $S$ 只包含小写字母以及标点符号
!()-.[].{}\|;:'",./?<>。
输出格式
输出一行，表示翻译后的结果。
输入输出样例 #1
输入 #1
1
2
3
4
2
abc a
d def
abc.d.d.abc.abcd
输出 #1
1
a.def.def.a.UNK
输入输出样例 #2
输入 #2
1
2
3
4
5
3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd
输出 #2
1
a,(def)def!-a?xxxx
输入输出样例 #3
输入 #3
1
2
3
1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz
输出 #3
1
!()-[]{}\|;:'",./?<>UNK
题目分析
题目分析
本题主要考察以下几个知识点：
- 字符串的处理
- 字符串的遍历和分割
- 字符的判断（区分字母和标点符号）
- 字符串的拼接操作
- 键值对（或数组）的应用
- A语言和B语言单词的对应关系存储
- 单词查找和替换
- 基本的输入输出处理
- 读取字典大小N
- 读取N对单词对应关系
- 读取待翻译的文章
解题思路：
- 首先需要建立A语言到B语言的映射关系
- 可以使用两个平行数组（数组解法）
- 或使用map容器（键值对解法）
- 处理输入的文章时，需要：
- 遍历文章中的每个字符，遇到小写字母时收集成单词，遇到标点符号时进行处理
- 当遇到标点符号时，先处理已收集的单词(如果有)，再保留标点符号
- 例如处理”abc.d”时:
- 收集字母’a’,’b’,’c’形成单词”abc”
- 遇到’.’时先翻译”abc”，再保留’.’
- 特殊情况处理：
- 文章结尾如果还有未处理的单词需要进行最后一次翻译
- 连续标点符号时(如”,.!”)，直接按顺序保留即可
- 时间复杂度分析：
- 数组解法：查找单词时需要 $O(N)$ 的时间复杂度
- 键值对解法：查找单词时为 $O(\log N)$ 的时间复杂度
- 总体时间复杂度取决于文章长度 $L$ 和查找次数 $M$，为 $O(L \times M)$
- 空间复杂度分析：
- 需要存储字典内容，空间复杂度为 $O(N)$
- 需要存储处理结果，空间复杂度为 $O(L)$，其中 $L$ 为输入文章长度
本题的难点在于正确处理单词的分割和替换，以及确保标点符号的位置保持不变。选择合适的数据结构（数组或map）对于代码的简洁性和效率都有重要影响。
示例代码
方法一，双数组模拟键值对
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
#include <iostream>
#include <string>
// 存储A语言单词的数组
std::string a_str_array[105];
// 存储B语言单词的数组，与a_str_array下标一一对应
std::string b_str_array[105];
/**
* 判断字符是否为小写字母
* @param c 待判断的字符
* @return 如果是小写字母返回true，否则返回false
*/
bool is_lower(char c) {
if (c >= 'a' && c <= 'z') {
return true;
}
return false;
}
/**
* 根据A语言单词查找对应的B语言翻译
* @param input A语言单词
* @return 如果找到返回对应的B语言翻译，否则返回"UNK"
*/
std::string get_b_str(std::string input) {
for (int i = 0; i < 105; i++) {
if (input == a_str_array[i]) {
return b_str_array[i];
}
}
return "UNK";
}
int main() {
// 读入字典条目数
int n;
std::cin >> n;
// 读入字典内容
for (int i = 0; i < n; i++) {
std::cin >> a_str_array[i];
std::cin >> b_str_array[i];
}
// 读入待翻译的文章
std::string input_str;
std::cin >> input_str;
// 存储翻译结果
std::string output_str = "";
// 临时存储当前正在处理的单词
std::string word = "";
// 遍历输入文章的每个字符
for (int i = 0; i < input_str.length(); i++) {
// 当前字符是小写字母时的处理
if (is_lower(input_str[i])) {
// 如果是小写字母，将其追加到当前正在构建的单词中
// 例如：处理"abc"时，依次将'a','b','c'加入word中
word += input_str[i];
} else {
// 当前字符是标点符号时的处理
// 如果已经积累了一个单词(word不为空)，需要先处理这个单词
if (word.length() > 0) {
// 查找这个A语言单词对应的B语言翻译
// 例如：word为"abc"时，查找得到对应的翻译"a"
std::string b_str = get_b_str(word);
// 将翻译后的单词加入到最终结果字符串中
output_str += b_str;
// 清空word，准备处理下一个单词
word = "";
}
// 将当前的标点符号直接加入到结果字符串中
// 标点符号在A语言和B语言中保持不变
output_str += input_str[i];
}
}
// 处理最后一个单词（如果存在）
if (word.length() > 0) {
std::string b_str = get_b_str(word);
output_str += b_str;
}
// 输出翻译结果
std::cout << output_str;
return 0;
}
方法二，利用键值对
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
#include <map>
#include <string>
#include <iostream>
#include <cctype>
int main() {
// 读入字典条目数
int n;
std::cin >> n;
// 创建字典，使用map存储A语言到B语言的映射关系
std::map<std::string, std::string> dict;
// 读入n组A语言和B语言的对应关系
for (int i = 0; i < n; i++) {
std::string A, B;
std::cin >> A >> B;
dict[A] = B; // 将A语言单词作为键，B语言单词作为值存入字典
}
// 读入需要翻译的A语言文章
std::string input_str;
std::cin >> input_str;
// 存储翻译结果
std::string result = "";
// 遍历输入文章的每个字符
int i = 0;
while (i < input_str.length()) {
// 如果当前字符是小写字母，说明遇到了一个单词
if (islower(input_str[i])) {
std::string word = ""; // 用于存储当前正在处理的单词
// 持续读取小写字母，直到遇到非小写字母或到达字符串末尾
while (i < input_str.length() && islower(input_str[i])) {
word += input_str[i]; // 将字母加入当前单词
i++;
}
// 检查单词是否在字典中
if (dict.count(word)) {
result += dict[word]; // 如果在字典中，添加对应的B语言翻译
} else {
result += "UNK"; // 如果不在字典中，添加"UNK"
}
} else {
// 如果是标点符号，直接添加到结果中
result += input_str[i];
i++;
}
}
// 输出翻译结果
std::cout << result << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
