互动｜期末玄学许愿指南

🎒 期末倒计时！你的玄学能量储备好了吗？ 在刷题、背诵、焦虑、抓狂的边缘反复横跳…… 别怕！期末许愿池2.0 限时返场！ 用宇宙的能量，换考场的奇迹—— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌟 许愿通道正式开启 请严格按以下格式，留下你的神圣考前愿望： 🎯 我希望： __________ 💀 我愿意为此放弃： __________ 🔮 如果灵验，我将回来还愿并： __________ 🌟 优质示范： > 🎯 我希望： 数学期末考能稳定发挥，大题不崩 > 💀 我愿意为此放弃： 一周的峡谷夜游，专心刷题 > 🔮 如果灵验，我将回来还愿并： 在社区分享我的错题笔记+给AC君点爆100个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 许愿者专属福利 所有按格式完整许愿的用户，均可参与能量池抽奖！ AC君将随机抽取 5位 天选锦鲤与点赞最高TOP1，送出AC狗拼图冰箱贴随机1片。 > ⏰ 活动时间：即日起 - 1月31日 23:59 > 🎉 开奖日期：2月2日（考完正好来还愿✨） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 许愿池使用说明 1. ✅ 愿望越具体、越真诚，宇宙接收信号越强！ 2. ✅ 放弃的代价要真实可执行（比如“放弃一周游戏”比“放弃呼吸”更靠谱） 3. ❌ 禁止许愿他人挂科（反向能量会反弹！） 4. 💫 互相点赞、评论加油的愿望，实现概率+99% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌌 来自宇宙的回复 > “你刷的每一道题，背的每一个知识点， > 都会在考场上变成让你稳住的底气。 > 许愿不是魔法，而是给自己一个仪式感的承诺—— > 期末考试月，我们一起把它变成奇迹发生的土壤。” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👇 评论区已开放许愿通道，你的愿望，宇宙正在收听！ 转发给并肩作战的搭子，一起接收好运能量！ 🔮 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

关于ACGO的一些小建议

关于ACGO的一些小建议： 处罚的力度 * 首先处罚的力度就很值得一说。处罚的力度大了，风气自然就好了。 至于如何处罚，值得一谈。 首先 ACGO 是一个 OJ 平台，作为一个 OJ 平台，那么学术诚信固然重要，现在感觉官方把“学术诚信”至关重要的这一点丢弃，作为次要的，把大精力丢弃到去管一些非常琐碎的小事。浪费资源。 其次不理解ACGO为什么会对“禁言”这个处罚情有独钟。个人认为学术诚信和禁言半毛钱关系没有。早就建议过官方加上“棕名”“扣分”“清空通过题目”这些处罚。不知道官方到底是为什么一直没有加。是技术原因还是什么，难猜。个人认为加上“棕名”“扣分”“通过0”这些处罚更好的能改变学术诚信。 再就是关于“封禁”这个或许是最严重的惩罚。建议 ACGO 采取洛谷一样对“封禁”的方式。建议给予一个封禁的期限（考虑到糖丸较多觉得定在 1~3 个月左右差不多），不要封禁就永久封，对社区的风气毫无帮助。建议的是增加给予“封禁”这个处罚的频率，减少“封禁”这个处罚的严重程度。当然对于屡教不改的可以给一点特殊关照。 觉得官方应该着重注意下以下几个点，而不是琐碎的小事： * 慢慢地把竞赛作弊者的比例降下来，考虑到糖丸较多，降到“10%”已经很好了，岁虽然远没有达到LGR的“2%”。对于这个建议官方除以“每作弊三次封禁 1 个月”这样的处罚，更有利于社区发展。大小号参赛封禁大小号各 1 个月 * 整治抄题解，提交记录行为。对于这个，主要让用户去菊爆。主要看两道题目的提交时间只差以及用户习惯的码风。一旦发现再30天内抄10次题解或提交记录的，与比赛作弊同罪。再者就是加上例如拿到40pts以上再让用户看提交记录是不是大大减少了这些事发生的频率 讨论区质量 关于社区的讨论区有一些机制很令人费解。 For example“热榜”这个机制很不理解。例如发这个帖子当时的热榜状况： 真正的学术贴可能只有 1 个甚至可以说是没有。不知道官方整改整改在哪里了。把学术贴全整改没了。 说真的不理解为什么让热帖上榜而不是学术贴。 个人认为应该让官方置顶帖优先上榜，有空位的让最新发布的学术贴上榜。 这个机制会稍微好些。再就是加强在学术贴内灌水的禁言力度。 还有些涉政的到没有造成什么特别大的实质性影响，这看官方自己了 @AC君

码上开聊VOL14 | 童瑞骐

码上开聊VOL14 | 童瑞骐：从ACGO榜一到CSP-S巅峰 关键词：CSP-S 一等、社区榜一、出题志愿者、ACGO核心玩家 > 个人档案 * 姓名：童瑞骐 * 社区昵称：cjdstttttt * 年级：九年级 * 坐标：广东深圳 * 江湖地位：ACGO社区长期“榜一”级核心大神、出题审核志愿者 * 硬核荣誉：2024年CSP-J一等奖，2025年CSP-S一等奖和NOIP(体验赛)一等奖 * 社区数据：一年提交超800次，解题数领先99.95%的用户，发帖破千，粉丝上千 * 社区好友：@Gragher，@dream92143，@MuktorFM，@复仇者_澜（不处不加团队） * 主页直通车：点击围观超级大帅童 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 正式开聊 Q1：社区里你的昵称“CJDSTTTTTT”，有什么特别的含义？ 帅童： 其实并没有特殊含义（（（，这个是按我 ACGO 一开始的 ID ”超级大帅童“ 改的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q2：你之前很长一段时间社区榜一，保持这种“统治级”的数据，背后是靠惊人的自律，还是纯粹的热爱驱动？ 帅童： 都有吧，我觉得更偏重于热爱。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q3：最早是怎么“入坑”编程的？是学校里接触的，还是自己偶然发现的？还记得第一次写出能运行的程序是啥感觉吗？ 帅童： 应该是偶然发现的。在我六岁的时候，妈妈觉得我没有什么爱好，就给我报了机器人兴趣班，但我手太笨拼不了那些，机构老师感觉我适合打代码，所以就入坑编程了。当天我调试了几次代码后发现能运行了，非常兴奋。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q4：从“学着玩”到“认真打比赛”，这个转变是怎么发生的？ 帅童： 大概就在去年，打ACGO 排位赛 #9 的时候，当时我熬了一晚上终于 AK 了。虽然现在看来题没有多难，但是这确实是我转向疯狂刷题的地方。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q5：为了达到现在的水平，你觉得自己投入最多的是什么？在这个过程中有没有想放弃的时候，又是怎么坚持下来的？ 帅童： 我投入最多的就是时间和精力。但我整个过程还算比较顺利的，也比较开心，没有放弃的想法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q6：从排位榜一大佬，变成为公开赛设计考题、审核比赛的“幕后大佬”，你觉得哪个角色更有挑战，也更有趣？ 帅童： 我觉得还是在当公开赛负责人时更有趣，因为能让其他 ACGO 同学做上我出的题特别有成就感（虽然现在看来质量也不是很高）。 附：帅童贡献的题目 * A49458.统计……？ * A49459.迷宫 * A49457.圆环游戏 * A49456.一个简单的迷宫 …… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q7：今年CSP-S拿下一等奖，这个结果在你意料之中吗？你觉得是哪些因素让你稳稳拿下？ 帅童： 也没多稳吧，当时估分的时候发现好像挂了 757575 分，吓死了，但最后出题人还是在 T3 送了我 303030，让我压线过一等。 我觉得今年的 CSP-S 能拿一等主要是心态还算不错，在发现不会写 T1 后没有特别崩溃，秒开 T2 并光速想到了接近正解的解法，后面一优化就 808080 分了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q8：作为过来人，你觉得对于冲刺CSP-J/S这种比赛，线下上课系统学，和在ACGO上刷题实战，这两件事怎么配合效果最好？ 帅童： 我认为应该理论和实践相结合，上课与刷题实战一个也不能少。如果还有时间的话也可以尝试看看博客。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q9：有没有哪个瞬间，突然感觉课上学的一个算法，在ACGO的某道题上“通了”，然后解题功力大涨？ 帅童： 划分区间。这个是老师给的线段树题目的作业。做完这题我感觉对线段树优化 DP 更熟练了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q10：你发帖量也巨大，这种大量的输出和讨论，真的对你的编程思维有帮助，还是纯粹为了快乐？ 帅童： 一开始我发的都是一些灌水、无意义的帖子，但后来我会将我学到的知识、做过的题的题解发到讨论区，时不时复习一下，顺便给 ACGO 用户科普一下。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q11：时间管理是大难题！你怎么平衡学校、机构课程和ACGO上“根本停不下来”的刷题/比赛？给大家支个招吧！ 帅童： 这个对我也很困难，只能自己想办法挤时间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q12：遇到真的“卡死”的难题，你的终极求助链条是啥？先自己死磕？翻题解？还是直接“摇”老师？ 帅童： 首先会想 30min，如果完全没思路或者思路假了就看一下题解，否则会自己想下去。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q13：作为已经登上S组顶峰的大佬，你打算怎么在ACGO上调整训练模式，去征服下一座山？ 帅童： 现在要全面转战蓝紫黑题了，争取在省选的时候把两天的 T1 都做出来。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q14：说一条你认为最重要的、对竞赛选手的“逆耳忠言”。 帅童： 信竞之路会越来越难走，到了后面几乎只能花时间“死磕”了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q15：在ACGO里，你觉得自己最大的收获是什么？ 帅童： 学到了很多知识，提高了代码能力，而且还认识了一堆大佬（上面的社区好友全都是）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q16：明年在学业和竞赛上有什么规划？打算如何实现？ 帅童： 编程和学业都要花时间做好，在补whk的同时也要努力刷题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > ⚡ 快问快答 * ACGO上最让你沉迷的功能是？ 讨论区。水讨论太好玩了（（（ * 最让你有挑战欲望的编程语言是？ 肯定是C++。 * 除了编程，最近在“肝”什么？ 在恶补语文、数学。 * 你的学习BGM风格是？ “随缘但坚持”，前面忘了后面忘了（（（ * 用一句话形容你的性格？ 有点糖（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 🎙️ 访谈结语 帅童的成长轨迹，是一条从偶然“入坑”到称霸社区，再到赛场夺魁的清晰路径。他的经历印证了热爱与坚持的力量：ACGO社区不仅是他的“练功房”，更是激发他从参与者成长为贡献者的舞台。面对未来更艰险的省选之路，他已准备好向蓝紫黑题发起新一轮冲锋。这份源于热爱的专注，或许正是他一路“稳”下去的最大底气。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击回顾往期访谈 >>

求此题题解

之前的题目做出来了（也因为比较“水”所以删了） 补充一下题目： 蓝题也许不水了吧（但愿是这样）

堆学习笔记

叠甲： > 本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。 堆及堆的性质 > 堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。 > > 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 priority_queue 其实就是一个大根堆。 > > （小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。 -- OI wiki ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 堆使用数组进行储存。对于第 iii 个节点，其父节点下标为 i2\frac{i}{2}2i ，左右孩子节点下标分别为 2×i2 \times i2×i 与 2×i+12\times i+12×i+1 。 （小根）堆元素的插入与取出 1. 在堆尾加入该元素，并把这个节点设为当前节点。 2. 比较当前节点与父节点的大小： 2.1 如果当前节点小于父节点，交换他们的值，并把父节点设为当前节点，重复步骤 2。 2.2 若当前节点大于父节点，或该节点已经为根节点，停止。 小根堆插入代码实现： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 取出堆的根结点的值 2. 把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。 3. 把根结点置为当前父结点 。 4. 如果当前父节点无儿子（parent>len/2parent >len/2parent>len/2），则结束；否则，把当前父节点的两（或一）个儿子中值最小的那个设置为当前的子结点。 5. 比较当前父节点与当前子节点的值，如果当前父节点的值小于或等于当前子节点的值，则结束；否则，交换这两个结点的值，把当前父节点指向当前子节点，继续执行步骤 4。 小根堆取出当前节点并删除当前节点代码实现（这里分为 top 和 pop ） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 手写堆模版： 小根堆： 大根堆： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 真题演练： 题目： 排序 题目大意： 给你 NNN 个数，要求输出他们从小到大排列的结果。 思路： 这里我们使用堆排序。 很简单，首先构建一个堆，将这 NNN 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ THE END 后序还会更新o

LHCX Cup 2026 赛时公告帖

返回目录 比赛严禁作弊！ 赛事讨论须知 * 赛前，你可以发布一些灌水内容； * 赛中，你只能发布与题目有关的内容，不得涉及解法、思路等； * 赛后，你可以与其他人一起探讨题目做法、思路。 赛事公告帖 * LHCX Cup 2026（邀请码：Rped） * @𝓐𝓘𝓮𝓻 质疑：T8T8T8 公式有误。 @𝓔𝓣𝓗𝓐𝓝 回答：检查无误。 * @想要AC 嘲讽：T4T4T4 太简单了！ @𝓔𝓣𝓗𝓐𝓝 回答：做人不可太狂妄。不过说实话，确实挺简单。 * @焉知非福 质疑：T3T3T3 根据 i,j,k,ti,j,k,ti,j,k,t 的范围，答案应该是 n⋅mn\cdot mn⋅m。 @𝓔𝓣𝓗𝓐𝓝 回答：范围内的 k,tk,tk,t 都算。 讨论处罚 按照岚核团队#等级制度处理并发布作弊信息在获奖通知帖中。

好奇AC狗友的作诗水平

此入抽风想看看AC狗友的作诗水平（想搞抽象也没事） 把上下句发在评论区 我想挑几首好的展示在帖子上 祝马年快乐~~ ——————————————-—————————— 以及，期末考试快到了 ，各位AC狗友都复习了吗？ 可以在我评论区许愿吗？我会给每条评论都点赞的哦 （省流：可以进团吗？新鲜的阿辞小蛋糕很好吃的） 团队在这↓ https://www.acgo.cn/application/1994033111445377024 —————————————————————————— 展示： 马年如红火沟， 一齐乐乐洋洋。 一生能过几马？ 且得珍惜一生！ ——@战神 我们游荡在无限的尾系里，感受着宇宙的生生不息 ——@破谜者烛汐 风月何添以晓霜，风自青睐又何妨？ 马蹄遂追千落回，岱那青山透青华。 破月惊天魂沾血，残旗卷云骨沁沙。 星河倒悬剑如雨，独向苍茫试裂甲。 烽火燃尽天涯路，犹有寒梅立断崖。 风磨月刃，霜淬戈鋋。 岱岳倾辉以铸魄，银河决口而洗兵。 魂沾血处，忽生赤薇千朵； 旗裂云时，乍现白虹贯野。 马蹄凿碎光阴路，青山浮作渡劫舟。 风月何曾畏晓霜？青山独向马蹄扬。 千回落日追残甲，万仞惊涛淬断枪。 破月魂悬星作雨，擎天骨立血为疆。 忽闻云外梅花曲，散作昆仑雪里香。 蹄声碎，山河缺。 角声断，云涛叠。 把沧桑煮酒，浇透诗页。 魂寄寒梅崖上雪，魄随孤雁关前钺。 待归来、松柏刻刀痕，皆成偈。 ——@Aler ——————————————————

讨论———GESP考试后你的想法

GESP考试刚刚结束，你的脑子里是不是装了各种各样的想法呢？ 是：“为什么考试前不复习呀，啊啊啊啊啊啊啊啊啊啊啊！” 还是：“考试综合征又犯了！” 又或者是：“忘打分号了！！！” 尽情地发泄在评论区吧！ 是因为标点而爆0？ 还是因为考试忘记深搜怎么写? 又或者是超纲了？ 还是尽情地发泄在评论区吧！ 如果和别人同感就给他点上一个赞，不要忘了给帖子点一个哟！孩子在做上榜的梦，帮我圆梦吧！ 发布于2025/12/30 1天时间，300阅读，100评论，50点赞，可以可以！ 作者消失3天，回来一看，帖子都到第二了，666，诗人（2026，1，4） 帖子都到第一了，又掉下来了

CCF GESP 12月3级考试游记

我一级考了90分卡点跳级考三级，9月是第一次考，报了绍兴市上虞区上德实验小学，下图为证： 三级我在ACGO备赛专区一直刷题，自我感觉一般般，不是很难。 进入正文： CCF ™的整个绍兴市都没考点，只好报杭州的浙大城市学院，下图为证： 到门口时，我顿时无语了，北校区和南校区相对而立。 5楼的话直接选择坐电梯，顺便和其他考生聊会儿天。 到了526教室时，入校政策不是说家长不能上来吗？怎么一大堆家长？早知道让我爸上来了。 进入考场，能坐70个人，NB！我是60号，一个更加NB的同桌连新建源代码都不会，善良的我还是教他了。 开始考试前，我不小心把“GESP”拖到粘贴链接的地方，打开了一个新网站，我赶紧删掉，应该没逝。 开考了，我眼前一大堆的伪代码，好家伙，伪代码当饭吃了，实在没辙，只好先做编程题。 而且伪代码我还看不懂，递归都有，A[I].FIND() 就这个看的懂。 编程题还好，第1题一做就对，第2题写了好几个代码，都没有预期效果。 最后忘记怎么写对了。 前面太难了，我本来想复制到DEV-C++，结果好几个人被抓了，不敢了！我直接 成绩还可以，起码过了，下图为证： 超纲的话我必须重考，有纪念品还保底过关，太好了！ CCF 你就是我的神！ 敬请期待三级重考游记......

#创作计划# 最小表示&Manacher

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 热度终究还是比不过灌水吗…… > UPD1.8，更新了一道例题 太好啦！加精啦！\tiny太好啦！加精啦！太好啦！加精啦！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以下为正文。 > 字符串的70%可以用哈希+二分解决，而剩下30%中的70%可以用后缀数组解决。 标题险些打不下 如你所见，本文讲解两种算法：最小表示法& Manacher\tt {Manacher}Manacher 算法（俗称马拉车）。 PART 1.最小表示法 前置芝士：循环同构 定义：当字符串 SSS 中可以选定一个位置 iii 满足 S[i⋯n]+S[1⋯i−1]=TS[i\cdots n]+S[1\cdots i-1]=T S[i⋯n]+S[1⋯i−1]=T 则称 SSS 和 TTT 循环同构。 最小表示法 定义：字符串 SSS 的最小表示为与 SSS 循环同构的所有字符串中字典序最小的字符串。 人话：把 SSS 放在一个环上，从任一点开始读取字符串，所得的串中字典序最小的即为 SSS 的最小表示。 暴力算法 思维难度： 000 我们每次比较 iii 和 jjj 开始的循环同构，把当前比较到的位置记作 kkk ，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。 * 缺点 该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉。 例如：对于字符串 aaa⋯abaaa\cdots abaaa⋯ab ，不难发现这个算法的复杂度退化为 O(n2)O(n^2)O(n2) 。 优化算法 我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。 考虑字符串 AAA 、 BBB 为 SSS 的两组循环同构，且他们的前 kkk 个字符相等，即： S[i⋯i+k−1]=S[j⋯j+k−1]S[i\cdots i+k-1]=S[j\cdots j+k-1] S[i⋯i+k−1]=S[j⋯j+k−1] 不妨设 S[i+k]>S[j+k]S[i+k]>S[j+k]S[i+k]>S[j+k] 如图，不难发现对于任意起始点为 l(i≤l≤i+k)l(i\leq l\leq i+k)l(i≤l≤i+k) 的字符串不可能成为答案（必定碰到红框导致被否掉）。 （黑框部分为相等部分） 所以我们比较时可以跳过下标 l∈[i,i+k]l\in [i,i+k]l∈[i,i+k] ，直接比较 Si+k***_{i+k****i+k+1 。 算法流程 (1)(1)(1) 初始化指针 i=0,j=1i=0,j=1i=0,j=1 ，匹配长度 k=0k=0k=0。 (2)(2)(2) 比较第 kkk 位，根据比较结果跳转指针（哪个大跳哪个）。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同。 (3)(3)(3) 重复 (2)(2)(2) 直到结束。 (4)(4)(4) 从 min(i,j)min(i,j)min(i,j) 开始输出答案。 具体体细节见代码。 例题1 板子题，直接上代码。 例题2 还是板子题，直接把最小表示丢进set里。 code: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 2.MANACHER\TT MANACHERMANACHER算法 引入 我们来看这样一个问题：求一个字符串的最长回文子串。 暴力 非常简单，枚举每个子串，判断回文，时间复杂度 O(n3)O(n^3)O(n3)。 中心扩展法 枚举每个点，向两边扩展，时间复杂度 O(n2)O(n^2)O(n2)。 需要注意的是，这个算法只能判断奇数长度的回文。 解决办法也很简单，在每个字符后面插入一个空格，把偶回文转换为奇回文。 优化(MANACHER\TT {MANACHER}MANACHER) 我们考虑以下定义 p[i]p[i]p[i]：表示以位置iii为中心的最大回文半径。 ididid：当前已知的右边界最靠右的回文中心。 mxmxmx：该回文的最右边界索引，满足 mx=id+p[id]−1mx=id+p[id]-1mx=id+p[id]−1。 算法流程(具体细节见代码注释) * 遍历每个位置 iii ，首先利用对称性确定 p[i]p[i]p[i] 的初始值： 如果 iii 在当前最右回文边界mxmxmx之外，只能从111开始暴力扩展。 如果 iii 在 mxmxmx 之内，可以通过对称点 i1i_1i1 （ iii 关于 ididid 的对称点）的信息，取 min(mx−i,p[i1])min(mx-i, p[i_1])min(mx−i,p[i1 ]) 作为初始值。 * 确定初始值后，向两边扩展检查字符是否匹配，更新回文半径: 如果当前回文的右边界超过了 mxmxmx ，则更新 ididid 和 mxmxmx 。 时间&空间复杂度 均为 O(n)O(n)O(n)，十分优秀。 例题1 这道题的主要思路就是马拉车+快速幂。 code: 例题2 这是一道比较难的题。 先预告一下：这道题中有一个技巧：在原串中插入字符后再在头尾各插一个别的字符充当边界。 接下来，题解开始： 我们处理出每个回文串的左右边界 ll[i]ll[i]ll[i]、rr[i]rr[i]rr[i]。 那么不难发现有： ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1)ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)\\ rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1) ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1) （这段可以自己画画图） 跑完 Manacher\tt {Manacher}Manacher 后，我们求出每个'#'为断点的 ll[i]ll[i]ll[i] 和 rr[i]rr[i]rr[i] ，其中 rr[i]rr[i]rr[i] 因为是 iii 结尾的回文长度，所以直接顺推，每往后移一位，最长回文子串长度 −2-2−2 ，于是 rr[i]=max(rr[i],rr[i−2]−2)rr[i]=max(rr[i],rr[i−2]−2)rr[i]=max(rr[i],rr[i−2]−2) ( i−2i−2i−2 是上一个'#'位置)，同理 ll[i]ll[i]ll[i] 直接逆推： ll[i]=max(ll[i],ll[i+2]−2)ll[i]=max(ll[i],ll[i+2]−2)ll[i]=max(ll[i],ll[i+2]−2) 。 最后枚举每个'#'为断点，更新答案即可 code: 例题3 如你所见，这是一道紫题，吓哭了。 但是我和题解区的一位大佬想到了同一个解法： 直接枚举一下每个处理出的回文是不是两段一样的回文相加不就好了？ 具体实现：在 Manacher\tt {Manacher}Manacher 中 mxmxmx 更新时,判断所有新出现的回文串的前一半是否为回文串即可。。。 然后就…… code: 嗯 例题4 这题洛谷上没找到，我觉得是紫 大致思路：Manacher\tt ManacherManacher+贪心区间覆盖 code： 留道拓展题吧 你猜为啥是拓展题，因为我也不会。 谁做出来了私信一下我哈。 孩子们我们没救了！题解区怎么全是FFT啊吓哭了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完结撒花！ 四蓝三紫，不知道要吓哭多少人\TINY 四蓝三紫，不知道要吓哭多少人四蓝三紫，不知道要吓哭多少人