数学是新一代把妹王

求此题题解

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

互动｜期末玄学许愿指南

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

码上开聊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社区不仅是他的“练功房”，更是激发他从参与者成长为贡献者的舞台。面对未来更艰险的省选之路，他已准备好向蓝紫黑题发起新一轮冲锋。这份源于热爱的专注，或许正是他一路“稳”下去的最大底气。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击回顾往期访谈 >>

【GeOI-M1】赛时答疑帖

奖金 3.60 RMB！ 【GEOI-M1】赛时答疑帖 比赛基本内容 这里是 2026 GeOI Math Round 赛时答疑帖，你可以在此处提出问题或报名比赛，比赛时间为 2026/1/16 12:00 至 2026/1/31 00:00，剩余时间为赛后补题，不计入获奖名单。 这里是 比赛链接，邀请码为 HXmj。 这里是 作弊名单，第一周每日更新，剩余时间三日更新一次。 答疑情况 * T2 没有错误数据 赛时公告栏 截止于 2026/1/17 19:50，比赛报名人数 303030，有分人数 888，AK 人数 000。 信息 * [2026/1/16 13:06] 验题完成 * [2026/1/18 00:21] 恭喜 @𝓐𝓘𝓮𝓻 首杀 A 题！

堆学习笔记

叠甲： > 本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。 堆及堆的性质 > 堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。 > > 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．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 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 超市 题目大意： 超市里有 NNN 件商品，每件商品都有利润 pip_ipi 和过期时间 did_idi ，每天只能卖一件商品，过期商品不能再卖。 求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。 其中 N≤2×105N\leq 2\times 10^5N≤2×105。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本题有两种做法，一种是采用贪心的策略，但是可能会爆。所以我们用堆。 先预处理所有商品，构建一个结构体并按照过期时间进行排序。 建立一个小根堆（这里采用 STL 容器的方式）。由于一天只能卖一个商品，所以堆的大小就是卖商品的天数。如果当前的商品过期天数与当前卖商品的天数相等，我们就看堆顶的那件商品（因为是小根堆，所以这件商品的收益肯定最小）的收益，如果比这件商品小，我们就替换掉。否则直接添加至堆中即可（因为已经排过序了）。 CODE

《关于我想写一篇关于ACGO的史记》

666上榜了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最近闲得慌想写一篇关于acgo这个网站从上线到现在发生的大事件的合集，编成一部“史书”，各位dalao能帮我提供一些大事件吗，越大越好的那种 目前已知：25.8.15反动书事件，25.9.15左右的芙宁娜&滚C事件，25.10月左右的和平宣言事件，26.1.14ACGO第一届嘻哈赛开始报名，26.1.15开始竞赛

CCF GESP 12月3级考试游记

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

# 官方题解 | 欢乐赛#64题解

官方题解 | 欢乐赛#64题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的土豆脑袋 入门 T2 皓仔和奶茶 入门 T3 皓仔的水果筛选 入门 T4 皓仔的指令执行 入门 T5 皓仔的累乘 普及- T6 皓仔的美丽子矩阵 普及- T1 皓仔的土豆脑袋 题目大意 直接输出一行语句 Potatoes are amazing!。 题解思路 直接使用 cout 进行输出即可。 参考代码 T2 皓仔和奶茶 题目大意 皓仔买了 aaa 包红茶和 bbb 盒牛奶来自己煮奶茶喝。 已知煮一锅奶茶需要 222 包红茶以及 333 盒牛奶， 请问皓仔手头的原料可以煮多少锅奶茶。 题解思路 可以煮的奶茶数量同时取决于红茶数量和牛奶数量。 aaa 包红茶可以煮 a/2a / 2a/2 锅奶茶， bbb 盒牛奶可以煮 b/3b / 3b/3 锅奶茶，因此最终实际上可以煮的奶茶数量应当是二者之间的最小值 min(a/2,b/3)min(a / 2, b / 3)min(a/2,b/3)。 参考代码 T3 皓仔的水果筛选 题目大意 nnn 个苹果的重量分别为 a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1 ,a2 ,⋯,an ， 现在皓仔将第一个苹果的质量 a1a_1a1 设定为本次出售的苹果重量基准值，重量和 a1a_1a1 差距不超过 555 的苹果都可以一起打包出售， 问皓仔这次可以出售多少个苹果？ 题解思路 题目要求苹果质量和第一个苹果的差距不超过 555, 那么可以使用绝对值表示差距: abs(a[i] - a[1]) <= 5。 或者根据数字的大小范围来判断： a[i] >= a[1] - 5 && a[i] <= a[1] + 5 遍历整个数组，每次发现符合条件的数字，则答案加一，最后输出答案即可。 参考代码 T4 皓仔的指令执行 题目大意 对于一个数字 xxx, 执行 nnn 次指令，在每次执行之后对 202601012026010120260101 取模。 对于每一条指令，令 sumsumsum 为指令内所有字符的 ASCIIASCIIASCII 码的总和， 如果 sumsumsum 是一个奇数， 那么令 x=x2x = x^2x=x2， 否则 x=2×xx = 2 \times xx=2×x。 题解思路 循环 nnn 次输入所有的指令，本题中对于每一条指令，我们遍历字符串内部的所有字符，计算得到总和之后，根据数字是奇数还是偶数来执行对应的指令： 如果 sumsumsum 是一个奇数， 那么令 x=x2x = x^2x=x2， 否则 x=2×xx = 2 \times xx=2×x，每一次操作之后将数字对 202601012026010120260101 取模。 参考代码 T5 皓仔的累乘 题目大意 皓仔计算从 111 累乘到 nnn 的结果，但他会避开他不喜欢的数字：凡是数位中包含数字 aaa 或 能被 aaa 整除的所有数，一律跳过不进行累乘。 题解思路 循环嵌套练手题，外层循环首先从 111 到 nnn 进行枚举，在内层需要进行数位分解，判断数字的数位是否含有 aaa。 如果当前数字既不是 aaa 的倍数，也不含有数字 aaa, 那么将其进行累乘，注意每一次需要将答案对 1e9+71e9 +71e9+7 取模。 参考代码 T6 皓仔的美丽子矩阵 题目大意 皓仔把一个子矩阵称为美丽子矩阵，当且仅当这个子矩阵的行数和列数都大于 111, 并且该子矩阵的四个角（左上、右上、左下、右下）格子的颜色完全相同。 现在请你帮助皓仔统计：在整张画布中，一共有多少个美丽子矩阵？ 题解思路 本题是一个子矩阵枚举的模板练习，当我们想要枚举子矩阵时候只需要做两件事情：枚举左上角的点，再枚举子矩阵右下角的点。 首先编写两重循环 i→[1,n],j→[1,m]i \rightarrow [1, n], j \rightarrow [1, m]i→[1,n],j→[1,m]枚举左上角的点 (i,j)(i,j)(i,j)。 注意右下角的点 (t,k)(t, k)(t,k)，坐标需要大于等于左上角的点，因此枚举起点为 (i,j)(i, j)(i,j)， 则枚举范围为 t→[i,n],k→[j,m]t \rightarrow [i, n], k \rightarrow [j, m]t→[i,n],k→[j,m]。 对于每一个子矩阵，判断四个角颜色是否一致，是的话答案加一。最后输出答案。 参考代码

语文是个人物

上过榜就行，有过辉煌！\COLOR{RED}{上过榜就行，有过辉煌！}上过榜就行，有过辉煌！ 前引 话说分久必合，合久必分，正如那时涨时落的成绩单，令人时而心碎，时而欢喜，而我，正如成绩的汪洋大海中的小鱼儿，不知所措，我欲吐出心得，与人们谈论实际在装 2025年终大总结，欢迎收看！ 真话 真无语了，这成绩真的无语，我将从多处细说。榜前五就我帖不是Ac君发的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 仅有一秒的巅峰 语文这玩意啊，我以前作文不错，还是经常得优，还上台读过我的范文，但我发现人老还真的不中用了；一到四年级，就破防了，一点不会，还拿过81的高分，但是——这四上期末模拟卷，直接开挂，我语文直飙95以上，连续四次第二，又三次第一，爽歪歪！ 四下，我意识到有90多分很不错了，不用奢侈95了，自己也稳定在90~95分，还不错。 本学期也就是五上，我才真正意识到啥叫过山车。第一单元没考作文，和同学们对完答案，不错，试卷有两张，一张大的（四面）和小的(两面)，牢湿在纸上登两面纸成绩，同学说了扣的分数，我欣喜若狂，因为： 哈哈哈！结果老师跟针对我一样和同学说：“吵什么？这张试卷只有陈**（我名字）一分没扣！” 然后写作文，30分我拿到了25分的好成绩，总分95分，我同桌作文减2分，96压我一分。呃啊！其实也不错！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 破防之时 第二单元就完了，我表面沉稳，心里激动，想在拿第一，冲上90分儿。结果天塌了，87！我们班曾经的学委，还有我们班长兼以前班三都有90及以上，一个91.5，还有一个90，旧时学委是我的竞争对手，完蛋！我作文又扣4分，阅读也扣了4分，基础减5分儿！六百六十六，“（橙子）吐血，崩于校。” U3更唐，79！作文22。好吧，我破防了！我们班的一个数学84的姐92，还有个91。 U4倒是回暖，87分，不过还是没比过数学84的**姐，她还在装：“菜！老娘又90多！” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 回升登王位，再度踢旧主 期中封神，93，班五左右，直接分解**姐，把她王座踢了，有个答案姐95，顾名思义，有答案，也是封神了。第五单元她84，姐81，活该 我94.5，班一，作文29，同桌抄我94，抄过头了吧 第六单元94，再次班一，（基础减5分这件事），登上王座！社团同学潘76.5，牢湿查违禁物品查出了10多样。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第七单元90，第四，第一91，第二90.5，w𝓪𝓷gliuju𝓷y𝓲90.5，背刺我！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 幕后 本文仅供娱乐，无起战之意，将持续更新。 谢谢！不考写不了啊 文采不够，请提出建议。成绩这样文采哪会有多好 我们牢湿天天说讲空话的人，阴阳怪气：“成绩能好吗？”我常讲空话，但很难被发现。 第七单元要考了，怎么办？求意见。 新作品我的校园生活，看看我新帖吧，点个赞，评个论，求求了！ 我与w𝓪𝓷gliuju𝓷y𝓲合作写我的校园生活系列，毕竟是同学。 w𝓪𝓷gliuju𝓷y𝓲新帖

#创作计划# 最小表示&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 四蓝三紫，不知道要吓哭多少人四蓝三紫，不知道要吓哭多少人