在集训如何逃离牢湿手册1

互动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++ 考出好成绩！！

备考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。还在学校的我笑你一辈子%%%

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

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感谢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算法的指正、@沈思邈对于一些细节的建议！

获奖公告｜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 官方赛事公平审核规则

好心人帮我找一下

谁取关了我，找到直接给10级管理员！！ 好心人加一下这个团队

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

前两天发不了名人专访1，现在更VOL.2了！！！！！顶！！！ 这次是滚蛋吧c++（他名字加了反转，@太难了） 不说肥话，开始正题吧！ > 先上总结 > > 滚蛋吧c++是一个典型的作业少年，热爱钢琴、撸猫、作业！！！！！！作业！！！！！作业！！！重要的事情说三遍。天文热爱者，小说热爱者。 钢琴10级的大佬\COLOR{LIGHTGREEN}{钢琴10级的大佬}钢琴10级的大佬 首先，资产问题 好吧 这次没那么炸裂 BER我说第二个问题有问题吗？ 反正我得说我作文确实不行，30分满分，我能考出20分好成绩 不是这么爱学习，模范学生啊 爱编程吗？ 为什么感觉这么不对劲？？？ 最后一个问题：咋么知道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是最好的 > > > > 标题：@‮༺དༀ༒∞░∞༒ༀཌ༻ > > > > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻ > > > > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻ 创作不易，给一个赞吧，求求了

#创作计划#字符串哈希详解

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 加精了\tiny 加精了加精了 本篇讲解哈希算法，这是一种在很多领域都有运用的算法。 > 目录 > > > > 1.简介 > > > > > > 2.关键性质 > > > > > > 3.核心思想 > > > > > > 4.单哈希算法 > > > > > > 5.双哈希算法 > > > > > > 6.无符号长整型溢出法 PART 1. 简介 哈希算法在编程竞赛中的主要应用是把一个字符串映射为一个数字（通常会取模）来把O(n)O(n)O(n)的字符串比较问题转化为O(1)O(1)O(1)的数字比较（当然预处理不是O(1)O(1)O(1)的）。 PART 2. 关键性质 哈希算法主要有以下性质 1. 确定性 * 相同的输入必定产生相同的哈希值（也是哈希算法的基础） 2. 高效性 * 计算哈希值的过程应该很快 3. 雪崩效应 * 输入的微小变化会导致输出的巨大差异 * 例如"aelloaelloaello"和"hellohellohello" 的哈希值应该完全不同 4. 抗碰撞性（这个指标是用来判定哈希冲突的） * 弱抗碰撞性：给定一个输入，很难找到另一个不同的输入产生相同的哈希值 * 强抗碰撞性：很难找到任意两个不同的输入产生相同的哈希值 PART 3. 核心思想 哈希算法的核心思想在于，将字符串的每个字符对应成0~25的数字，再将整个字符串映射为一个kkk进制数（kkk通常取128128128）模一个大质数（比如1e91e91e9、998244353998244353998244353）。 具体实现不难，只需预处理128128128的幂次就可以轻松实现。 PART 4. 单哈希算法 单哈希算法即只用一个数作为模数。 实现并不难，模板代码就不给了，给出一道例题 PART 5. 双哈希算法 这是我们重点讲解的算法。 要想学习双哈希算法我们首先得了解—— 哈希冲突\HUGE 哈希冲突哈希冲突 相信很多读者会发现：哈希算法是基于映射和取模的，那岂不是很好hackhackhack？只要构造两个取模后相等的字符串不就好了？没错，这就是哈希冲突，双哈希算法就是用以解决哈希冲突的。 那么我们如何解决哈希冲突呢？很粗暴，就是用两个不同的模数来判断，如果两个字符串所映射的数字模两个数都相等，那么他们大概率就是相等的。 这时候，聪明的同学就说了，主包主包，那还是可以hackhackhack啊？大家大可放心，到现在还没有人成功hackhackhack掉双哈希（bzojbzojbzoj上就有一道这样的题，一直到它倒闭都没人做出来），因为如果有这样的数据，字符串会长到不可想象，所以双哈希是绝对可靠的。 就算不可靠你可以再模一个，自创三哈希 > 注：一个实用技巧，哈希在实战中常常使用前缀的形式，详见后面的代码。 下面给出一道例题 代码： 我在其中封装了两个哈希结构，不会封装的也可以分开写。 PART 6. 无符号长整型溢出法 双哈希固然好用，但是实现非常困难也没多困难，所以，我们隆重推出懒人写法—— 无符号长整型法，即unsignedunsignedunsigned longlonglong longlonglong。 这个算法基于无符号长整型溢出后自动取模的特点，但是有小概率被卡CSP被卡别怪我 还是给一道例题 代码： 大概是史上最短创作计划了，萌新有什么看不懂的可以在评论区留言，也欢迎大佬给出珍贵的建议，@AC君求精。