互动24｜# CSP人间真实

📌 #CSP人间真实# 👩‍💻 本周六就是 CSP 第一轮考试 了！考前和考后，你的真实状态是啥？ 📌 无论是： * 考前立下“AK”的flag * 考场翻车、写挂题目 * 还是考后灵魂出窍、只想躺平 * 这些都是真·CSP人间真实！ ✨ 参与方式： 直接评论分享你的当前状态。 😆 图文、表情包、段子、吐槽都可以！越真实，越容易戳中大家的笑点/泪点。 🎁 活动奖励： 随机抽取3名幸运之子送：ACGO定制笔 ⏰ 活动时间： 即日起至10月8日 👉 往期话题

CSP-J/S 2025游记（9.29更

9.29更 南开大学 & 快去写C++【合作赛#1】 邀请码：KPRR 加团（目前300人） AC君给我点赞置顶了！！！ 注：后续还会持续更新复赛模拟赛和准备 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY -3 今天洛谷的运势是大凶，555 初赛题目感觉没什么手感 DAY -2 今天打了场初赛模拟赛，蒙了十道选择题没一道对的…… 运气真的好差——但是 这会不会预示着我考试的时候能运气爆棚（俗话说，事情发展到最差的极点一定会触底反弹，往好的方向发展）？ 洛谷运势：凶（感觉比昨天好点？ DAY -1 洛谷运势居然达到了中平？逐渐上升的趋势？？ 今晚来打一场比较正式的模拟赛，也是2025年CSP初赛之前的最后一场比赛，希望能拿个好成绩，这样心里踏实点 85分！！！运气好起来了！！！ 晚上睡前再复习了一下重要的知识点，然后就早早睡觉了 DAY -0.5 比赛日早早的就醒了可能是生物钟的原因 打开洛谷发现今天的运势居然是中吉，太开心了！ 吃早餐之前又复习了一下所有重要易错的知识点，吃完早餐就准备去考试啦 DAY 0 CSP-J 比赛过程 上午考 J 组，下了雨，考场外面整个堵住了，只好步行500米到考场，辛亏身上没淋湿（假。。 然后进入考场（考场在一楼，很快就看到了）还有半个小时才开始考试，坐着真的好无聊（其实没过多久就发答题卡了） 这里插播一条很有趣的事情：这是我第一次去这个学校考试，所以找厕所找了好久，没想到在一个比较偏僻的角落里，来回一趟厕所裤子全湿了 考试开始，按照我的策略，先翻阅了所有的试题，发现阅读程序没什么太长的，太难的（假的，我阅读程序错了好多），就稍微放松了一点。 开始看第一题，32位？这不是 int 吗？比去年考得还简单，直接选 C！（然后就错了，没看到无符号。。 …… 做到阅读程序第二题时，我发现我好像不知道 unique 是什么东西，不管了随便算吧（事实证明，不知道 unique 还真的做不了，错误重灾区） …… 我终于在考试开始一小时十分钟时完成了所有题目，开始填涂答题卡（8分钟），顺便用15分钟把没做出来的题目又做了一遍，开始漫长的检查（说实话，这个检查还挺有用的，检查出了好几个错误），最后五分钟罚坐，自己感觉做的还行？（假 回家没有看答案，专心准备蒙一下下午的 S 组。 DAY 0 CSP-S 比赛过程 依旧是早早地到达考场，发卷啥的就不说了。 看题，选择题感觉还行？后面的就不用想了，直接有依据地蒙！ 判断题答案：AABBBBBBB（说明，其实后面六题我是有做出来对的，但是由于保险起见。。。（J 组的第二道阅读程序判断题全错，完美避开三个正确答案）），机智的我直接将后面两题所有答案全部蒙成 B（好像正确答案 A 更多，早就说蒙 A 了） 倒数第二道阅读程序感觉还挺简单？最后一道根本不知道在讲什么。。 插播：听说这次阅读程序第二题是什么“扔鸡蛋”的题目？ 其中程序中的一句话 仔细想想，感觉有点搞笑（在这里不细说… DAY 0 CSP 初赛赛后总结 测了一下分，J 82（完善程序全对换来的），S 65，感觉有点悬（有点心理阴影，J 去年就差了 1 分）… 按我的角度来看，今年的 J 组难度相较去年来讲稍微变难一点点；S 组相较去年简单一些。 预测分数线：J 70，S 58（仅仅是个人看法） 最后，大家考的怎么样，对分数有什么看法，欢迎留言！！ 注：从此处开始，接下来的时间将以复赛时间为标准 DAY -37 今天打复赛模拟赛。 难度写的是“普及”，实则是介于普及和提高之间 / 提高的难度（老师评价难度“懂的都懂”） 比赛开始，看题，题目都挺短，都挺难 第一题被硬控10分钟后发现是一道诈骗题，5分钟搞定！ 第二题没思路，去做第三题，发现会写50分的暴力（好耶！），30分钟完成。 接着写第四题dfs暴力，可以拿 25 分，这时发现 n≤20n \le 20n≤20 可以拿60分，脑海中闪过一个想法——打表！ 开始使用暴力进行打表，打到 n=18n=18n=18 发现打不下去了（电脑快爆了），果断放弃最后两个数。 第二题想到最后还是不会，只能乱写一个贪心，再输出个样例结束。 比赛结束，居然拿了 100+80+20+0=200 分！第二题的乱贪心拿了 80！第四题怎么爆零了？ 不管了，反正是rk13 DAY -36 查分日 今天出分数，J 83.5，S 65，跟估分差不多，希望能进复赛。 DAY -35 今天优先晋级分数线出来了，也是成功的两个组都稳进了，太开心了！！ DAY -34 上午依旧模拟赛，130分爆冷 下午 GESP，飞翔杯没打成（感觉这次人好少，官方下次能不能选个好一点的时间555） 最后，也祝大家 RP++ 考出好成绩！！

#创作计划#图论算法概述

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感谢AC君加精\tiny 感谢AC君加精感谢AC君加精 > UPD 9.28，应评论区大佬建议，增加了关键代码的注释。 本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的LCALCALCA MARKDOWNMARKDOWNMARKDOWN原码5318字，最终展示4000左右。 大家请坐稳，我们马上开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 1 最短路算法 最短路算法是图论中最基础的方法，在各大比赛中都有涉及，本篇将会提到4种最短路算法。 一、定义 最短路问题即求一个带权图中两个节点的最短的路径。 二、DIJKSTRADIJKSTRADIJKSTRA算法 1.简介 这是图论中最常用的最短路算法，由荷兰计算机科学家EdsgerW.DijkstraEdsger W. DijkstraEdsgerW.Dijkstra于195619561956年提出，其核心思想是贪心和广度优先搜索。它解决的是单源最短路问题。 2.核心思想 DijkstraDijkstraDijkstra算法的核心在于维护一个 distdistdist 数组， dist[i]dist[i]dist[i] 表示从起点到 iii 号点的最短路。 3.适用范围 非负权图，DijkstraDijkstraDijkstra算法每个点只松弛一次的特性决定了其无法解决负权问题。 4.朴素DIJKSTRADIJKSTRADIJKSTRA算法 * DijkstraDijkstraDijkstra算法将节点分为两类： 1. 已确定节点：已经找到从起点到该节点的最短路径的节点集合。 2. 未确定节点：尚未找到最短路径的节点集合。 * 算法流程： 1. 每次从 “未确定节点” 集合中，选择一个 距离起点最近 的节点。 2. 将其加入 “已确定节点” 集合。 3. 松弛 这个新确定节点的所有邻居。 * 松弛操作（也是该算法最重要的思想）： 检查对于新确定节点 uuu 的每一个邻居 vvv，如果从起点 sss 先到 uuu，再从 uuu 到 vvv 的路径距离，比之前已知的到 vvv 的距离更短，那么就更新 vvv 的距离。 * 核心代码： * 完整代码： * 时间复杂度：O(n2+m)O(n^2+m)O(n2+m)（一般写作O(n2)O(n^2)O(n2)） * 空间复杂度：O(n+m)O(n+m)O(n+m) 5.堆优化DIJKSTRADIJKSTRADIJKSTRA算法 * 区别于朴素做法的枚举每个可能松弛的节点，堆优化算法使用堆找到目前最近（最可能松弛）的节点。 * 代码： * 时间复杂度：O(mlogn)O(mlogn)O(mlogn) * 空间复杂度：O(n+m)O(n+m)O(n+m) * 注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。\color{red}{注意在稠密图中，堆优化算法会退化为O(n^2logn),此时应使用朴素算法。}注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。 6. 练习 三、FLOYDFLOYDFLOYD算法 1.简介 FloydFloydFloyd算法是一种基于dpdpdp的思想，是学生们最喜欢的一种基础最短路算法也是最慢的（竞赛中不常用） 2.核心思想 从节点 iii 到节点 jjj 的最短路径，无非有两种可能： 1. 直接从 iii 到 jjj。 2. 从 iii 经过某些中间节点 kkk 再到 jjj。 FloydFloydFloyd算法不断尝试和比较这些可能性，逐步优化最短路径的估计值（这也是该算法较慢的原因）。 3.适用范围 FloydFloydFloyd不适用于存在负权回路的图中。 4.FLOYDFLOYDFLOYD算法实现 * 状态定义： d[k][i][j]d[k][i][j]d[k][i][j]：表示从节点 iii 到节点 jjj，仅使用 1,2,⋯ ,k1, 2, \cdots, k1,2,⋯,k 号节点作为中间节点的所有可能路径中的最短路径长度。 * 状态转移方程： 对于每一个中间节点 kkk，我们检查对于每一对 (i,j)(i, j)(i,j)，是否存在一条更短的路径： d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]) d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j]) * 这个方程的含义： d[k−1][i][j]d[k-1][i][j]d[k−1][i][j]：不使用 kkk 作为中间节点，iii 到 jjj 的最短路径。 d[k−1][i][k]+d[k−1][k][j]d[k-1][i][k] + d[k-1][k][j]d[k−1][i][k]+d[k−1][k][j]：使用 kkk 作为中间节点，路径分解为 iii -> kkk 和 kkk -> jjj 两段，这两段路径只使用前 111 到 k−1k-1k−1 号节点作为中间节点。 * 取这两种情况的最小值。 * 代码（空间优化版）： * 时间复杂度：O(n3)O(n^3)O(n3) * 空间复杂度：O(n2)O(n^2)O(n2) 5. 练习 四、BELLMANBELLMANBELLMAN-FORDFORDFORD算法 1.简介 BellmanBellmanBellman-FordFordFord算法是另一种单源最短路算法，价值在于可以解决负权（回路）问题。 2.核心思想 BellmanBellmanBellman-FordFordFord算法的思想非常直接： 最短路径最多经过 n−1n-1n−1 条边。 如果一条从源点 sss 到终点 ttt 的最短路径经过了超过 n−1n-1n−1 条边，那么它必定包含一个环。如果是正环或零环，可以移除它得到更短的路径；如果是负环，则不存在最短路径。 基于这个思想，通过松弛操作对图中的所有边进行 n−1n-1n−1 轮遍历。每一轮遍历都尝试用一条边来更新和优化当前已知的最短距离。经过 n−1n-1n−1 轮后，理论上所有可能的最短路径都已经被找到。这时执行一轮松弛操作，还能有路径被更新，则证明图中存在负权回路。 3.适用范围 BellmanBellmanBellman-FordFordFord算法适用于所有情况 4.BELLMANBELLMANBELLMAN-FORDFORDFORD算法实现 * 初始化： 1. 将dist[s]dist[s]dist[s] 设为 000。 2. 将所有其他节点的 distdistdist 值初始化为 1e91e91e9。 * 进行 n−1n-1n−1 轮松弛： 1. 对每一轮，遍历图中的所有 mmm 条边。 2. 对于每条边 (u,v,w)(u, v, w)(u,v,w)，执行松弛操作： * 核心代码： * 如果需要检查负权回路，再额外进行一次对所有边的遍历（即第 nnn 轮松弛），如果发现任何一条边 还能进行松弛操作，就可以得出结论：图中存在从源点 sss 可达的负权回路。 * 注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。\color{red}{注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。}注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。 * 完整代码： * 时间复杂度：O(nm)O(nm)O(nm) * 空间复杂度：O(n+m)O(n+m)O(n+m) 5. 练习 五、SPFASPFASPFA算法 1.简介 SPFA（ShortestPathFasterAlgorithm）SPFA（Shortest Path Faster Algorithm）SPFA（ShortestPathFasterAlgorithm）是对于BellmanBellmanBellman-FordFordFord的队列优化版本，在随机图中时间更优，但容易被卡。 2.核心思想 我们发现，BellmanBellmanBellman-FordFordFord算法中，并不是每一次松弛操作都会有效，只有那些在前一轮松弛中成功更新了最短路径值的点，才有可能引领下一次有效的松弛。 SPFASPFASPFA 对此进行了关键优化： 使用一个队列来维护有可能引起松弛操作的点。只有当某个点 uuu 的最短距离 dist[u]dist[u]dist[u] 被更新变小了，才说明它的出边有可能使其邻居 vvv 的 dist[v]dist[v]dist[v] 也变小。这时，我们才将 uuu 放入队列，等待后续用它来松弛它的邻居。 这个过程避免了 BellmanBellmanBellman-FordFordFord中大量无用的松弛尝试，使其在平均情况下的时间复杂度远优于BellmanBellmanBellman-FordFordFord。 3.适用范围 SPFASPFASPFA适用于所有情况 4.SPFASPFASPFA算法实现 * 初始化： 1. 创建 distdistdist 数组，dist[s]=0dist[s] = 0dist[s]=0，其余为 INFINFINF。 2. 创建一个队列 qqq，将源点 sss 入队。 * 创建一个 in_queuein\_queuein_queue数组，标记节点是否已在队列中，防止重复入队。初始时，in_queue[s]=Truein\_queue[s] = Truein_queue[s]=True。 * (可选，用于检测负环) 创建一个 countcountcount 数组，记录每个节点的入队次数，初始为 000。 * 主循环：当队列不为空时 1. 从队首弹出一个节点 uuu，并标记 in_queue[u]=Falsein\_queue[u] = Falsein_queue[u]=False。 2. 遍历 uuu 的所有出边 。 3. 尝试对边 (u,v)(u, v)(u,v) 进行松弛操作。 * 代码： * 平均时间复杂度：O(km)O(km)O(km) 其中kkk是个很小的常数 * 最坏时间复杂度：O(nm)O(nm)O(nm) 在一些特殊数据，比如网格图中，会退化为BellmanBellmanBellman-FordFordFord * 空间复杂度：O(n+m)O(n+m)O(n+m) 六、小结 算法 DijkstraDijkstraDijkstra BellmanBellmanBellman-FordFordFord SPFASPFASPFA FloydFloydFloyd 类型 单源最短路径 单源最短路径 单源最短路径 多源最短路径 策略 贪心 动态规划 队列优化 动态规划 时间复杂度 O(mlogn)O(m log n)O(mlogn) O(nm)O(nm)O(nm) O(km)O(km)O(km) O(n3)O(n^3)O(n3) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) 负权边 ❌ ✅ ✅ ✅ 负环检测 ❌ ✅ ✅ ❌ 适用场景 非负权图 负权图 随机图 n<500n<500n<500 最佳情况 非负权图 负权图 随机图 n<500n<500n<500 最坏情况 无，均可用对应优化 稠密图 特殊图，例如网格图 小数据，大规模查询 实现难度 中等 中等 较难 简单 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 2 并查集 并查集是图论中一种基础算法，是最小生成树等算法的基础，本篇将会提到3种并查集。 一、定义 并查集是一种用于管理元素分组情况的数据结构。 二、朴素版 1.简介 并查集高效地支持以下两种操作： * 合并：将两个元素所在的集合合并为一个集合。 * 查找：查询某个元素是否在同一集合。 2.核心思想 并查集的核心思想在于用多棵树来表示集合。森林中的每一棵树代表一个集合，树中的每个节点对应一个元素，树的根节点就是这个集合的“代表”。 3.算法流程 * 初始化： 一开始，我们拥有nnn个元素。通常我们用一个数组 parentparentparent 来表示每个元素的父节点。 初始化时，每个元素都是自己的父亲，即每个元素自成一个集合，自己是自己那棵树的根。 * 查找 即查找元素 xxx 所在集合的根节点。方法很简单：不断地通过 parentparentparent 数组向上查找，直到找到那个父节点指向自己的元素（即 parent[x]=xparent[x] = xparent[x]=x），它就是根节点。 * 合并 即将元素 xxx 和元素 yyy 所在的两个集合合并成一个集合，主要有两个步骤： 1. 找到 xxx 的根节点 rootx=find(x)rootx = find(x)rootx=find(x) 和 yyy 的根节点 rooty=find(y)rooty = find(y)rooty=find(y)。 2. 如果 rootx=rootyrootx=rootyrootx=rooty，说明它们本来就在同一个集合里，无需合并。否则将其中一棵树挂到另一棵树的根节点下面。即让 parent[rootx]=rootyparent[rootx] = rootyparent[rootx]=rooty。 4.代码实现 * 单次操作时间复杂度：最坏O(n)O(n)O(n) * 空间复杂度：O(n)O(n)O(n) 5. 练习 三、按秩合并 1.简介 在朴素算法中，我们不难发现，在特殊数据下，树会退化为一条链，时间会退化为O(n)O(n)O(n)，无法满足需求，于是按秩合并应运而生。 2.核心思想 我们使用一个额外的数组 rankrankrank 来记录每个根节点所代表的树的“高度”的估计值（这就是秩）。 初始时，每个元素都是根节点，自己构成一棵高度为 000 的树，所以 rank[i]=0rank[i] = 0rank[i]=0。 注意：我们只维护根节点的rank值，非根节点的rank值没有意义。\color{red}{注意：我们只维护根节点的 rank 值，非根节点的rank值没有意义。}注意：我们只维护根节点的rank值，非根节点的rank值没有意义。 3.算法流程 * 在合并两个根节点 rootxrootxrootx 和 rootyrootyrooty 时： 1. 比较它们的秩（rank[rootx]rank[rootx]rank[rootx] 和 rank[rooty]rank[rooty]rank[rooty]）。 2. 将秩较小的树挂到秩较大的树下。 * 注意：如果两棵树的秩相等：任意选择一方作为新的根，并将新根的秩加 111。 * 为什么相等时要加 111？ 想象两颗高度均为 hhh 的树。当它们合并时，新树的高度至少为 h+1h+1h+1（将一颗树挂到另一颗的根节点下，整个树的高度必然增加 111）。 4.代码实现 这段代码请由各位自行完成(doge)。 5. 还是这道 四、路径压缩 1.简介 路径压缩是并查集中一种非常重要的优化技术，它在查找中实施，可以显著提高并查集的效率。 2.核心思想&算法流程 朴素算法通过递归查找根节点，而路径压缩指的是在递归返回的过程中，将路径上每个节点的父节点直接设置为根节点，这样，整个路径被"压缩"了，所有节点都直接指向根。 3.代码实现 这是朴素的findfindfind 这是路径压缩的findfindfind 完整代码： 5. 还是这道 6.复杂度分析 * 时间复杂度：并查集的时间复杂度分析比较特殊，它不是一个简单的 O(logn)O(log n)O(logn) 或 O(n)O(n)O(n)，路径压缩的时间复杂度是由一个增长极其缓慢的函数——反阿克曼函数 α(n)α(n)α(n) 来描述。至于这个函数有多缓慢呢？在n≤265536n ≤ 2^{65536}n≤265536 时，α(n)≤5α(n) ≤ 5α(n)≤5。所以路径压缩并查集的单次操作一般认为是O(1)O(1)O(1)的。 * 空间复杂度：O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 3 最小生成树 最小生成树是图论中一种基础方法，考试中会出现很多变体，本篇将会提到两种最小生成树算法。 一、定义 生成树是一个无向连通图的子图。它必须包含原图的所有顶点，但只包含足够形成一棵树的边，并满足以下三个条件： * 是连通图：所有顶点都连接在一起。 * 无环：图中不存在任何环路。 * 边数 = 顶点数 - 111。 最小生成树 就是在一个带权连通无向图中，所有可能的生成树里，边的权重之和最小的那一棵（或那几棵）。 二、KRUSKALKRUSKALKRUSKAL算法 1.简介 KeuskalKeuskalKeuskal算法是基于边的一种最小生成树算法，也是竞赛中最常用的一种。 2.核心思想 从小到大选择不会形成环的边，直到连接所有顶点。 3.算法流程 * 排序：将图中所有的边按权重从小到大排序。 * 初始化：创建一个空的集合用于存放最小生成树的边。 * 遍历：按权重从小到大遍历每条边： * 如果当前边连接的两个顶点不在集合的同一个连通分量中（即加入这条边不会形成环），则将这条边加入集合。 * 如果会形成环，则跳过。 * 终止条件：当集合中的边数等于顶点数减111时，算法结束。 * 如何判断是否成环？ 我们通常使用并查集来高效地判断两个顶点是否属于同一个集合以及把两个点的集合合并。 4.代码实现 * 时间复杂度：O(mlogm)O(mlogm)O(mlogm) * 空间复杂度：O(n+m)O(n+m)O(n+m) 5. 练习 三、PRIMPRIMPRIM算法 1.简介 不同于KruskalKruskalKruskal算法，PrimPrimPrim算法是基于点的一种最小生成树算法，比较慢。 2.核心思想 从一个顶点开始，每次选择与当前树相连的权重最小的边，并扩展这棵树。 3.算法流程 * 初始化： 1. 随机选择一个顶点作为起点，加入最小生成树集合。 2. 维护一个数组 keykeykey，记录每个顶点到当前最小生成树的最小权重，初始值为无穷大（起点为000）。 3. 维护一个数组 parentparentparent，记录每个顶点是由哪条边连接进来的。 * 循环扩展： 1. 从未被选择的顶点中，选择一个 keykeykey 值最小的顶点 uuu，将其加入树中。 2. 遍历顶点 uuu 的所有邻接顶点 vvv，如果边 (u,v)(u,v)(u,v) 的权重小于 vvv 当前的 keykeykey 值，则更新 vvv 的 keykeykey 值为这个权重，并记录 parent[v]=uparent[v] = uparent[v]=u。 * 终止条件：所有顶点都被加入树中后，算法结束。parentparentparent 数组就定义了最小生成树的结构。 4.代码实现 * 时间复杂度：O(mlogn)O(mlogn)O(mlogn)（不用优先队列的朴素版是O(n2)O(n^2)O(n2)） * 空间复杂度：O(n+m)O(n+m)O(n+m) 四、小结 算法 KruskalKruskalKruskal PrimPrimPrim 对象 边 点 时间复杂度 O(mlogm)O(m log m)O(mlogm) O(mlogn)O(mlogn)O(mlogn) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) 适用场景 稀疏图 稠密图 数据结构 并查集 优先队列 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 4 LCALCALCA—最近公共祖先 这是一个在树中非常常见且重要的问题，是许多其他高级问题的基础。 一、定义 字面意思对于一棵有根树中的两个节点 ppp 和 qqq，它们的最近公共祖先被定义为同时是 ppp 和 qqq 的祖先的节点中，深度最大的那个节点。 二、倍增法求LCALCALCA（暴力解法这里就跳过了） 1.简介 这是求LCALCALCA最常用的方法，用倍增的思想来向上“跳”。 2.核心思想 倍增法的主要思想是：任何整数都可以用二进制表示，那么从任何一个节点到其祖先的路径长度，也可以拆分为多个222的幂次方步长。我们预先计算好每个节点向上跳 2k2^k2k 步会到达哪里，查询时就能快速向上“跳”，而不需要一步一步走。 3.算法流程 * 预处理： depth[i]depth[i]depth[i]：记录每个节点 iii 的深度。 up[i][j]up[i][j]up[i][j]：这是核心的倍增表。它表示从节点 iii 开始，向上跳 2j2^j2j 步后，所到达的祖先节点。 这两个数组均可在dfsdfsdfs中通过递推实现。 depthdepthdepth就不说了，我们重点讲解upupup，注意到从 iii 点跳 2j2^j2j 步 === 先从 iii 点跳 2j−12^{j-1}2j−1 步到一个中间节点 midmidmid，再从 midmidmid 节点跳 2j−12^{j-1}2j−1 步，由此，up[i][j]=up[up[i][j−1]][j−1]up[i][j] = up[ up[i][j-1] ][j-1]up[i][j]=up[up[i][j−1]][j−1]，这样，我们可以用已经计算好的 第j−1j-1j−1 层的信息，来构建第 jjj 层的信息。 * 查询 1. 深度对齐：首先，确保两个节点 uuu 和 vvv 处于同一深度。假设 depth[u]>depth[v]depth[u] > depth[v]depth[u]>depth[v]，我们需要把 uuu 往上提。计算深度差 d=depth[u]−depth[v]d = depth[u] - depth[v]d=depth[u]−depth[v]。将深度差 ddd 看作一个二进制数，利用倍增表快速提升 uuu。 2. 检查是否同一节点： 如果此时 u=vu =vu=v，那么这个点就是LCALCALCA，直接返回。 3. 同步攀升：如果深度对齐后 uuu 和 vvv 不同，则让它们一起向上跳，从最大的步数 k=20k = 20k=20 开始尝试，向下递减，如果 up[u][k]!=up[v][k]up[u][k] != up[v][k]up[u][k]!=up[v][k]，说明这个祖先还不是公共的（还没越过LCALCALCA），我们就可以安全地将 uuu 和 vvv 同时向上跳 2k2^k2k 步，否则说明越过了LCALCALCA，不跳。 4. 经过第333步后，uuu 和 vvv 会停留在LCALCALCA的正下方的两个直接子节点上。因此，uuu 和 vvv 此时的父节点就是LCALCALCA，即 up[u][0]up[u][0]up[u][0]。 4.代码实现 * 时间复杂度：O(nlogn)O(nlogn)O(nlogn) * 空间复杂度：O(nlogn)O(nlogn)O(nlogn) OK啊，终于杀青了！打字不易，点个赞吧。 特别鸣谢@AAA混泥土批发PPL哥、@复仇者_帅童对于FLOYDFLOYDFLOYD算法的指正、@沈思邈对于一些细节的建议！

备考GESP，半退

祝我上南开 考GESP前一周内看状态请看头像： 1. 南开校徽 说明很无聊，非常想跟人说话，我一定会关注你。 2. 南开教学楼 说明在做题，尽量不要打扰我，我没时间回复你。 3. 开满海棠花的校园 说明在发癫，可以来跟我说话，我很高兴见到你。 4. 我是看南门的 说明在怼人，最好不要打扰我，我可能会误伤你。 5. 和小号同一头像 说明不在线，有事可私信留言，我上线就回复你。

世界上最恐怖的事情（会更新）

更新时间：2025年9月29日15:51:36\HUGE{更新时间：2025年9月29日15:51:36}更新时间：2025年9月29日15:51:36 感觉热度没了，要被刷下去了。放在这里了，我会持续更新的《初中开学日记》 大家可以吧经历过的事打在品论去O。如果都干过可以跳了。 1.刷牙的时候衣摆碰到洗手台上的水 2.光脚在家走的时候踩到乐高。 3.半夜起来水ACGO发现你的妈妈早就看着你了，而且你还不知道你麻麻是什么时候来的。 4.上学时在地上看到蟑螂，刚回头碰上大片树叶 5.看见一个很恐怖的虫子，突然发现腿痒痒的。 6.睡觉的时候发现墙上的光影在动。 7.当你早读偷偷读课外书的时候，发现你的老师不知道什么时候站在你身后 8.单人玩恐怖游戏时候房门被风吹上了。 9.在你没好好写作业时，听到门边传来脚步声 10.在墙上看到一直大虫子，一转身发现虫子不见了。。。 11.吃西红柿的时候西红柿皮粘在上牙床上扣不下来了（经常被这样干掉过）。 12.玩游戏的时候开了个小差，突然发现浮木在你身后，亖亖的瞪着你 13.开学第一天肉体没起，梦到灵魂起了。 14.深夜时分，突然有位几乎很少和你打电话的人给你打电话了 15.午夜，起床喝水发现家里的门莫名其妙的关了，而你记得家长从不关门，你也没关门就睡了，家长一直在睡...... 16.写作业拿手肘撞桌子,结果撞到麻筋 17.梳头梳下来一只蟋蟀 18.老师叫你和一个成绩很差的同学到他办公室 19.网络上有人叫你真名 or 现实中有人叫你网名 20.在跑操时踩到一个嘎嘣作响的东西 21.上学，梧桐树上突然掉一只绿色猪儿虫掉投稿人肩上。。。。。。。。。。。。。。。。。。 22.网上骂了个人，感觉很爽。结果突然发现是你爸爸的网名（ 23.刚上完厕所出门发现有一个同学手里舀着水朝你冲了过来。。。 24：不让发了 25.上编程课玩游戏，下课后麻麻看了一眼老师发的课堂评价 26.刷父母手机，不小心按到关机键，还不知道密码 27（这一条是对于Stars_Seeker的，排名1699的是我）： 28.补充：在学校里，黑板拉开是老师该学期的占课计划表，微机课和体育课壮烈牺牲 29.偷偷刷短视频，结果背后传来拍照声（细思鼻孔） 30.自信的写完一个大题，这是你写的最多字的大题。结果全错。而且答案上还是“略”。 31（在图书馆看同学打游戏见到的）.同学玩和平，地铁逃生。他为了给我们秀操作把各种七级甲，枪带上了。还花了4多万买物资。结果开箱的时候被狙了。装备掉了一地。。。 32.尺子掉到了地上（总所周知尺子掉地上就捡不起来了） 欢迎补充。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 彩蛋： 1.如果你怀疑晚上有鬼怎么办？ 首先你可以对着空气说一句“鬼，帮我关下灯”。如果灯没关证明没有鬼，如果灯关了，你也不用怕。毕竟鬼都帮你关灯了，这么有礼貌的鬼你怕啥QAQ。什么？你说鬼不想关灯怎么办？那你更不用怕了。这么懒惰的鬼，他都懒得吃你！ 2.如果你有一个娃娃，不管什么时候总会在每天的12:00出现在你家床头怎么办？ 非常简单。你把这个娃娃挂在某宝上，5块一个。如果有人买的话，发货过了一天它就自己回来了。然后你就可以继续卖了QAQ。 彩蛋2（讲个笑话）： 男：我们出去旅游吧。 女：不行，孩子刚出生。 男：wtf，我们俩认识5—6年了，你才认识这个孩子两天。 女：。。。 在哪个地方找的，忘了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 现在是2025年9月19日17:25:01。还在学校的我笑你一辈子%%%

获奖公告｜ACGO巅峰赛#25

获奖公告｜ACGO巅峰赛#25 ID 参赛者 礼品 3416957 @AK不了IOI 盲盒 + 定制吧唧 4740708 @fangz 盲盒 + 定制吧唧 1943184 @egogaming 盲盒 + 定制吧唧 4406908 @宋雨琦才是真神 盲盒 + 定制吧唧 3632312 @dream_陆军展览（不加团队） 盲盒 + 定制吧唧 2836360 @芙宁娜·德·枫丹 盲盒 + 定制吧唧 4679786 @2/3扣拿塔反思克拉波 盲盒 + 定制吧唧 1371791 @复仇者_天之神_银色子弹 盲盒 + 定制吧唧 1653365 @Xylophone 盲盒 + 定制吧唧 4763653 @CEGO.tyx 盲盒 + 定制吧唧 3971643 @忘川秋裤 盲盒 + 定制吧唧 🎁 获奖信息填写 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ⚠️ 赛事违规公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 89 名用户存在疑似 AI 生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，将在9月15日统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，将在9月15日统一 禁言 30 天； * 仅违规 1 次者不予展示。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 申诉机制 请在10月7日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。 本轮赛事审核志愿者：@复仇者_帅童 @dream_陆军展览（不加团队） 本轮赛事出题老师：@NoonMaple 本赛违规记录 名次 参赛者 ID 总分 理由 1 枫 5031884 520 T1-T6 AI 3 ‏‮™☯一合神星༻དༀ瞳ༀཌ༺ 4961547 520 T3-T6 AI 5 159****3660 4592666 516 T3-T6 AI 6 what！ 880830 516 T3-T6 AI 7 acidlemon 4817688 516 T3-T6 AI 8 yaonainai 4851507 516 T6 AI 9 183****1200 4372216 516 T3-T6 AI 10 ༺༒༻传奇大傻༺༒༻ 3580701 516 T1-T6 AI 11 TMP&MPX&烂 4366229 516 T2-T6 AI 12 我不是AC君 5081613 516 T2-T6 AI 14 狂拽魔神 3999499 516 T1-T6 AI 15 Scarlett2025 5156723 516 T1-T6 AI 17 eee 4673991 516 T1-T6 AI 18 AAA冰块批发AI哥 4978429 516 T1-T6 AI 19 ༺ཌༀཉི༒白·羊༒༃ༀད༻ 4955978 512 T3 AI 21 怪盗基德(互关，包回关，冲1k） #N/A 512 T1-T6 AI 22 玛薇卡 4527070 504 T5雷同 23 ༺ཌༀཉི༒元༒帅™༒༃ༀད༻ 4673370 504 T1-T6 AI 24 汁购蛙 4051525 504 T1-T6 AI 27 156****7371 5212969 500 T1-T5 AI 28 米家的狗 3300336 496 T1-T6 AI 29 Gold（有关必回） 4956019 490 T1-T5 AI 30 LOVEKlee1314 4326906 488 T1-T4，T6 AI，T5雷同 31 天之神_星河_枫原万叶 4958296 480 T1-T5 AI 32 A 4440554 476 T1-T6 AI 33 钟离在玩三角洲 4226363 472 T1-T6 AI 34 压~~力~ #N/A 471 T1-T6 AI 35 对方正在输入... 959560 460 T1-T6 AI 36 しゅんこう-小号 5165631 456 T1-T6 雷同 37 ༺དしゅんこ༒うTGHཌ༻ 1535745 456 T1-T6 雷同 38 ༺ཌༀཉི复仇者_金雨晗༃ༀད༻ 4958593 451 T1-T6 AI 39 复仇者_溱泪 3428625 449 T1-T6 AI 40 ZhangCxuan vOwOv 527747 443 T1-T5 AI 41 🥥 3621376 440 T3 AI 42 Avelina 2736262 435 T1-T5 AI 43 "orange"之父 3815071 435 T1-T5 AI 44 114514 5006148 426 T1-T6 AI 46 AC坤 4456314 419 T1-T6 AI 47 twitter 3318585 416 T1，T3-T6 AI 49 Crisit 4454967 412 T1-T6 AI 50 飞到绝技 #N/A 406 T1-T6 AI 51 杨曙宁 4740425 404 T1-T6 AI 52 古希腊掌管AC和WA的神 4747742 400 T1-T3 AI 53 无敌的鳖佬仔给老爷爷猜猜被 4252088 400 T1-T6 AI 54 「ด้้༺༻༺༻༺༻༺༻༺༻』 4683247 397 T1-T6 AI 55 盛翰祺 4926857 396 T1-T6 AI 56 你是不是喜欢c++ 4181234 396 T3 & T5 AI 57 一只人畜无害的狗 4722696 390 T1-T6 AI 58 比比和虎🐯🐅 4956149 390 T1-T6 AI 59 Pallas pit viper 4958310 389 T1-T6 AI 60 lyh 5144594 388 T1-T6 AI 61 yh26zhuenaf 2927399 384 T1-T6 AI 62 刘骋原 5014448 384 T1-T6 AI 63 ༺ཌༀ凌驾于你之上ༀད༻ 5140337 384 T1-T6 AI 64 暴力出奇迹，结果TLE 3719181 374 T2 AI 65 ༺ཌༀ死神·魔ༀད༻ 4787217 372 T1-T6 AI 66 ༺ཌༀ复仇者.叫我浅琪ༀད༻ 2901632 369 T1-T5 AI 67 米哈游 4615250 368 T1-T6 AI 68 IN Hacker(彻底黑化) 4787172 364 T1-T6 AI 69 粉丝一号 4384206 363 T1-T6 AI 71 ≥~≤ #N/A 355 T1-T5 AI 72 瀚高祖 4787141 354 T1-T6 AI 73 c++..... 4278985 345 T3 AI 74 1234567 1015995 345 T1-T4 AI 75 帅帅(有关必回) 4763628 344 除T3，T6 外AI 76 1145141919810二年级 5137945 340 除T3，T6 外AI 77 复仇者_孔明_仲达（定回关） 4742959 340 除T5外AI 78 ༺ཌༀཉི༒天·龙༒༃ༀད༻ 3869215 340 T1-T6 AI 79 临渊者__sheng（已复活） 4739854 335 T1-T6 AI 80 yjynb666 5148234 330 T5&T6 AI 81 AAA忘川秋库的秋裤批发哥 4419090 324 T1-T6 AI 82 yh24-oi-cym 1779364 323 T4-T6 AI 83 善 4770910 320 T3-T6 AI 84 天之神——集训营一小只 4724944 319 除T3外AI 85 AC酱 4471932 317 T1-T6 AI 86 咕咕咕 1975597 316 T4 AI 87 北辞 3310550 310 T3 AI 88 鹿王-蔡锡龙 1159069 309 T1-T5 AI 89 蔡栋旭 113室 老登 4323608 305 T1-T5 AI 90 天之神_复仇者_ZDZC 4787374 301 T1-T6 AI 91 老骥 4881054 300 T1 AI 92 player 4649646 300 T1 -T3 AI 93 158****4378 1714307 300 除T1&T5外AI 95 🕈.👎.☝✌💧❄☜☼ 774357 293 T1-T6 AI 96 ‌NovaBlade 1915048 291 T1-T5 AI 97 Ajax 3634791 288 除T2以外 AI 98 我的世界老玩家（互关，专攻难题） 4963362 282 T1-T6 AI 99 Srobot 4997640 280 T2 AI 100 ༺ཌༀ复仇者_和平的凡人ༀད༻ 4326855 279 T1-T6 AI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📎 ACGO 官方赛事公平审核规则

#创作计划#KMP算法精讲

前言： 本文涵盖KMPKMPKMP算法的详细步骤，大家有什么建议可以在评论区说哦！ 加精啦！！！感谢AC君赞助！！！ 竟然榜7了！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广告： 求加团！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 目录（CONTENTS）： > > > > 第一部分：导言 > > > > > > 第二部分：什么是 KMP 算法 > > > > > > 第三部分：KMP 算法的核心概念与预处理 > > > > > > 第四部分：KMP 算法的匹配过程与实现 > > > > > > 第五部分：刷题时光 > > > > > > 第六部分：常见踩坑点与避坑指南 > > > > > > 第七部分：常见问题与注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第一部分：导言: 在字符串处理场景中，我们经常需要解决 “模式匹配” 问题 —— 比如从一篇文章里找某个关键词、在日志中匹配特定指令，这时候最直接的思路是 “暴力匹配”：用模式串的每个字符依次对比主串的对应位置，不匹配就回溯主串重新开始。 但暴力匹配效率极低，比如主串是"AAAAA...A"（1000 个 A），模式串是"AAAB"，每次匹配到最后一个字符才失败，主串频繁回溯导致时间复杂度达到O(N*M)（N 为主串长度，M 为模式串长度）。 为此，我们需要更高效的算法 ——KMP 算法。它通过预处理模式串生成 “部分匹配表”（PMT），避免主串回溯，将时间复杂度优化到O(N+M)，是字符串匹配的经典高效方案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：什么是 KMP 算法： KMP 算法由 KNUTH、MORRIS 和 PRATT 三位科学家共同提出，核心思想是利用模式串自身的前缀后缀匹配信息，在匹配失败时让模式串 “少后退”，从而跳过不必要的对比步骤。 核心问题：为什么暴力匹配效率低？ 假设主串为S = "ABCABDABCAB"，模式串为P = "ABCAB"： > ·暴力匹配时，前 4 个字符 "ABCA" 均匹配，第 5 个字符 S [4] = 'X'（此处替换为与 'B' 不匹配的字符，如 'X'）与 P [4] = 'B' 不匹配，此时主串会回溯到 S [1]，模式串回到 P [0] 重新开始。 > ·但观察模式串"ABCAB"，其前 4 个字符"ABCA"的前缀"A"和后缀"A"是最长匹配的（长度 1）。这意味着主串中S[3] = 'A'（对应模式串P[3] = 'A'）其实可以直接与模式串的P[1]继续匹配，无需回溯主串。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分：KMP 算法的核心概念与预处理： 在学习 KMP 的实现前，必须掌握两个核心概念：前缀后缀和部分匹配表（PMT）。 3.1. 前缀与后缀： > ·前缀：字符串中除最后一个字符外，所有以第一个字符开头的连续子串。例："ABCAB"的前缀为["A", "AB", "ABC", "ABCA"]。 > ·后缀：字符串中除第一个字符外，所有以最后一个字符结尾的连续子串。例："ABCAB"的后缀为["B", "AB", "CAB", "BCAB"]。 > ·最长公共前缀后缀（LCP）：前缀和后缀中长度最长的相同子串。例："ABCAB"的 LCP 为"AB"，长度为 2。 3.2. 部分匹配表（PMT）： 部分匹配表（也称NEXT数组）是 KMP 的核心，它存储了模式串中每个位置的前缀子串的 LCP 长度。 > ·下标：模式串的字符位置（从 0 开始）。 > ·值：该位置前的前缀子串（即P[0..I-1]）的 LCP 长度。 如何构建 PMT（以模式串P = "ABCAB"为例）： 模式串字符 p[0] = 'A' p[1] = 'B' p[2] = 'C' p[3] = 'A' p[4] = 'B' 前缀子串 空串 "A" "AB" "ABC" "ABCA" LCP 长度 0 0 0 1 2 PMT 值 0 0 0 1 2 构建 PMT 的代码实现： 核心逻辑：用双指针I（指向后缀末尾）和J（指向前缀末尾）遍历模式串，通过对比字符更新 LCP 长度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第四部分：KMP 算法的匹配过程与实现： 有了 PMT，KMP 的匹配过程就非常清晰了：用两个指针分别遍历主串S和模式串P，匹配失败时通过 PMT 调整模式串指针，主串指针始终不回溯。 匹配步骤 1.初始化主串指针I = 0，模式串指针J = 0，并构建模式串的 PMT。 2.遍历主串： > ·若S[I] == P[J]：两个指针同时后移（I++，J++）。 > > ·若S[I] != P[J]： > > > ·若J > 0：通过 PMT 将J调整为PMT[J-1]（利用前缀后缀匹配信息跳过无效对比）。 > > > > ·若J == 0：主串指针后移（I++），模式串从开头重新匹配。 3.当J == P.SIZE()时，说明模式串完全匹配，返回匹配的起始位置（I - J）；遍历结束未匹配则返回 - 1。 完整代码实现： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第五部分：刷题时光： 例题 1：LEETCODE 28. 找出字符串中第一个匹配项的下标 题目大意：给你两个字符串HAYSTACK（主串）和NEEDLE（模式串），请返回NEEDLE在HAYSTACK中首次出现的下标。如果NEEDLE不是HAYSTACK的一部分，则返回-1。 解题思路：直接套用 KMP 算法模板，核心是构建 PMT 并执行匹配逻辑。 完整代码： 例题 2：查找模式串在主串中的所有匹配位置 题目大意：读入主串S和模式串P，输出P在S中所有出现的起始下标，若未匹配则输出 “无匹配”。 解题思路：在 KMP 匹配中，当J == M（匹配成功）时，不直接返回，而是通过 PMT 调整J（J = PMT[J-1]），继续查找后续匹配。 核心代码片段： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第六部分：常见踩坑点与避坑指南： KMP 算法的逻辑看似清晰，但在编码和理解过程中极易陷入细节陷阱，以下是高频踩坑点及解决方法： 1. PMT 构建：用 “IF” 代替 “WHILE” 回溯 J，导致 LCP 计算错误： 坑点描述： 构建 PMT 时，当P[I] != P[J]，新手常误用IF语句单次回溯J（如IF (J>0) J=PMT[J-1]），而非WHILE循环，导致无法找到最长的有效前缀后缀。 反例代码（错误） 问题分析： 以模式串P = "ABABAC"为例： > ·当I=4（P[I]='A'）、J=3（P[J]='B'）时，P[I] != P[J]，需回溯J到PMT[2] = 2（P[2]='A'）。此时P[4]='A' == P[2]='A'，J应更新为 3。 > ·若用IF，仅回溯一次就停止；若P[J]仍不匹配（如更复杂的模式串），会导致 LCP 长度计算偏短，后续匹配出错。 避坑方案： 必须用WHILE循环回溯J，直到J=0或P[I] == P[J]，确保找到最长的公共前缀后缀： 2. 匹配时：主串指针回溯，违背 KMP 核心逻辑： 坑点描述： 受暴力匹配思维影响，在S[I] != P[J]时，不自觉地让主串指针I回溯（如I = I - J + 1），导致时间复杂度退化为O(N*M)，失去 KMP 的效率优势。 反例代码（错误） 问题分析： KMP 的核心优化是 “主串不回溯”，所有调整仅针对模式串指针J。主串指针I一旦后移，就不再退回，这是保证O(N+M)复杂度的关键。 避坑方案： 牢记：匹配过程中主串指针I只做自增，绝不回溯。所有匹配失败的调整都通过修改J实现。 3. 边界处理：忽略模式串为空或长度大于主串的情况 坑点描述： 编码时未考虑极端边界场景，如模式串P为空、P.SIZE() > S.SIZE()，导致数组越界或返回错误结果。 反例代码（错误） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第七部分：常见问题与注意事项： 1.PMT 与 NEXT 数组的区别：有些资料中NEXT数组是 PMT 的 “右移 + 1” 版本（如NEXT[0] = -1），本质逻辑一致，只是实现时指针调整方式略有不同，本文采用原始 PMT 定义更易理解。 2.模式串为空的处理：根据题目要求，通常模式串为空时返回 0（匹配开头）或空列表。 3.字符类型适配：KMP 算法适用于所有可比较的字符类型（如大写字母、小写字母、数字），无需修改核心逻辑。 4.PMT 构建的易错点：当P[I] != P[J]时，必须用WHILE循环回溯J（而非IF），确保找到最长的有效前缀后缀。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 尾声： > 特别鸣谢： > > > 排版： @AC是最好的 > > > > 标题：@‮༺དༀ༒∞░∞༒ༀཌ༻ > > > > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻ > > > > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻ 创作不易，给一个赞吧，求求了

名人砖访 VOL.2 滚蛋吧c++

前两天发不了名人专访1，现在更VOL.2了！！！！！顶！！！ 这次是滚蛋吧c++（他名字加了反转，@太难了） 不说肥话，开始正题吧！ > 先上总结 > > 滚蛋吧c++是一个典型的作业少年，热爱钢琴、撸猫、作业！！！！！！作业！！！！！作业！！！重要的事情说三遍。天文热爱者，小说热爱者。 钢琴10级的大佬\COLOR{LIGHTGREEN}{钢琴10级的大佬}钢琴10级的大佬 首先，资产问题 好吧 这次没那么炸裂 BER我说第二个问题有问题吗？ 反正我得说我作文确实不行，30分满分，我能考出20分好成绩 不是这么爱学习，模范学生啊 爱编程吗？ 为什么感觉这么不对劲？？？ 最后一个问题：咋么知道ACGO这么个东西？ 经典回答好吧 求关，必回关 好玩的传送门 某件搞笑的事：我把标题写成专访了，然后改成了转访

互动23｜#开学哪有不疯的

📌 活动话题：#开学哪有不疯的# 开学已经一周了，大家都还好吗？ 作业、早八、军训、社团、课表……是不是已经把你整疯了？🙃 快来分享你的“疯点”： * 作业堆成山，疯了 📚 * 军训晒成碳，疯了 ☀️ * 社团活动连轴转，疯了 💃 * 钱包见底，疯了 💸 * 早八连续四天，疯了 ⏰ ✨ 参与方式： 直接在帖子下方评论， 😆 形式不限：文字吐槽、配图表情包、段子，都可以！越真实、越搞笑、越社死，越有机会被大家热评！ 🎁 活动奖励： 随机抽取3名幸运之子送：ACGO定制笔 @仰天长啸你爹驾到 @130****6780 @༺ཌༀ™☯追光·少年☯™ༀད༻ 请在10月30日前私聊@AC君收件信息 ⏰ 活动时间： 即日起至9月18日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🔥 来吧，让全社区都看看你开学后的疯癫瞬间！（或许你会发现，大家都疯得差不多 🤣） 👉 往期话题

初中开学日记

不是诈尸了了吗，一直上上下下的。 前言\HUGE{前言}前言： 帮忙宣传：广子1，广子2，广子3（STARS_SEEKER特别播出） 这个帖子会不定时更新，如果有好玩的事的话会更新。之后会打上日期。打星号的是周末。我补充的 正文\HUGE{正文}正文： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 主任给我们讲的什禁食。 据说有4个七年级（以前的）女生拉了个群，然后他们看见一个女的经常跑去8年级那里，然后她们就在群里遭他黄瑶。本来她们4个是约定互相保密的，但是不知道咋地全校都知道这件事了。然后被造谣的那人的家长跑到学校来了，要求警方调查。后来虽然他们删了聊天记录，但是被警方使用高科技半个小时搞回来了，然后她们道了个歉，然后就没了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 吐槽一下学校： 汤是难喝的， 厕所是不关门的， 书桌是破的， 多媒体是旧的。。。 我们班三个男生上厕所被一个女生看到说是甜蜜三排。。。。。。。那仨个人分别是我小学同学和他的闺蜜。。。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 0（报到日） OK啊我也是成为初生了好吧~，还是很激动的。 进学校的时候，由于是骑自行车来的，我去停车。推进门的时候，学长肥肠核癌可氢的跟我打招呼： 学长：你是大一新生吗？ 大一新生（ 我：不是啊。 学长：那你怎么这么矮？还有，你咋不穿校服啊，小心被扣分哦 我：。。。 走进教学楼。见到小学同学。刚好和我一个班。然后我们一起进的教室。 排位置。果不其然第一排。我座位的的左边和后边都是小学同学。 在操场上排位置，突然旁边一个女生直接倒在我脚边，吓死我了。 之后班主任讲了一些东西。就去食堂吃饭。 饭菜我觉得A餐还是可以的。我们班一群人在吐槽B餐。我唯一吐槽的就是汤：番茄榨菜汤。嗯，怎么说呢。就是汤的含量是西红柿和榨菜的10多倍。嗯，就这样。 然后一个小插曲：我们组的人全跑了。其他组的也跑了。就我一个人来打扫卫生。（老师还表扬了今天值日的学生） 然后去听讲座。讲完之后外边下雨了。被迫听老师的鸡汤 回教室，各科老师都来了。反正噼里啪啦一大堆。总结一下老师的特点： 英语老师（班主任）：就一个字：善。 语文老师：和蔼 科学老师：非常的幽默，有趣。开场就是一个小实验。 数学老师：权威（似乎数学老师永远权威） 社会老师：人狠话不多 副科老师：不知道，没见到呢。 结果走的时候书包重的跟背了一包哑铃似的。而且还下雨了。被迫等了半天 后来成功平安到家。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 1： 今天开始军训。 第一眼看到教官就感觉教官十分的权威。 早读读完之后竞选班委。反正我没去 军训刚开始教官直接给我们个下马威。直接让我们俯卧撑两分钟。勉强撑住。 然后就是枯燥的站军姿啊，原地踏步啊之类的练习。 吃饭的时候一位大佬和其他人对线，1 V 5 完胜%%%。 下午依旧练习。不过听说因为女生没喊出声音来教官要制裁女生们。好像说是要体能训练之类的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 2： 教官没有给女生体能训练QAQ。 今天没干啥，正常训练+看了一部红色电影。 教官：“见到老师要向老师问好，来一遍。” 我们：“xxx班向老师问好” 教官：“声音大点啊” 我们：“向老师问好（超大声）” …下午 我们：“向老师问好！” 教官：“你们喊这么大声干啥，小一点不会吗，老师耳朵不难受吗？” 我们：“。。。” 这里要吐槽一下，我就去上个厕所，回来之后教官说我们男生讲话，让我们男生做俯卧撑。做就算了，也不知道哪个**发 神 经，还在讲话，害得我做了至少有50多个俯卧撑。而且是这么做的： 教官：“我数到一你们就下去，二你们就起来。1…………………………………………………………………………………………………………（看省略号的长度）2”。我真的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 3： 今天教官带我们看了阅兵仪式。果不其然要写作文QAQ（现在几乎一天一片了）。 怀疑教官太善良了。居然带我们在空调房里做了一下午。真的ｂ(￣▽￣)ｄ。 没发生啥大事。就这么多了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 4 666今天中午的汤简直一坨，《南瓜肉丝汤》。 汇演彩排之后，发生以一件很好笑的事： 隔壁教官：“奥利给！” 我们：“绷” 隔壁教官：“想笑，就笑吧”（气泡音。上面也是，可以想象电影里反派的说话方式） 我们：那啥表情包找不到了，反正你们可以想象出来。 疑似滚某综合征发作QAQ（滚蛋吧c++别干我）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 5 今天最后一天军训，我们班同学整了个活，直到那个椰树牌椰汁的广告吗，他把椰汁换成了特能输，然后做那个动作，还说：“特能输，我从小喝到大”。不敢放图片怕侵权，直到特能输是啥吧。 中午，旗手擦桌子，然后他等的不耐烦了“哎呀你们吃快点嘛——给我吃一个”。中午吃的是鸡米花 下午结营仪式，密码的教官莫名其妙让我们蹲了30分钟。之后教官不打招呼就跑了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ *9.7： 晚上熬夜看血月，选了两个最红的照片，可能不是特别清晰： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.8: 第一次跑操，发现跑操老师像咸鱼梦想家。 今天正式上课，感觉挺累的。作业也很多。但是我突然发现数学老师似乎也很幽默QAQ。 科学课上老师做实验，好像是加了个什么氢氧化钠，然后我们班的同学就说“加纳”，科学老师以为我们是在说这个东西，然后就纠正我们，给我们全班搞笑死了。 体育老师是00后%%% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.9： 今天第一次上体育，体育老师还是很善的，会给我们自由活动。 吐槽晚餐，那个魔芋做的跟肥肉一样。 晚自习课间发生了一个很搞笑的事，不兴说，想知道的私聊我。 我最喜欢在晚自习课间去看夜景，我们学校的夜景可美了。跑到三楼去看，真的很好看。前边是一条小河，之后是一大片农田。再向后看就是城市夜景了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.10: 信息课摸鱼： 555老师电脑太强了，还不是极域，根本破不掉 科学课上的科学实验，科学老师操作不规范，灭酒精灯只盖了一次盖子QAQ 晚餐B餐里糖醋里脊有点那啥了，给我们班一个人吃成咸鱼梦想家了（他还说A餐狗都不吃~~~） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.11： 考核的压轴题： 第四题： en，自己看看就知道了，难度不说了，这是压轴题o。 明后天介绍我的同学们QAQ。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.12： 今天跑操依旧看见咸鱼梦想家老师。 体育课的话大家都不陌生了，说实话，怀念xx时候的体育课。但是我们这届体育课老师就让我们跑了800米，然后就自由活动去了，老师，你是这个：ｂ(￣▽￣)ｄ。 老师和我们班同学打篮球，比赛。3V5（三个老师，三个学生），5:7。感觉老师没发挥全部的实力。后来来了一坨九年级的，然后那五个人力战九年级，赢了。就很神奇。好像是赢了3分来着。在回顾一下：体育老师是零零后o。 周末作业好少，学校都快写完了，只剩一个科学的ABC。但是： qwq 一个搞笑的对话： 科学老师：不拉不拉不拉。怎么测量我的体积呢？ 我：排水法。 科学老师：o？怎么测？ 我：在这个物体（老师）上挂一个绳子，然后把他（老师）全部浸没在水中，测量就行（这里不想说太多，只选取了有意思的部分）。 科学老师：。。。。。。。。。。。。 同学们笑成zhu了hhh（这是真实的）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ *9.14： 突然想到一个很搞笑的事情。 老师让我们仿写《春》我们班有个人的作文： > 盼望着，盼望着，西风来了，春天的脚步近了。 > 不拉不拉…… > “一年之计在于秋”，刚起头……。 笑死我了。 感觉升入初中背诵能力加强了。就背了一小会《春》就背下来了QAQ。 学鲁迅，老师告诉我们： 一怕写作文，二怕文言文，三怕周树人。 Q：鲁迅是浙江__人 。 A：浙江周树人。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.15： 666体育课给我搞中暑了 密码的晚上吃饭他们给我菜抢了，结果那人还在那里叫“那咋了那咋了”的。我去要不是我难受我直接给他饭掀了。md 今日MVP课程：历史。 他干掉了语文，干掉了英语，干掉了数学，干掉了科学，干掉了体育，干掉了音乐QAQ（人话：上面提到的学科全被历史占了）。 学了周朝之后我们班一群人说：“推翻谭（旗手性谭）天子暴政！诸侯们快随我造反。”我去笑死我了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.16： 虽然素材没了但是我写一下我们学校的汤： 举个例子。绿豆汤喝过吧。要么绿的要么红的。我们学校的绿豆汤几乎是清的！就隐隐约约看的见一点点颜色。而且还在红与绿两种颜色之间来会切换（我不知道这个是不是科学的）。食堂啥都好，就是汤有点那啥了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.17（别问我16去哪了，问就是素材没了）： 我去今天我们教室来了个神秘入。最主要的是他戴了个熊猫人头套。给我们班人笑了个半死HHH。也不知道熊猫人头套是怎么流入市场的。（那啥熊猫人都知道吧） 今天食堂阿姨发力了。菜做的特别好吃。还打的特别多QAQ 今天数学考试。发生了一件很搞笑的事： 数学老师讲一道题，说可能出现在试卷上（根据经验0秒直到一定会在试卷上出现）。老师把题目解法写在黑板上。忘记擦掉了QAQ。考试的时候我们全班都把题目答案抄上去了。而且我们还趁数学老师来之前销毁了证据（擦掉了）。我去笑死了。这题还是12分压轴题哈哈哈哈哈哈哈哈哈。 晚上下雷雨。旗手举着班牌。感觉跟举着避雷针似的。。。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.18： 谁懂这一刻的救赎感： 今天同学表演秒鸡翅QAQ。 我去了吃饭的时候就因为食堂搞了个烤肠然后一群人就开始说一些不兴说的东西，md饭都吃不下去了。 感觉内容有点少，介绍一下我们的班长吧： 班长是女的，非常善良。不会像纪委一样黑化。并且班长有一个特性： 每当你吃完饭后，你会在回教室路上的任何时间任何地点看到班长。但绝不会在教室里QAQ。（我们吃完饭是自己回班的）。 感觉码豆商城里的幸运盒子良心了。最近开的都是赚的。而且只要4700多就能换ACGO盲盒呢！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.19： 没有素材了，介绍一下我校两大传奇人物： 第一位胡主任： 光辉战绩：军训的时候让我们午睡的时候去太阳下站军姿/给我们灌输心灵鸡汤/和总教官谈合作。 第二位跑操老师： 外号咸鱼梦想家 光辉战绩：在跑操的时候抓出来两个码他的。然后执行了严格教育/原本跑800米让我们跑1000米。 而且最近胡主任不出来了。咸鱼梦想家也消失了一段时间，当然现在回归了。我们班怀疑是咸鱼梦想家吸收了胡主任而复活了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.23： 前面几期素材全没了。。。 今天我们班同学用大师球收了一个蛐蛐。在晚自习上。。。 介绍一下我的同桌： 外表看似和善实则内心非常阴暗。 别看他是个文静的女生，但是： 后桌说“闭上眼睛，你会看到神奇的东西” 同桌：“看到你这个神犇（详见ppl的帖子）吗？” 后桌：“你对胡主任的评价是啥” 同桌：“贱人” 后桌碰到了她的书本，她直接把后桌打{}死{}了。。。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.23 依旧每日班长。 晚自习的时候老师一个如来神掌（不是故意的）把我刚买的修正带打掉了，修不好了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.24（秋游特别篇）： 本篇比较长，我不一定能一次性写完。但是我保证我会在2025年9月28日日之前写完。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 今天秋游。 去了个理工大学，看了一些不知道是啥的东西。 主要是后来去的公园。 公园整体挺好，就是有流浪汉。 我们找了个 封{}尸{}宝地 风水宝地。搭了野餐垫。这里确实好。别的地方都被太阳晒熟了。我们这鸟事没有。 玩同学带的三国杀，摸了近10个杀，还有个诸葛连弩。而且我被动还是可以使用红牌当杀用。 去找厕所，绕了一大圈，走了1个小时，一万多步（这里是真的，假的死{}全{}家）累死我了。发现绕了一大圈，厕所就在背后。。。 中午吃饭。三明治。。。 太好吃了（（（ 我去了他们十几个人组团去吃海底捞了，给我馋死了（但是被抓了嘿嘿嘿 厕所回归的时候，他们把旁边的水管弄爆了。一瞬间，血 {} 水流成河（后来据说流了10吨，他们赔了好多钱）。 同学红温了，零食被吃完了。 见到了许多小学同学，简单聊了一会。 走的时候发现假山上都是零食。然后刚好学了历史，我们就说：“这是山顶洞人，具有爱美意识”哈哈哈。 后来也就回学校了（md还有晚自习 发生了一件特别吓人的事情。特别吓人，惊动了校长和主任。大概描述一下：有一个人刚动完大手术，结果另一个人搞了他一下，然后他手术恢复期吗。结果就出问题了。我去特别吓人，给我吓死了都。我去一点没夸张。 晚上吃炸鸡（✌ 666晚自习啥事没有。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.27： 666英语成绩发了，一个字：石\huge{石}石 那啥吧，下午没上课。我报了社团。集训 昨天出事的那个人平安回来了。 今天到没啥事，介绍一下同学吧： 食堂战神（补充版）：他有5个外号。我最常叫他xxx（和名字挂钩，不能说），贝爷（也和名字挂钩）。本人是同意的o。 猪妞兼stronger：这么说吧。说他猪妞呢是因为这件事：我们这里有一个江东大桥，我敢说住在这里的绝对知道。桥对面是下沙（这里可以问滚c。他就住在下沙）。结果他说“这是哪啊？我咋不知道”。这就是叫他猪妞的原因，虽然很明显是装的吧。为什么这么说呢？因为他指着一个办公楼说：“到火车站了。我来过这里——哇风景好好啊，我都没来过”。。。（脚注：这个地方就是在江东大桥上看见的）。特别的，这人喜欢搞别人。 猪妞本体：和身材挂钩。这里没有鄙视他的意思。这个外号还是他自己取得呢。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.28 放假啦！杭州有秋假，多放两天哈哈哈哈。 因为昨天调休错过了飞翔杯 准备下午在图书馆把国庆作业秒掉。 完了看见李华了，没救了（但是为什么李华还客串历史呢） 666图书馆偶遇贝爷。。。他被他爸压制了，话都说不出来了哈哈哈 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 9.29： 今天都是补充。 同学制作了蟑螂味薯片，嗯肥肠嚎池。有缘我给你们拍下来。（还有更多的，比如淋巴肉味） 我把ACGO本子带去学校，那位同学（同上）把狗哥画下来了。非常的逼真。 还是她。 我们的名牌上有一只鸟。他就改版了一下这只鸟。并且题词：乌鸡，海盗鸟，社会你鸟哥（有三只鸟被爆改了）。有缘拍给你们看 关于后桌的寝室：一个字，猎奇。里面有qjf出没。。。。（后桌的jio非常的臭。他半夜睡觉脚搭在楼梯上，把下铺的同学臭醒了）。 师之字体： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 彩蛋\HUGE{彩蛋}彩蛋： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 支线任务： 每一个只会记名字的记录委员都是由一个善良的男/女生黑化而来的。我们班是女的（她原本特别文静善良的）： 目前黑化程度：80%（今天她一巴掌把他的同桌打SI了。。。时间：9:24）。 班长黑化进度：30% 同桌唤醒进度：50%（后桌已经被**N次了。。。） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 主播作文很烂，大家凑活着看。 教官对我们还是很好的，想方设法的带我们偷懒。（教官是伞兵QAQ） 谢谢各位的支持： 谢谢大家。