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; }感谢阅读转载标明出处

相关新闻

Qt +C++ OpenCV+YOLO ONNX+PyTorch 整套技术栈分层掌握标准

Qt +C++ OpenCV+YOLO ONNX+PyTorch 整套技术栈分层掌握标准

Qt C OpenCVYOLO ONNXPyTorch 整套技术栈分层掌握标准按岗位需求分为三层:工程落地刚需层(必须精通)、模型转换辅助层(浅会即可)、算法训练进阶层(可选精通),适配机器视觉上位机、嵌…

2026/11/21 23:45:07 阅读更多 →
新手必看:CRM系统是什么?完整概念解读指南

新手必看:CRM系统是什么?完整概念解读指南

你是不是对CRM的认知还停留在「存客户电话号码的通讯录」? 很多刚接触CRM的职场人、中小创业者都有这个误区:花几千块买个CRM,就是为了防止销售离职带走客户。但实际上,作为企业数字化转型最核心的工具之一,CRM的价值远…

2026/11/7 17:43:28 阅读更多 →
体检数据分析与预警实战:某制造企业健康管理落地案例

体检数据分析与预警实战:某制造企业健康管理落地案例

📌 目录 1. 背景:一家被慢病拖住的工厂 2. 过去的做法为什么没用 3. 预警体系是怎么搭起来的 4. 实施前后的数据对比 5. 一个真实的预警闭环 6. 给HR的几点实操建议---1. 背景:一家被慢病拖住的工厂华东某装备制造集团,两个生产基…

2026/11/18 12:02:22 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/21 23:27:35 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/21 23:27:35 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/21 23:27:35 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/21 23:27:35 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/21 23:27:36 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/21 23:27:37 阅读更多 →

日新闻

周新闻

月新闻