CSP202409B：字符串 K 次替换查询的高效解法

今天我们来看CSP202409B. 字符串变换这道题目题意很简单给定替换函数f将某些字符替换成其它字符求执行K次替换后的结果首先我们可以想到最暴力的解法1.维护一个mapchar,char mp记录每个映射关系2.执行k轮变换每轮变换对每个字符c执行操作cmp[c]这样就得到了如下代码# include bits/stdc.h using namespace std; #define itn int #define ll long long #define ld long double #define mod 998244353 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string s; getline(cin,s); // 有空格用getline读取 int n; cinn; cin.ignore(); mapchar,char mp; for (char c A; c Z; c) mp[c] c; for (char c a; c z; c) mp[c] c; for (char c 0; c 9; c) mp[c] c; mp[ ] ; string temp; for(int i0;in;i) { getline(cin,temp); mp[temp[1]]temp[2]; } mp[#]#; int m; cinm; while(m--) { int k; cink; string sss; for(int i0;iss.length();i) { for (int j 0; j k; j) { if (mp[ss[i]]ss[i]) break; ss[i]mp[ss[i]]; } } coutssendl; } return 0; }我们发现暴力的解法只能得到80分考虑对解法优化对每个字符c我们记录它不断映射后的结果无非两种1.进入自环形成一条链最后一个字符满足 mp[c] c可视为一个自环。2. 进入真循环存在 mp[a] b, mp[b] c, mp[c] a 的情况即形成环。也就是说f最后一定会进入某个循环那么我们只需要对每个字符进行dfs遍历找到循环起点和环大小如果k比循环起点小那么直接找路径对应位置否则说明已经进入循环对 k 取模后映射到环上的对应字符。这样我们就得到了满分代码# include bits/stdc.h using namespace std; #define itn int #define ll long long #define ld long double #define mod 998244353 char get(char c,int k,const mapchar,char mp) { vectorchar path; // 存储从字符c开始的变换路径 setchar visited; // 记录访问过的字符 char currentc; while (visited.find(current)visited.end()) { visited.insert(current); path.push_back(current); currentmp.at(current); } int cycle_start0; // 记录循环起点 while (path[cycle_start]!current) cycle_start; if (kcycle_start) return path[k]; int remainingk-cycle_start; int cycle_lenpath.size()-cycle_start; return path[cycle_startremaining%cycle_len]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string s; getline(cin,s); ss.substr(1,s.length()-2); int n; cinn; cin.ignore(); mapchar,char mp; for (char c A; c Z; c) mp[c] c; for (char c a; c z; c) mp[c] c; for (char c 0; c 9; c) mp[c] c; mp[ ] ; string temp; while (n--) { getline(cin,temp); mp[temp[1]]temp[2]; } int m; cinm; while (m--) { int k; cink; string ress; for (char c:res) { cget(c,k,mp); } cout#res#endl; } return 0; }感谢阅读转载标明出处