GESP 2023年12月 真题题解 | 小杨的字典(字符串处理)
- 2026-11-22 22:57:17
在遥远的星球,有两个国家 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 来替换它。
abc a
d def
abc.d.d.abc.abcd.
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz
换个角度看这题:如果你是出题人,你会怎么设卡?顺着这个角度,解法反而更好记。
轮到 GESP 2023年12月 的字符串处理题了。这题在考场上属于「必须拿分」那一档,下面按上课的顺序讲:先看什么、再算什么、最后怎么验。
题目:小杨的字典
场次:2023年12月 四级|难度:四级
知识点:字符串
链接:https://www.acgo.cn/problemset/info/46132
在遥远的星球,有两个国家 A 国和 B 国,他们使用着不同的语言: A 语言和 B 语言。小杨是 B 国的翻译官,他的工作是将 A 语言的文章翻译成 B 语言的文章。 为了顺利完成工作,小杨制作了一本字典,里面记录了 N 个 A 语言单词对应的 B 语言单词,巧合的是,这些单词都由地球上的 26 个小写英文字母组成。 小杨希望你写一个程序,帮助他根据这本字典翻译一段 A 语言文章。
一句话概括:用字符串把题目要求原样翻译成代码,属于考场上必须拿满分的题。
| 卡点 | 出题人卡的是什么 | 你要做的事 |
|---|---|---|
| 数据类型 | 用 int 装不下的人 | 累加变量用 long long |
| 边界 | 只按样例想问题的人 | 题目说「到」或者「包括」 |
| 输出格式 | 不看输出要求直接 cout 的人 | 换行、空格、顺序逐项对 |
三个卡点都不难,难的是同时想到。
出题人不会白给数据范围。范围里就藏着「能不能暴力」这个提示,顺着它往回推,解法基本就定了。
这段代码的主要逻辑是:
1 . 通过 map 存储 A 语言到 B 语言的映射关系。 2 . 读取字典中的条目数和具体的映射关系。 3 . 读取需要翻译的 A 语言文章。 4 . 遍历文章,将小写字母拼接成单词,检查单词是否在字典中,如果在则输出翻译,否则输出 UNK 。同时,输出标点符号。
此代码对于给定的问题描述能够完成相应的任务,将 A 语言文章翻译成 B 语言。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
using namespace std;
map<string, string> dict; // 使用map存储A语言到B语言的映射关系
int main() {
int N;
cin >> N; // 输入字典中的条目数
while (N--) {
string word1, word2;
cin >> word1 >> word2; // 读入
dict[word1] = word2; // 将A语言单词和对应的B语言翻译存入map
}
string content, word = "";
cin >> content, content += "\n"; // 输入需要翻译的A语言文章
int m = content.length();
for (int i = 0; i < m; i++) { // 遍历
if (content[i] >= 'a' && content[i] <= 'z') { // 判断
word += content[i]; // 如果是小写字母,拼接成单词
} else {
if (word != "") { // 判断
if (dict.count(word)) // 判断
cout << dict[word]; // 如果单词在字典中,输出对应的翻译
else
cout << "UNK"; // 否则输出UNK
word = ""; // 清空单词
}
cout << content[i]; // 输出标点符号
}
}
return 0;
}
代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。
第一段,把数据读进来。
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
if (content[i] >= 'a' && content[i] <= 'z') {
word += content[i]; // 如果是小写字母,拼接成单词
} else {
if (word != "") {
if (dict.count(word))
cout << dict[word]; // 如果单词在字典中,输出对应的翻译
else
cout << "UNK"; // 否则输出UNK
// …(这段后面还有,见上面的完整代码)
这段是整道题唯一需要想的地方,也是字符串处理的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
下面按四步验一遍,这个顺序建议你考试时也照做。
样例输入
abc a
d def
abc.d.d.abc.abcd.
样例输出
| 步骤 | 做什么 | 通过标准 |
|---|---|---|
| 1 | 拿样例对一遍 | 输出和题目给的一模一样 |
| 2 | 换成最小规模 | n = 1 或只有一组数据时不崩,结果符合题意 |
| 3 | 检查输出末尾 | 没有多余空格,最后一行有换行 |
| 4 | 跑完剩下 2 组样例 | 全部对上再提交,别只看第一组 |
题目还有 2 组样例,全部跑通再提交。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 递归层数爆栈 | 链状数据直接递归到 n 层 | 改显式栈,或把递归改成从底往上推 |
| 累加结果溢出 | int sum = 0; | 累加变量用 long long |
| 漏掉区间右端点 | i < R | i <= R |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
最后收个尾,三句话说完这题。
- 筛的是什么:字符串的完整度——范围、边界、格式缺一不可。
- 要记住的:
string从 0 开始,题目说第 i 个字符,代码里写s[i-1]。 - 下一步:找同场次另一道题,用同样的三个卡点自查一遍。
系列按场次往前推,下一篇还在这个级别,难度会往上走一档。
- 本文属于《GESP 真题题解》系列,第 25 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道字符串处理题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:学完这题,你能想出一道用同样套路的旧题吗?评论区对个暗号。
把这篇转给一起刷题的同学,两个人对着讲一遍思路,比一个人看三遍都管用。关注本号不迷路。
后台回复 “资料”,领历年真题完整代码包(持续更新)。
本篇编号 GESP-083(公众号 MP-083)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。