互动24｜# CSP人间真实

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

退站声明

退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了退站了 完了事情闹大了，其实我没退（（（

CSP-J/S 2025游记（9.25更

9.25更 加团（目前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（仅仅是个人看法） 最后，大家考的怎么样，对分数有什么看法，欢迎留言！！ 注：从此处开始，接下来的时间将以复赛时间为标准 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，跟估分差不多，希望能进复赛。 最后，也祝大家 RP++ 考出好成绩！！

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

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

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

精辣！！！感谢AC君赞助！！！ 竟然榜5了 本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的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，耗时6天，终于杀青了，打字不易，点个赞吧。 特别鸣谢@AAA混泥土批发PPL哥对于FLOYDFLOYDFLOYD算法的指正、@沈思邈对于一些细节的建议！

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

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

#创作计划#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是最好的 > > > > 标题：@‮༺དༀ༒∞░∞༒ༀཌ༻ > > > > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻ > > > > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻ 创作不易，给一个赞吧，求求了

Stars_Seeker的生活习性

众所周知STARS_SEEKER只会用5种头像,1个背景 666进榜10了！！！ 1、小嘴巴 代表了它现在在灌水或者摸鱼，可以随时捕捉。。。 2、蓝色裤衩猫 代表了它现在可能在打比赛或者在做事情，尽量不要捕捉。。。 3、xitele猫 代表了它现在在当喷子或者在攻击其他不明物种，请千万不要捕捉，否则它会反过来攻击你。。。 。。。 4、火星人 只是传错头像了。。。不用在意 5、猫猫虫 这是我刚接触互联网时用的第一个头像，也是我前洛谷里用的头像。它有着非凡的意义…… 看到他说明我在思考或者在发癫，这两个随机。。。 背景 1、蓝色裤衩猫权威2.0 它的主页常驻背景。 你知道吗？豆包太好用了！！！ 非常权威 @‮༺དༀ༒∞░∞༒ༀཌ༻ @CH/陈---必回关 @༺ཌༀ我要上南开ༀད༻ 望周知 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

如何破坏气氛

这种什惊玩意是怎么上榜的

码上开聊 VOL.13｜王李轩

码上开聊 VOL.13｜王李轩 关键词：CSP-J 一等、飞翔杯、图论突破、ACGO社区 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 个人档案 * 姓名：王李轩 * 年级：新初二 * 坐标：绍兴市第一初级中学龙山校区 * 兴趣爱好：打单机小游戏，编程，做数学 * 获奖经历：2024CSP-J复赛一等奖，多次市赛、区赛获一、二等奖 * 社区好友：@忘川秋库 ，@MuktorFM, @ganruiling * 社区主页：围观yaonainai的主页 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 正式开聊 Q1：你是从什么时候开始学 C++ 的？之前还接触过其他语言吗？ 王李轩： 五年级的时候开始学的。之前在学校学过 python，但是只学了一点皮毛，后来换老师之后就没再碰过了。平时周一到周四我主攻学习，周五晚上 + 周末会写点代码 + 上课。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q2：你最早接触编程时，觉得编程和数学相比，最大的不同是什么？ 王李轩： 编程是让计算机去解决问题，而数学则是人来解决。编程需要强大的数学基础，数学则不需要编程能力。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q3：最初是怎么接触到 OI 和 ACGO 的？ 王李轩： 老师让我们打飞翔杯的比赛，于是我稍微探索了一下 ACGO，然后平时有空就打打比赛。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q4：你最早学习 OI 的动机是什么？ 王李轩： 当时应该是父母让我去学的，然后我自己也觉得挺有趣的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q5：学习过程中最难坚持的地方是哪一块？ 王李轩： 学图论那块的时候，一点也没法理解，后来我放假每天 5h 补习，总算学会了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q6：突破图论瓶颈后，你有什么启发？ 王李轩： “菜就多练”，遇到难题真得花时间去啃，否则以后遇到不可能会了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q7：你在 2024 CSP-J 复赛中获得了一等奖，当时心情如何？ 王李轩： 第一次获这么大的奖，非常激动，也期待明年能在 S 组拿一等。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q8：在飞翔杯普及组获奖，对你来说意味着什么？ 王李轩： 第一是奖品，第二是同学的敬佩，第三是 ACGO 上的成就。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q9：你印象最深的一场比赛是哪一次？ 王李轩： 第二届飞翔杯。本来以为最后奖品应该是蓝牙耳机了，没想到最后奖品竟然是 300 京东卡，直接卡线。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q10：有没有哪道题让你印象深刻？ 王李轩： 洛谷 P2063，非常考验数学，这是我人生中第一道黑题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q11：你认为比赛和日常刷题的关系是什么？ 王李轩： 刷题有助于比赛。我认为比赛更加有效，因为比赛能通过排行以及分数更直观地体现出选手的水平（当然，AIer 多了，也没意义）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q12：平常是如何规划学习和刷题的？ 王李轩： 刷题不要为了 AC 率，要刷自己薄弱的点。一般我暑假时会把白天用来学习，晚上用来刷题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q13：有没有特别喜欢的题型或算法？ 王李轩： hash 算法以及分治算法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q14：遇到瓶颈时，你一般怎么解决？ 王李轩： 花更多的时间或者问老师。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q15：你怎么看待“坚持刷题”和“效率学习”的关系？ 王李轩： 坚持刷题没错，但效率学习更重要。做任何事都要讲究效率，这比你没日没夜的刷题要好很多。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q16：你会给初学 OI 的学弟学妹什么建议？ 王李轩： acgo / 洛谷的题单顺序是正解，按照这个顺序刷题会比较好。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q17：在你看来，ACGO 相比其他 OJ 最大的优势是什么？ 王李轩： 竞赛时间长，奖品好（但是最大的缺点就是 AIer）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q18：你在 ACGO 社区最喜欢的功能是什么？ 王李轩： 讨论区。精华帖看来涨知识，看水帖能放松。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q19：如果让你给 ACGO 提一个改进建议，你会改进什么？ 王李轩： 优化等级分。可以仿照洛谷，搞不同名字的颜色。这与勋章并不矛盾，可以根据不同勋章的质量加相应的分数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q20：你觉得 OI 学习对你的生活或思维方式有什么改变？ 王李轩： 有些时候在批量修改某组数据时（我妈工作），我能用 C++ 快速解决。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q21：未来在 OI 上的目标是什么？ 王李轩： 高一拿 NOIP 一等，进入省队。争取在 NOI 中取得好成绩，帮助高考。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q22：除了 OI，你还有哪些兴趣或方向想尝试？ 王李轩： 五大竞赛（当然现在没想好）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > ⚡ 快问快答 * 最喜欢的编程语言？ C++ * 最不喜欢的题型？ 大模拟 * 最近在研究的算法？ AC 自动机 * 如果用一个词形容你打比赛的风格？ 抽象 * 比赛中最怕遇到的情况？ 有道题看别人很快 AC，自己却连暴力分都拿不到 * ACGO 里最喜欢的功能？ 讨论区资源 * 编程之外最喜欢做的事？ 打单机小游戏 * 未来最想挑战的比赛是？ NOI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 访谈结语 王李轩的学习之路里，既有突破图论瓶颈的毅力，也有追求效率的学习理念。他的经历说明：OI 不仅需要刷题，更需要反思与方法。未来他希望能在省队和 NOI 舞台上继续突破自我，我们也期待见证他的成长。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击回顾往期访谈 >>