可汗大点兵

互动24｜# CSP人间真实

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

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

感觉热度没了，要被刷下去了。放在这里了，我会持续更新的《初中开学日记》 大家可以吧经历过的事打在品论去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.偷偷刷短视频，结果背后传来拍照声（细思鼻孔） 欢迎补充。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 彩蛋： 1.如果你怀疑晚上有鬼怎么办？ 首先你可以对着空气说一句“鬼，帮我关下灯”。如果灯没关证明没有鬼，如果灯关了，你也不用怕。毕竟鬼都帮你关灯了，这么有礼貌的鬼你怕啥QAQ。 2.如果你有一个娃娃，不管什么时候总会在每天的12:00出现在你家床头怎么办？ 非常简单。你把这个娃娃挂在某宝上，5块一个。如果有人买的话，发货过了一天它就自己回来了。然后你就可以继续卖了QAQ。 彩蛋2（讲个笑话）： 男：我们出去旅游吧。 女：不行，孩子刚出生。 男：wtf，我们俩认识5—6年了，你才认识这个孩子两天。 女：。。。 在哪个地方找的，忘了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 现在是2025年9月19日17:25:01。还在学校的我笑你一辈子%%%

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

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

CSP-J/S 2025 游记（会继续更

9.23更 加团（目前300人） AC君给我点赞置顶了！！！ 上榜四了！！！！！！感谢大家！！！ 注：后续还会持续更新复赛模拟赛和准备（虽然还不知道能不能进复赛555） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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（仅仅是个人看法） 最后，大家考的怎么样，对分数有什么看法，欢迎留言！！ 最后，也祝大家 RP++ 考出好成绩！！

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

精辣！！！感谢AC君赞助！！！ 本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的LCALCALCA 大家请坐稳，我们马上开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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，耗时6天，终于杀青了，打字不易，点个赞吧。 @AC君求加精

寝室怪谈(23)·终章

我往城堡更深处走着，有一条很长的走廊，里面被黑暗笼罩着，显现出一种恐怖与诡异。走廊的窗户被黑布照着，透不进来一点灯光。我慢慢地走着，走廊好像永无尽头，我很疲倦，但我知道，我要报仇，我要希望。我的朋友们不都是丧命在恶魔之手吗？他们的命不是命吗？我更加坚定向前走着……我不敢往边上看，闪耀的金色墙壁在黑暗的走廊中也会暗淡，呈现出一种死气沉沉的感觉。 不知过了多久，我看到了光亮，它像一把犀利的宝剑一样刺向黑暗的走廊，我看到了一个极其华丽的大堂：各种宝石砌成的墙壁反射着灯光，金色的地板闪耀着我很久都没有看见过的金光，像是晌午的阳光……一把很大的椅子上坐着一个人，他的左右都有侍卫，他睁开眼睛“你是谁？你为什么” “我是杀手四号，我认为我有新的任务。“ “行，你是想要彻底灭除人类吗？” “不是，我希望，我能拯救人类！我看不惯为了你而惨死的人。” “你以前一直同意和我一起消除人类，你忘了吗？” “我没有说过，也永远不会说，我 正是你一直要追杀的人——狗狗！” 我看到窗外灰蒙蒙的天，映衬这宫殿里闪着金光的墙壁，和恶魔充满畏惧的眼神。我直直地站在宫殿的中央，凝视着恶魔和他的侍卫：“我 就是你们一直要追杀的人——狗哥，今天我就要实行我的使命，让人类的太阳破云重现！” 我用力冲向恶魔，我身上没有利剑，但是我知道，只要有着一颗复仇的心，就一定能胜利。正在我接近恶魔的一瞬间，他的眼睛慢慢变小，身子缩成一坨，变成一只老鼠逃了。 我打量着四周，这个宫殿里空无一人，但是我听到了一点声音：他们像是地底下最深处的力量在嘶吼，每一声都拉着我的心弦。我像一个小小的门走去…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我打开了门，里面放着一个大笼子，笼子的银色柱子在窗外微弱的灯光下反射着，里面一个个人都在尽力的嘶吼着，他们像地底下最深层的力量在震动：他们就是那些被清除的同学！我要拯救他们，他们是无辜的，可恶的恶魔，居然把他们关起来了。我看着笼子门上的那把锁，上面写着一行字：**如果你是狗哥，请用你的生命还他们自由！这行鲜红的字，深深的刻在我脑海里，刻在我的心里，是的，我会去做的！ 我慢慢按下了确定按钮，银白色的笼子慢慢打开，里面的同学像蜜蜂一样奔跑出来，那一刻，我感觉到了我在这个世界上存在的意义，那是一种非凡的感觉，一种快乐的感觉，一种无法描绘的感觉…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我看到恶魔的城堡像一阵风一样慢慢消失，消失在那云朵的尽头里，那一刻我看到了世界上最美的景色：同学们正欢快地在操场上玩耍。我的心充满了一种不可描绘的感觉，它像火炉一样温暖着我的内心，我微笑这，看着这属于我们最美丽的阳光：对，那是人类的夕阳啊，是属于我们的夕阳。我躺在操场上，在我生命的最后一刻沐浴着这许久没有见到的阳光……对，阳光不再遥远，梦想不再缥缈，我第一次与世界感觉那么近，我的心柔软了，我的梦实现了……但是我的身体慢慢透明，像烟雾一样，随着风飞去…… 夕阳豪迈地吧周边的云彩染的火红，像是一幅画。太阳慢慢地落下去，我不伤心，因为它明天还会升起来的…… 已完结，下一期：远征 > 寝室怪谈系列目录： - 寝室怪谈系列目录

获奖公告｜ACGO挑战赛#22

获奖公告｜ACGO挑战赛#22 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ID @参赛者 礼品 4817688 @acidlemon 盲盒 1590033 @复仇者_帅童 盲盒 4372216 @183****1200 盲盒 4754145 @小小小Why 盲盒 4336036 @xueman 盲盒 4181234 @你是不是喜欢c++ 盲盒 5050722 @EKM_ 盲盒 4763653 @CEGO.tyx 盲盒 4406908 @宋雨琦才是真神 盲盒 1975597 @咕咕咕 盲盒 2324516 @Bellman_ford 笔记本 5137945 @1145141919810二年级 笔记本 4502534 @.云志.(〃'▽'〃) 笔记本 3085682 @阿毛mao 笔记本 4787135 @程庆阳 笔记本 🎁 获奖信息填写 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ⚠️ 赛事违规公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 46 名用户存在疑似 AI 生成或高相似度代码的情况。 相比以往，违规人数已有所减少，说明大家逐渐认识到赛事公平的重要性。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 本次违规名单将公示至 9 月 15 日； * 累计违规 >3 次的用户，将在9月15日统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，将在9月15日统一 禁言 30 天； * 仅违规 1 次者不予展示。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 申诉机制 用户可在赛后提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。 本轮赛事审核志愿者：@复仇者_帅童 本轮赛事出题老师：@NoonMaple ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📎 ACGO 官方赛事公平审核规则 以下为违规记录： ID 昵称 赛事违规次数 4326901 @Xclipse 4 1293833 @Banny 3 4252088 @无敌的鳖佬仔给老爷爷猜猜被 3 4326914 @ld returned 1🌌 3 4926857 @盛翰祺 3 4956019 @༺ཌༀཉི༒复仇天神༒༃ༀད༻ 3 5031884 @临渊者-恶灵骑士 3 1195034 @复仇者_零 2 795832 @AK仔 2 1472264 @小桂子GUINEVERE 2 1828641 @玮伦 2 1846820 @天之神_ZDZL_小徐同学(回关) 2 1896550 @𝓢𝓷𝓾𝓰𝓰𝓵𝓮 2 2684257 @谁来教我C++ 2 2736262 @xmy 2 2843748 @口味改vector(>ω<) 2 3041969 @༺ཌༀ小柴-贪醟 人机领袖ༀད༻ 1 3318585 @windows🐱‍💻 2 3475635 @‮++c吧蛋滚 2 3621376 @🥥 2 3971643 @忘川秋裤 2 4238026 @时间刺客 2 4337775 @垚Man 2 4348708 @‮🐱‍🚀 2 4372216 @183****1200 2 4437139 @☭中华c++ HP（关注必回关） 2 4481182 @复仇者_sxwwsด้้（加团队） 2 4504793 @༺ཌༀ`(>﹏<)′ༀད༻ 2 4509049 @小黑子 2 4573413 @AAA牙刷批发商 2 4592666 @༺ཌ𝓒𝓾𝓷𝓽𝓪𝓲ད༻ 2 4690036 @神 2 4793393 @༺དༀ༒吕哲铧༒ༀཌ༻ 2 4798866 @AAA秋褲批發lexora_哥 2 4911730 @复仇者_shazi一坨 2 4955978 @༺ཌༀཉི༒白·羊༒༃ༀད༻ 2 4958593 @༺ཌༀཉི复仇者_金雨晗༃ༀད༻ 2 4978429 @AAA冰块批发AI哥 2 4982181 @鲤鱼Ace·TADC 2 5014448 @刘骋原 2 5081613 @朱为源 2 5119926 @꧁aaa꧂ 2 5148234 @donk 2

远征预告

> HELLO，我是一个人 寝室怪谈都更完了，那我也要更新下一个小说了，当然，也不是AI写的，我避免不了错别字，不是寝室怪谈23的错别字都闹笑话了《狗狗》，哈哈哈。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这个的梗概我已经想好了 我都准备了2个月了\COLOR{YELLOW}我都准备了2个月了我都准备了2个月了。最近因为喜欢看科幻类的小说，当然我也要尝试写，写怪谈类型的我变菜了，寝室怪谈后面不是都没有规则吗？ 但是声明一点，因为是同一个人写的，文笔是不变的，风格也是不变的。当然，这个神经头像在我更新远征第一章的时候还是保留着的，更玩了就去换（我上个厕所像登基）。没事的，欢迎来评论区讨论，这次不会取像“狗哥”那么RZ的名字了，HHH 可能会分为n部曲，也可能不是

#名人砖访 VOL.1 白羊大神

从今天开始我将开始做一个节目，叫#名人砖访，这是VOL.1，将采访这位：༺ཌༀཉི༒白·羊༒༃ༀད༻ 他在社区也是很活跃的（身高8米61的帅哥） 首先第一个问题： 你有什么获奖经历？ 是吗？？？ 大佬真谦虚 第二个问题： 您是什么时候开始学编程的呢？是直接学C++吗？ 才学了一年不到？就csp-j1=? 有点牛！！！ 下一个问题：您平常爱打比赛吗？ acgo的比赛对于我这种水平确实也挺难的（（（ 再来一个：您的大学考虑？ 再问一下学校的成绩 WK！！！挑战赛都能AK！！！ 要是我这个水平欢乐赛都没法AK。。。。。。 下一个问题： 大佬也是从A+B开始的啊（（（ 那ACGO是怎么吸引大佬注册的呢？ 那除了ACGO你还喜欢哪些编程网站呢？ 最后一个： 您有什么资产呢？ 好家伙，之前说洛谷大boss是cjdst，原来真正的大佬这么谦虚 还有： 可见对学习的热情 彩蛋 下一期可能是编程之神\color{white}{下一期可能是编程之神}下一期可能是编程之神滑动 > 我k，竟然上top.10了 > 打一个广告

9.13更 大型纪入片《人类代码的特征》

第三篇番外《“访谈”复仇者shazi一只》现已更新--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 番外篇更新了\HUGE 番外篇更新了番外篇更新了 这是人类代码特征的番外篇 AI代码的特征番外篇 这是访谈第二期 大家好，我是**作者，我终于更了 在此鸣谢：提供主题者 如果你要提供特征，请提供相应的人类代码！！！\LARGE 如果你要提供特征，请提供相应的人类代码！！！如果你要提供特征，请提供相应的人类代码！！！ 针对于所有人对14条（人类不会用AUTO）的否定，现已删除\LARGE 针对于所有人对14条（人类不会用AUTO）的否定，现已删除针对于所有人对14条（人类不会用AUTO）的否定，现已删除 接下来是人类的几条特征，如果竞赛有判断不确定的情况，可以靠以下几个特征排除人类 1.人最爱用万能头（或者初学者用iostream，省内存的用cstdio 2.人类用的库绝对不超过5个（搞笑的除外 3.初学者及部分人敲代码一坨一坨的，判断不带空格； 4.某些人爱用类似于“aa”“bbb”"ccc"的变量名； 5.人类要么不写注释，要么一写一堆； 6.初学者不用vector 7.人的注释会写思路，但不是指引的思路 8.人类会用-‘0’转换 9人类用define不用typedef 10.人类取变量会在一起取 11.人类有时会用const（常数） 12.搞基高级人类都用全局变量 13.人类读取长度会用XX.size() 14.人类变量名会出现拼音（？） 15.python魔怔者会把||和&&写成or和and，当然不可否认也能用 例如下面代码 就这些了，如果你还有其他的特征或是人类代码，请发表在评论区，如果具有代表性就选取