题目描述
本题涉及字符包括大小写字母（A-Z 和 a-z）、数字（0-9）和空格共 63 种。在这个字符集合上，小 P 定义了一个字符替换函数 f(ch)，表示将字符 ch 替换为 f(ch)。 例如 f(a)=b 表示将 a 替换为 b，f(b)=0表示将 b 替换为 0。 进而可以将其扩展为字符串变换函数 F(s)，表示对字符串 s 进行变换，将 s 中每个字符 ch 都替换为 f(ch)。
字符替换函数 f 可表示为 n 个字符对 (ch1,ch2)，即 f(ch1)=ch2。
-
n 个字符对中，ch1 两两不同，即不会出现同时定义了 f(a)=b 和 f(a)=0 的情况；
-
未定义的 f(ch)，可视为 f(ch)=ch，即字符 ch 保持不变；
-
函数 f 为单射，即当 ch1≠ch2 时有 f(ch1)≠f(ch2)，例如不会同时有 f(b)=0 和 f(0)=0（
b和0都被替换为0）。
现给定初始字符串 s，试处理 m 个查询：每个查询包含一个正整数 k，询问对初始字符串 s 变换 k 次后的结果 Fk(s)。
输入格式
从标准输入读入数据。
输入共 n+4 行。
输入的第一行包含一个字符串，形如 #s#，即用两个井号字符 # 将初始字符串 s 囊括其中。
输入的第二行包含一个正整数 n，表示组成函数 ff 的字符对数；接下来 n 行每行输入一个形如 #xy# 的字符串，表示 f(x)=y。
输入的第 n+3 行包含一个正整数 m，表示查询的个数；下一行包含空格分隔的 m 个正整数 k1,k2,⋯,km，表示 m 个查询。
输出格式
输出到标准输出。
输出共 m 行，依次输出 m 个查询的结果；输出时每行同样是一个形如 #s# 的字符串，即用两个井号把变换后的字符串 s 括起。
样例输入
#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3
样例输出
#H llarWaeld#
#HrlloeWo ld#
#Hella Warld#
子任务
前 6060 的测试数据保证初始字符串 s 仅包含小写字母，且输入的 nn 个字符对也皆为小写字母（即保证小写字母仅会被替换为小写字母）；
前 8080 的测试数据保证查询数量 m≤10m≤10、变换次数 k≤100k≤100；
全部测试数据保证 0<n≤630<n≤63、0<m≤1030<m≤103、0<k≤1090<k≤109 且初始字符串 s 包含不超过 100 个字符。
提示
由于读入的字符串中包含空格字符，推荐使用按行读取的方式，避免读入时跳过空格（如 cin 直接读入字符串）。
C 语言：可以使用 fgets() 函数读入整行，fgets(s, count, stdin) 会从标准连续输入读入至多 count - 1 个字符，并存入字符数组 s，直到遇到换行符或文件末尾为止。在前一种情况下，s 结尾处会存有读入的换行符。也可使用 getchar() 函数逐个字符读入，如 char ch = getchar();，这种方法需手动判断是否到达行末，即返回值是否为 \n。
C++：可以使用 std::getline() 函数读入整行：std::getline(std::cin, s) 会从标准输入读入字符，并存入字符串 std::string s 中，直到换行符或文件末尾为止。在前一种情况下，换行符会从标准输入中读出，但不会存入字符串 s 中。
Python：使用 input() 函数即可读入整行。
题解：
刚看完题，就感觉给的单射一定能形成循环，否则当k是1e9肯定超时。
开始解题，关于如何替换字符串，使用一个<char,char>的map记录单射，循环原串就可以得到转化一次后的新字符串。
所以第一种解法就是蛮力求解，循环k，每循环一个就从头开始循环原串，输出，得到80分（前面的给的是真宽泛），时间效率O（N3）。
想怎么优化，因为CCF给的空间达到了512M，所以空间非常充足，以空间换时间是很好的办法，于是有了第二种方法。建一个新的<int,string> 的map，先取得k的最大值，然后变换k次，每次把得到的string和次数放进map里，最后遍历一遍k输出string就可以了，得到80分，但是时间优化到了O（N2）。
那怎么办呢，于是就再牺牲一下空间并考虑一下循环的事了。
说到循环，很简单的方法就是记录循环的次数然后取模即可，但是你怎么知道循环从哪开始，题目也没说一定全部都是循环，所以从原串开始变换，并压入一个新的map并记录变换的次数（代码是用了一个vector记录，原理一样），然后当遇到重复的就去map里找，得到开始重复的次数，当k<=这个数就直接输出，当k>这个数时就取模后加上序号即可，得分90，时间O（N），但是仍然有两个数据集出现了奇怪的问题（还没搞明白）。
但是对于解题，我们已经搞定了数据集最大的那几个，那就结合第二种和第三种方法，就成功得到了100啦！虽然很可耻……
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long ll;
string s;
int n=0,i,j,t,t1;
string op[1001]={""};
int m=0;
int k[10001]={0};
vector <int> v;
map<char,char> mp;
map<int,string> mpp;
map<string ,int > maa;
vector <string > vt;
int maxk=0;
int cmp(int x,int y){
return x<y;
}
main(){
getline(cin,s);
//cout << s << "\n";
/*
for(i=0;i<s.size();i++){
mp[s[i]]=s[i];
}
*/
cin >> n;
getchar();
for(i=0;i<n;i++){
getline(cin,op[i]);
mp[op[i][1]]=op[i][2];
}
cin >> m;
for(i=1;i<=m;i++){
cin >> k[i];
if(k[i]>maxk){
maxk=k[i];
}
mpp[k[i]]="";
}
//cout << maxk << "\n";
maa[s]=1;vt.push_back(s);
//maxk=100;
if(m>=11){
for(i=1;i<=maxk;i++){
/*
for(t=0;t<s.size();t++){
s[t]=mp[s[t]];
}
*/
for (char& ch : s) {
if (mp[ch]) ch = mp[ch];
}
//cout << s << "\n";
if(maa[s]==0){
maa[s]=1;
vt.push_back(s);
}
else{
for(j=0;j<vt.size();j++){
if(vt[j]==s){
t1=j;
break;
}
}
/*
cout << maa.size() << "\n";
cout << vt.size() << "\n";
t=maa.size();
cout << t << " " << t1 << "\n";
for(j=0;j<vt.size();j++){
cout << vt[j] << "\n";
}
*/
t=maa.size();
break;
}
}
for(i=1;i<=m;i++){
if(k[i]<=t1){
cout << vt[k[i]-1] << "\n";
}
else if(t1!=0){
cout << vt[(k[i]-1)%(t-t1)+t1] << "\n";
}
else{
cout << vt[k[i]%(t-t1)+t1] << "\n";
}
}
}
else{
for(i=1;i<=maxk;i++){
/*
for(t=0;t<s.size();t++){
s[t]=mp[s[t]];
}
*/
for (char& ch : s) {
if (mp[ch]) ch = mp[ch];
}
/*
if(mpp.find(i)!=mpp.end()){
//cout << s << "\n";
mpp[i]=s;
}
*/
mpp[i]=s;
}
for(i=1;i<=m;i++){
cout << mpp[k[i]] << "\n";
}
}
}
