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

今天我们来看CSP202409B. 字符串变换这道题目：

题意很简单，给定替换函数f，将某些字符替换成其它字符，求执行K次替换后的结果

首先，我们可以想到最暴力的解法：

1.维护一个map<char,char> mp，记录每个映射关系

2.执行k轮变换，每轮变换对每个字符c执行操作：c=mp[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; cin>>n; cin.ignore(); map<char,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 i=0;i<n;i++) { getline(cin,temp); mp[temp[1]]=temp[2]; } mp['#']='#'; int m; cin>>m; while(m--) { int k; cin>>k; string ss=s; for(int i=0;i<ss.length();i++) { for (int j = 0; j < k; j++) { if (mp[ss[i]]==ss[i]) break; ss[i]=mp[ss[i]]; } } cout<<ss<<endl; } 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 map<char,char> &mp) { vector<char> path; // 存储从字符c开始的变换路径 set<char> visited; // 记录访问过的字符 char current=c; while (visited.find(current)==visited.end()) { visited.insert(current); path.push_back(current); current=mp.at(current); } int cycle_start=0; // 记录循环起点 while (path[cycle_start]!=current) cycle_start++; if (k<cycle_start) return path[k]; int remaining=k-cycle_start; int cycle_len=path.size()-cycle_start; return path[cycle_start+remaining%cycle_len]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string s; getline(cin,s); s=s.substr(1,s.length()-2); int n; cin>>n; cin.ignore(); map<char,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; cin>>m; while (m--) { int k; cin>>k; string res=s; for (char &c:res) { c=get(c,k,mp); } cout<<"#"<<res<<"#"<<endl; } return 0; }

感谢阅读！

转载标明出处