CSP202409B - 字符串变换
题目描述
本题涉及的字符共有 种，包括大小写英文字母 A-Z、a-z，数字 0-9 和空格。
小 P 在这些字符上定义了一个字符替换函数 ，表示把字符 替换成 。
例如，若 ，则字符 a 会被替换成 b；若 ，则字符 b 会被替换成 0。
在字符替换的基础上，定义字符串变换函数 ：将字符串 中的每个字符 都替换为 。
字符替换函数 由 个字符对 给出，表示：
并满足以下条件：
- 所有字符对中的 两两不同，即同一个字符不会被定义两种不同的替换方式；
- 如果某个字符 没有在输入中定义，则认为 ，即该字符保持不变；
- 函数 是单射，即不同字符不会被替换成同一个字符。
现在给定初始字符串 ，需要处理 个查询。
每个查询给出一个正整数 ，要求输出对初始字符串 连续执行 次字符串变换后的结果：
从标准输入读入数据。
输入共 行。
第一行输入一个形如 #s# 的字符串，即使用两个井号 # 将初始字符串 包围起来。
第二行输入一个正整数 ，表示字符替换规则的数量。
接下来的 行，每行输入一个形如：
#xy#
的字符串，表示：
第 行输入一个正整数 ，表示查询数量。
最后一行输入 个由空格分隔的正整数：
分别表示 次查询要求的变换次数。
输出共 行。
对于每个查询，输出字符串经过相应次数变换后的结果。
每一行仍使用两个井号将结果字符串包围，即输出形式为：
#s#
#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3#H llarWaeld#
#HrlloeWo ld#
#Hella Warld#前 的测试数据满足：
- 初始字符串 只包含小写字母；
- 输入的字符替换规则也只涉及小写字母，即小写字母只会被替换成小写字母。
前 的测试数据满足：
全部测试数据满足：
并且初始字符串 的长度不超过 。
由于输入字符串中可能包含空格，因此读入字符串时应当使用能够读取整行的方法，而不能直接使用会跳过空格的普通字符串读入方式。
C++ 中推荐使用：
getline(cin, s);Python 可以直接使用：
input()题解
这道题目放在第2题是相对简单的一道，很容易 AC。
主要需要注意到，对全部的测试数据， 是能够取到 的数量级的，说明这道题不能够完全遵循题意去搞模拟，不然只能过 的测试点。
注意到此题的字符变换有周期性，可以写成环的形式，例如样例：
H -> He -> <blank> -> r -> e<blank> -> r -> e -> <blank>r -> e -> <blank> -> ro -> a -> oa -> o -> a
根据这个性质，就可以不借助模拟，通过取模直接得到各字符在一定次数 次变换后的结果，给出代码如下：
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int n, m;
unordered_map<char, string> f;
unordered_map<char, char> r;
int main() {
string s;
getline(cin, s);
cin >> n;
cin.ignore();
// init
for(char ch = 'a'; ch <= 'z'; ch ++) {
f[ch] += ch;
}
for(char ch = 'A'; ch <= 'Z'; ch ++) {
f[ch] += ch;
}
for(char ch = '0'; ch <= '9'; ch ++) {
f[ch] += ch;
}
f[' '] += ' ';
// read basic relation
while(n --) {
string p;
getline(cin, p);
r[p[1]] = p[2];
}
// transmit
for(const auto& kv : r) {
if (kv.first != kv.second) f[kv.first] += kv.second;
char t = kv.second;
while(r.count(t) && r[t] != kv.first) {
f[kv.first] += r[t];
t = r[t];
}
}
cin >> m;
cin.ignore();
while(m --) {
int k;
cin >> k;
for(const char& ch : s) {
if(f.count(ch)) {
string str = f[ch];
cout << str[k % str.length()];
}
else cout << ch;
}
cout << "\n";
}
return 0;
}