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

CF1789B Serval and Inversion Magic

CF1789B Serval and Inversion Magic


思路

由于讨论回文性我会将下面所有示例字符串以|分成两半

1.先思考我的[l,r]区间有哪些可能呢?

第一种:区间跨左右不对称
1011|1110
如果想要这种区间反转后回文,至少要先保证11|11回文
如果11|11是回文的,区间完全可以缩小为
1011|1110
即可以归纳为第三种

第二种:区间跨左右对称
101111101
这种一定本来就是回文串,直接YES

第三种:区间在一侧
11011|11101
从外层向内,由内层向外,如果本来就满足回文,区间完全可以缩小为
11011|11101

2.从区间的分析已经得到了本题算法

(1)本来就是回文串,直接YES
(2)从外层向内,由内层向外,找最小区间
(3)最小区间反转后回文即为YES
(4)否则为NO


时间复杂度 O(n)


AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;string s;cin >> s;if (n == 1){cout << "Yes\n";continue;}int i = 0, j = n - 1, x = floor((n - 1) / 2), y = n / 2;while (i < j && s[i] == s[j]){i++, j--;}while (i <= x && y <= j && s[x] == s[y]){x--, y++;}if (i == x + 1){cout << "Yes\n";continue;}else{while (((s[i] - '0') == 1 - (s[j] - '0')) && (i <= x)){i++, j--;}if (i == x + 1){cout << "Yes\n";}else{cout << "No\n";}}}
}
http://www.hskmm.com/?act=detail&tid=34253

相关文章:

  • springboot配置拦截器,实现用户未登录不能访问其他页面
  • 2025卫衣厂家口碑推荐:COVERNAT乐酷天品质卓越,时尚舒适首选!
  • 2025年工作服厂家推荐排行榜,防静电/劳保/国网/餐厅/工厂/电工/防酸碱/电力/车间/航空/员工/文化衫/T恤/POLO衫/冲锋衣工作服公司推荐!
  • 岐金兰AI元人文构想的系统化研究:理论创新与实践挑战
  • AtCoder Beginner Contest 391
  • 2025年兄弟机床维修厂家推荐排行榜,专业维修与高效服务口碑之选!
  • 第二章博客
  • 正则表达式入门
  • 2025年气泡膜机厂家推荐排行榜,气泡膜制袋机,高速气泡膜机,全自动气泡膜机,复合气泡膜机,小型气泡膜机公司精选!
  • 深入解析:《Gdb 调试实战指南:不同风格于VS下的一种调试模式》
  • 10 个常见的Python 错误及如何避免它们
  • 平铺窗口合成器杂谈
  • 2025年手持光谱仪/光谱分析仪/便携式光谱仪厂家推荐榜单:矿石/元素/合金/贵金属分析利器,赛普斯/IF光谱仪精选!
  • 微信公众号文章插入附件详细教程-适合于招聘,报名表,公告公示等
  • 题解:P12037 [USTCPC 2025] 数学分析
  • 题解:P10514 考试
  • 华为昇腾笔记之Mindspeed-LLM 中 MoE 实现机制与重写逻辑总览
  • 实时时序上下文推荐系统获KDD最佳论文奖
  • 题解:CF1010A Fly
  • 2025年精密磨床/CNC机械加工厂家推荐排行榜,覆盖铣床/车床/磨削/多轴/复合加工,专业非标定制服务首选!
  • 题解:CF1914F Programming Competition
  • 独立开发者找蓝海:新词引流实战
  • 使用云服务器搭建飞牛Frp 内网穿透服务
  • Luogu P14255 列车(train) 题解 [ 蓝 ] [ 线段树 ] [ 二维平面转化 ]
  • 使用VS2022和Unity时可能出现的问题总结
  • 2025年喷雾机器人,取件机器人,工业机器人厂家权威推荐榜单:智能高效与稳定性能的行业首选!
  • 2025年给汤机厂家推荐排行榜,高效节能/智能控制/稳定耐用的优质品牌选择!
  • 理想完美主义者的宣战:当一人面对整个时代的“合理”谎言
  • Java中的this关键字的用法
  • 网络安全威胁狩猎:主动防御的终极指南