*天梯卡关*

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

互动｜期末玄学许愿指南

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

我把ACGO写到作文里被老师表扬了！！！

666，又榜3了!!!! 感谢AC君的嘉年华！！！！！！ 事情是这样的： 主包的语文老师要我们写一篇作文，主包脑子顿时想到了一个坏坏的想法书呆子书呆子书呆子 第二天早上，主包的作文收上去了，意想不到的是，下午的语文课上，语文老师直接狠狠地表扬了主包 “天宇同学的作文很好！！！ 作文用一个故事很好的描写了ACGO社区的有趣之处，简直是精彩绝伦啊！！！“ 互动方式 小彩蛋： 要是上榜主包直接发ACGO的作文！！！！！！！ 对了，在这里祝大家马年大吉 事事如意！！！

元旦放假日记

null

LHCX Cup 2026 赛时公告帖

返回目录 比赛严禁作弊！ 赛事讨论须知 * 赛前，你可以发布一些灌水内容； * 赛中，你只能发布与题目有关的内容，不得涉及解法、思路等； * 赛后，你可以与其他人一起探讨题目做法、思路。 赛事公告帖 * LHCX Cup 2026（邀请码：Rped） 讨论处罚 按照岚核团队#等级制度处理并发布作弊信息在获奖通知帖中。

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

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

语文是个人物

上过榜就行，有过辉煌！\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𝓲新帖

GESP ~1-8级考纲核心考点总结

GESP 1−8级考纲核心考点总结\Huge{GESP ~1-8级考纲核心考点总结}GESP 1−8级考纲核心考点总结 一、GESP 1级（入门启蒙） 1. 核心目标 掌握编程基础概念，能编写简单顺序结构程序，理解计算机基本运算逻辑。 2. 基础语法 * 变量：变量定义、赋值（数值型、字符串型），变量的基本使用 * 输入输出：简单输入（键盘输入数值/字符串）、输出（屏幕打印结果） * 基本运算：算术运算（+、-、*、/、%）、关系运算（>、<、==、!=） * 编程语言：C++，熟悉Dev-C++等考试指定编程环境操作，掌握基本代码框架（#include <iostream>、using namespace std;、main函数结构） * 变量：变量定义、赋值（int、float、char等基本类型），变量的作用域基础（局部变量） * 输入输出：cin（键盘输入）、cout（屏幕打印）的基本使用，了解endl换行符 * 基本运算：算术运算（+、-、*、/、%）、关系运算（>、<、==、!=、>=、<=），运算符优先级 3. 程序结构 仅考查顺序结构，无分支和循环；能按步骤完成简单任务（如计算两数之和、字符串拼接）。 4. 实战题型 数值计算（如计算长方形面积、简单加减乘除）、字符串处理（如拼接姓名和问候语）、简单变量赋值与输出。 二、GESP 2级（基础进阶） 1. 核心目标 掌握分支结构，理解循环的基本概念，能编写简单分支程序解决实际问题。 2. 基础语法拓展 * 分支结构：if语句、if-else语句，能根据条件执行不同代码块（如判断奇偶性、比较大小） * 分支结构：if语句、if-else语句、if-else if-else语句，能根据条件执行不同代码块（如判断奇偶性、比较大小） * 逻辑运算：逻辑与（&&）、逻辑或（||）、逻辑非（!），组合条件判断（如多条件筛选） * 字符串基础：char数组存储字符串，字符串长度计算（strlen函数），字符串的简单输入输出（cin、cout或puts、gets） 3. 程序结构 重点考查分支结构，初步接触循环概念（不考查循环编写，仅了解循环的作用）。 4. 实战题型 条件判断（如判断成绩是否及格、判断闰年）、简单逻辑组合（如判断是否为三位数且是偶数）、字符串基本处理（如统计字符串长度）。 三、GESP 3级（循环入门） 1. 核心目标 掌握循环结构，能编写循环程序解决重复执行的任务，理解数组（列表）的基本概念。 2. 核心语法 * 循环结构：for循环（固定次数循环）、while循环（条件循环），循环变量的初始化与更新，循环嵌套基础 * 数组：一维数组的定义、初始化、访问单个元素、遍历数组元素（循环遍历） * 循环控制：break语句（跳出循环）、continue语句（跳过本次循环）的使用场景 3. 程序结构 分支与循环的组合使用，能编写“分支+循环”的复合程序。 4. 实战题型 循环计算（如计算1到100的和、求n的阶乘）、数组遍历（如统计数组中偶数的个数）、简单重复任务（如打印菱形、输出乘法口诀表）。 四、GESP 4级（数组与函数基础） 1. 核心目标 熟练使用数组（列表），掌握函数的定义与调用，能通过函数封装代码逻辑。 2. 核心语法 * 数组进阶：一维数组的增删改查操作，二维数组的定义、初始化、访问（如矩阵的行数列数访问） * 函数：函数的定义（返回值类型、参数列表）、声明与调用，值传递，函数的嵌套调用，递归函数入门（简单递归逻辑） * 常用算法：简单排序（冒泡排序、选择排序）、查找（顺序查找），算法的C++代码实现 3. 实战题型 数组处理（如数组元素排序、查找指定元素位置）、函数封装（如编写求最大公约数的函数）、简单排序算法实现、二维数组应用（如统计矩阵中元素和）。 五、GESP 5级（字符串与算法进阶） 1. 核心目标 掌握字符串高级处理方法，熟练运用常用排序与查找算法，理解递归的基本思想。 2. 核心语法与算法 * 字符串进阶：char数组的高级处理（字符串拼接strcat、比较strcmp、复制strcpy），C++ string类基础（定义、赋值、字符串拼接、长度获取） * 算法进阶：插入排序、快速排序（基础实现），二分查找（有序数组适用），算法的时间复杂度基础认知 * 递归：递归的基本原理与递归出口设计，递归程序实现（如求斐波那契数列、阶乘的递归实现、汉诺塔问题入门） * 数据类型拓展：结构体（struct）的定义与使用，结构体数组（如存储多个学生信息） 3. 实战题型 字符串处理（如统计单词个数、判断回文字符串）、高级排序与查找实现、递归程序编写、结构体/字典应用（如存储学生信息并排序）。 六、GESP 6级（复杂算法与数据结构） 1. 核心目标 掌握基本数据结构（栈、队列、链表）的C++实现，能运用贪心、动态规划等复杂算法解决实际问题，理解指针的基本概念与使用。 2. 核心数据结构与算法 * 数据结构：栈（先进后出）的C++ 实现（数组模拟）、队列（先进先出）的C++ 实现（数组模拟）、单链表（定义、节点插入、删除、遍历） * 算法进阶：贪心算法（基本思想与典型应用，如活动选择问题、找零问题），动态规划入门（简单DP问题，如斐波那契数列的DP实现、爬楼梯问题） * 指针基础：指针的定义、指针与变量的关系（&取地址、*解引用），指针访问数组元素 3. 实战题型 栈的应用（如括号匹配、表达式求值入门）、队列的应用（如任务调度模拟）、单链表操作（增删改查）、贪心算法应用题、简单动态规划题、指针操作题与图的基本概念、存储结构、基础遍历等。 七、GESP 7级（高级数据结构与算法） 1. 核心目标 掌握复杂数据结构的C++实现与应用，熟练运用动态规划、图论基础算法解决问题，理解STL容器的基本使用。 2. 核心数据结构与算法 * STL基础：常用容器（vector向量、map映射、set集合）的基本使用（初始化、插入、删除、遍历） * 数据结构进阶：双链表、循环链表的实现与操作，二叉树基础（定义、遍历：前序/中序/后序遍历的递归与非递归实现） * 算法进阶：动态规划（经典问题，如最长公共子序列LCS、0-1背包问题），图论基础（图的存储：邻接矩阵、邻接表；图的遍历：DFS深度优先搜索、BFS广度优先搜索） * 指针进阶：指针与数组的关系，指针作为函数参数，指针数组基础 3. 实战题型 STL容器应用题、二叉树遍历题、动态规划经典题（LCS、0-1背包）、图的存储与遍历题（DFS/BFS）、指针进阶操作题。 八、GESP 8级（综合算法与工程化基础） 1. 核心目标 掌握综合算法的设计与实现，理解面向对象基础思想，能解决复杂编程问题，具备基本的代码优化意识。 2. 核心知识点 * 面向对象基础：类（class）与对象的定义，构造函数与析构函数，封装与访问控制（public、private） * 算法综合：图论算法进阶（最短路径：Dijkstra算法、Floyd算法；最小生成树：Prim算法、Kruskal算法），复杂动态规划问题（多重背包、区间DP入门） * 数据结构进阶：二叉搜索树（BST）的实现与操作，堆（大根堆、小根堆）的基础实现与应用 * 代码优化与工程化：常用代码优化技巧，异常处理基础（try-catch），程序的模块化设计（多文件编程基础：.h头文件与.cpp源文件） 3. 实战题型 图论综合题（最短路径、最小生成树）、复杂动态规划题、二叉搜索树操作题、堆的应用题、面向对象编程题（类与对象实现）、综合模块化编程题。 点赞破50出CSPJ/S\mathsf{点赞破50出CSP J/S}点赞破50出CSPJ/S

现有的数学体系被推翻了！

设有一个方程：x2+x+1=0x^{2}+x+1=0x2+x+1=0 可见x≠0x\neq0x=0 于是把方程变为x+1+1x=0x+1+\frac{1}{x}=0x+1+x1 =0 接着两式相减，左边减左边，右边减右边，变成： x2−1x=0x^{2}-\frac{1}{x}=0x2−x1 =0 两边同乘xxx 变成： x3−1=0x^{3}-1=0x3−1=0 一眼看出x=1x=1x=1 带入原式，12+1+1=31^{2}+1+1=312+1+1=3，3=0？

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