【CSP CCF记录】202409-2第35次认证 字符串变换
题目
样例输入
#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3
样例输出
#H llarWaeld#
#HrlloeWo ld#
#Hella Warld#
暴力求解
由题目中对字符替换函数f的定义，立即想到了可以用unordered_map容器存储f的映射。
写代码时要特别注意getline 读取一行输入时，会读取到换行符（\n），但是会丢弃换行符，不会将换行符存储在目标字符串中。然而，如果你在cin 中之前使用了其他输入方法（比如cin >>），该输入方法也会读取数据并留下一个换行符在缓冲区中，这可能会导致下一次调用getline 时立即读取到空行或出错。调用cin.ignore() 会丢弃缓冲区中的换行符，这样getline 就能正常工作，读取到你输入的字符串。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
string s;
getline(cin,s);
cin>>n;
cin.ignore(); //忽略换行符
unordered_map<char,char> f;
for(int i=0;i<n;i++)
{
string chars;
getline(cin,chars);
f[chars[1]]=chars[2];
//cout<<"f("<<chars[1]<<")="<<chars[2]<<endl;
}
cin>>m;
for(int i=0;i<m;i++)
{
int times;
cin>>times;
string t=s;
for(int j=0;j<times;j++)
{
for(int k=0;k<s.size();k++)
{
char v=t[k];
if(t[k]=='#')continue;
auto it = f.find(t[k]);
if(it==f.end())continue;
else t[k]=f[v];
}
}
cout<<t<<endl;
}
return 0;
}
但这种暴力求解只能拿80分，最后几个用例用时过长。
改进：字符变换周期
参考了以下两篇博文：第35次CCF-CSP认证 字符串变换C++AC源码（100分）_第35次ccf字符串变换题解c++-CSDN博客
CCF CSP题解：字符串变换（str）（202409-2）_ccf字符串变换-CSDN博客
考虑到字符可能有变换周期，例如以下这种情况，字符最终又会变回自身：
F(a)=b，F(b)=c，F(c)=d，F(d)=a。
所以我们定义一个translistbuild函数，找到f函数中每个字符的变换路径。
unordered_map<char, vector<char>> translist;
void translistbuild(unordered_map<char, char> mp){
for(auto i=mp.begin();i!=mp.end();i++){
char a=i->first;
translist[a].push_back(a);
char c=a;
while(mp.count(c) && mp[c]!=a){
c=mp[c];
translist[a].push_back(c);
}
}
}还是以前文的字符a变换为例，解释这个函数：
1. 遍历mp中的键值对，寻找每个字符的变换周期。
2. 初始化：执行translist[a].push_back(a)，mp[a]={a}，c更新为a，这个操作意味着每个字符a都至少包含自己作为一个变换的起点。
3. 进入while循环：
- mp(a)=b，c更新为b，执行translist[a].push_back(b)，mp[a]={a，b}
- mp(b)=c，c更新为c，执行translist[a].push_back(c)，mp[a]={a，b，c}
- mp(c)=d，c更新为d，执行translist[a].push_back(d)，mp[a]={a，b，c，d}
4. mp(d)==a，退出while循环
在main函数中进行字符替换时只要找到这是该字符最新变换周期的第几次变换。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
unordered_map<char, vector<char>> translist;
void translistbuild(unordered_map<char, char> mp){
for(auto i=mp.begin();i!=mp.end();i++){
char a=i->first;
translist[a].push_back(a);
char c=a;
while(mp.count(c) && mp[c]!=a){
c=mp[c];
translist[a].push_back(c);
}
}
}
int main()
{
int n,m;
string s;
getline(cin,s);
cin>>n;
cin.ignore(); // 忽略换行符
unordered_map<char,char> f;
for(int i=0;i<n;i++)
{
string chars;
getline(cin,chars);
//cout<<chars;
f[chars[1]]=chars[2];
//cout<<"f("<<chars[1]<<")="<<chars[2]<<endl;
}
translistbuild(f);
cin>>m;
for(int i=0;i<m;i++)
{
int times;
cin>>times;
string t=s;
for(int j=0;j<s.size();j++)
{
char v=t[j];
if(t[j]=='#')continue;
auto it = f.find(t[j]); // 查找键为t[j]的元素
if(it==f.end())continue;
else
{
int sz=translist[s[j]].size();
int x=times%sz;
t[j]=translist[s[j]][x];
}
}
cout<<t<<endl;
}
return 0;
}测试结果：
原文地址：https://blog.csdn.net/m0_73733846/article/details/144305258
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！