当前位置: 首页 > news >正文

题解:P12672 「LAOI-8」近期我们注意到有网站混淆视听

题目传送门

题目分析

本题要求我们判断对于给定的字符串,最少需要多少次字符交换操作,使得字符串中不存在同时包含 LGR 子串和 CSP 子串的情况。每次操作可以交换任意两个字符。

关键观察:

若字符串中不同时存在 LGR 和 CSP 子串,则无需任何操作(答案为 0)
若字符串中同时存在 LGR 和 CSP 子串,则仅需 1 次操作即可满足条件

为什么只需 1 次操作?因为我们可以交换 LGR 中的任意一个字符与 CSP 中的任意一个字符,这样至少会破坏其中一个子串的结构,使得两者无法同时存在。

解题思路

  1. 统计子串数量:对于每个输入字符串,统计 "LGR" 子串的出现次数(cl)和 "CSP" 子串的出现次数(cC)。

  2. 判断共存情况:如果两种子串不同时存在,不需要任何操作(操作次数为 0)。

  3. 计算最小操作次数:若两种子串同时存在,取两者数量的较小值(mv),最小操作次数为 \(⌈min_val / 2⌉\)(即 \((min_val + 1)/ 2\) ,通过整数运算实现向上取整)。

复杂度

时间复杂度:\(O (T×n)\),其中 T 是测试用例数量,n 是字符串长度。对于每个字符串,我们只需遍历一次即可完成检查。
空间复杂度:\(O (1)\),仅使用了常数个额外变量。

代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;int main() {int AIAmHere = 0;int T;cin >> T;while (T--) {string s;cin >> s;int cl = 0, cC = 0;int n = s.size();for (int i = 0; i <= n - 3; ++i) {string sub = s.substr(i, 3);if (sub == "LGR") {cl++;} else if (sub == "CSP") { cC++;}}int ans = 0;if (cl > 0 && cC > 0) {int mv = min(cl, cC);ans = (mv + 1) / 2; }cout << ans << endl;}return 0;
}

居然真让我找到了可以写题解的红题

http://www.hskmm.com/?act=detail&tid=25955

相关文章:

  • 详细介绍:基于LangChain构建高效RAG问答系统:向量检索与LLM集成实战
  • EPU+VPU+WBUC+WAUC:AI元人文的硅基基石体系
  • 股市技术分析突破
  • 干货分享:无需下载,在线快速编辑图片的完整教程
  • 34.1STM32下的can总线实现知识(区分linux)_csdn - 详解
  • js实现promise常用场景使用示例
  • 英语_阅读_Balancing Benefits and Risks_待读
  • 大模型部署
  • 读技术之外:社会联结中的人工智能02劳工
  • linux
  • 鼠标图标更改样式
  • webpack和vite的区别 - 指南
  • m3u8在线播放测试的方法与常见问题解决方案(附网页演示
  • 校招题
  • Manim实现旋转扭曲特效
  • go语言学习 第5章:函数 - 详解
  • 混沌熵池:“创造之源”还是“皇帝的新衣”?
  • 间谍软件通过虚假自然灾害警报传播
  • KaTeX手册
  • Qt编写上下界面切换效果/前进到下一个界面/后退到上一个页面/零件工艺及管理设计系统
  • 【题解】P1131 [ZJOI2007] 时态同步
  • LGP9120 [NOIP 2022.5] 密码锁 学习笔记
  • 深入解析:OpenCV CUDA模块图像处理------创建CUDA加速的Canny边缘检测器对象createCannyEdgeDetector()
  • 机器人技术奖学金项目助力STEM教育发展
  • SAP ABAP 事务码 RZ12 里的 Max Number of WPs Used 参数的作用介绍
  • busybox 没有 clear 命令吗
  • 实用指南:Hive SQL 中 BY 系列关键字全解析:从排序、分发到分组的核心用法
  • 经过基于流视频预测的可泛化双手运行基础策略
  • 每个JavaScript开发者都应掌握的33个核心概念
  • 解决Docker存储空间不足问题 - 指南