[dog]

互动｜期末玄学许愿指南

🎒 期末倒计时！你的玄学能量储备好了吗？ 在刷题、背诵、焦虑、抓狂的边缘反复横跳…… 别怕！期末许愿池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

CXXP#1赛前预告帖

比赛介绍 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 这里是 C++Pippi#1 （简称 CXXP#1 ）比赛。 * 本场比赛时间为 202620262026 年 222 月 161616 日 8:008:008:00 ∼\sim∼ 202620262026 年 222 月 181818 日 12:0012:0012:00，共 222 天 444 小时 ，由于时间不短，不建议打满。 * 本场竞赛题目很简单，大约在红~绿，欢迎各位来玩，题目详细信息见题目信息。 * 本次竞赛采用 ACGO 赛制，实时可见排名。 * 本场比赛不计入 ACGO 等级分，请放心参与。 * 鸣谢各位参赛者参赛，各位工作人员出比赛，审核员审核，xmw 提供 ACGO ，尚弟提供世界。 * 赛后补题 出题组信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次比赛出题组成员： * 题目主要负责人：亚洲卷王 * 出题人：亚洲卷王，忘川秋库，🥥 * 验题人：PPX|AndyCGM/，yaonainai，复仇者_澜（中途退出），AC是最好的，Cocacola * 数据人：复仇者_零（中途加入） * 审题人：Xylophone（中途加入），༺ཉStars_Seekerད༻（中途加入） 除 AC是最好的外，其余人均达到了 奖项认证/铂金段位 条件。AC是最好的已向管理组报备。 出题组非必要不要在赛时提交代码。 以下用户因为见过题目或提前为下次竞赛提前加入出题组而不得参赛： * priority（不加团队）（下次竞赛出题者） * 滚蛋吧c++（中途加入又中途退出） 题目信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次竞赛所有题目时间限制均为 1000ms1000ms1000ms ，空间限制均为 128MB128MB128MB ，每题中的每个测试点均等分，每题满分 100100100 分 题目序号 题目idea来源 实际出题人 测试点数量 难度 题型 T1 忘川秋库 忘川秋库 101010 入门 传统 T2 🥥 🥥 505050 普及- 传统 T3 忘川秋库 亚洲卷王 & 忘川秋库 505050 普及/提高- 传统 T4 亚洲卷王 亚洲卷王 202020 普及+/提高 传统 相关链接 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 竞赛综合帖 * 赛前预告帖 * 赛时答疑帖 * 题解与总结 广告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 李总博客网站，欢迎注册账号 * 加入 CXXP 公开赛出题组要求见此处，有意愿且符合要求的私信忘川秋库 * 待定，等一个金主来 奖品信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 快速 AK 变换 * 在开赛 30min30min30min 内，首个 AKer\texttt{AKer}AKer 送出 222 个盲盒 + 随机 222 块拼图 + 111 个吧唧（如无在 30min30min30min AKer\texttt{AKer}AKer 则取消此奖励） * 由于题目不难，排行榜前 333 且 AK\texttt{AK}AK 的送出 111 个盲盒 + 随机 222 块拼图 + 111 个吧唧（如榜前三不是 AKer\texttt{AKer}AKer 则取消此奖励） 一血 * 每题首杀获得 111 个盲盒 + 111 个吧唧 不幸中的不幸 * 所有题目均有 80 pts80~pts80 pts 以上且没有 111 题通过获得随机 111 块冰箱贴 万幸中的万幸 赛后执行此代码，被抽中的对应排名获得随机 111 块冰箱贴，若作弊则取消该奖项。 题解奖 * 让有奖项认证的出题人看到的符合要求的题解之创作者，可以获得奖品（待定）。 作弊者的新年礼物 * 作弊者会受到至少 333 天的禁言作为奖励。 所有奖项允许叠加，作弊顺延，如果报名人数超过 100010001000 且有提交人数超过 600600600 会补上一些有价值的奖品。 注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 如果发现比赛有原题或其他影响公平性的因素，请私聊管理员和出题人，而不要以任何方式公开，违者视影响可能会得到取消成绩或禁言的惩罚。 * 因为是新年期间的竞赛，赛时的答疑可能不及时，但一般情况下看到了就会进行答疑。 * 不给予直播讲解，提供文字题解与赛后补题。 关于作弊 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 审核方式 CXXP 赛事的作弊审核与传统的方式不相同，我们会将每个选手的 444 道题的代码随机选择 1∼41\sim 41∼4 份代码进行抽查，即每个选手的代码都会被审核者看到。 主要的作弊方式有： * AI 辅助答题（A） * 大小号答题（B） * 代码辱骂（C） * 调戏反作弊机制（D） * 赛时讨论做法（E） * 赛时灌水（F） * 索要、套取他人代码或思路（G） * 负责人觉得就是作弊了（S） 申诉机制 若初审被认定作弊，可以申诉，但申诉人必须满足以下条件之一： 1. 提交参赛全程的全屏录制视频，视频内容须清晰展示整场比赛完整操作过程，且画面可辨识参赛者身份及操作界面。视频可以在 BiliBili 等视频网站上传、也可以提交百度网盘等网盘链接； 2. 由 CCF 认证不小于 888 级的用户代为提交申诉，须充足理由； 3. 自身的 CCF 认证不小于 666 级，须充足理由； 4. 明显不是作弊行为的：出题人提交选手代码、或者代码中直接复制题面等情形。 任何用户仅可进行一次申诉，申诉一旦失败则在 ACGO 公示选手代码进行众裁。申诉成功撤销记录。 公示机制 一旦被认定作弊一次，即公开名单、取消奖品且不可再在 CXXP 系列赛事中获得奖品，哪怕写检讨也仍然禁赛。

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 四蓝三紫，不知道要吓哭多少人四蓝三紫，不知道要吓哭多少人

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

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

【GeOI-M1】赛时答疑帖

奖金 3.36 RMB！ 【GEOI-M1】赛时答疑帖 比赛基本内容 这里是 2026 GeOI Math Round 赛时答疑帖，你可以在此处提出问题或报名比赛，比赛时间为 2026/1/16 12:00 至 2026/2/26 00:00。 这里是 比赛链接，邀请码为 HXmj。 这里是 作弊名单，第一周每日更新，剩余时间三日更新一次。 答疑情况 * T2 没有错误数据 赛时公告栏 截止于 2026/1/17 6:32，比赛报名人数 333，有分人数 111，AK 人数 000，rk1 为 未知（该用户为作弊者）、250 分。 信息 * [2026/1/16 13:06] 验题完成 * [2026/1/16 18:26] 未知 （该用户为作弊者）首杀 A 题！