远征目录

【互动】#1024吐槽节#

💥 #1024吐槽节# 盛大开幕！ 嘿，AC狗友们！🧑‍💻 又到了一年一度，咱们程序员的专属节日——1024！ （没错，ACGO也有自己的小传统了，仪式感拉满 😎） 所以，我们决定如期举办那个 “让人又爱又恨” 的活动—— #1024吐槽节# 今年的规则，简单到令人发指： > 看ACGO哪里不顺眼？大胆开麦！ 是题库太阴间？测评机日常抽风？ 还是社区功能用起来像在考古？ 或者，你单纯想对我们AC君喊一句： “你们这个功能是祖传的吗？能不能动一动！” 没问题！今天你说了算！🫡 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 来来来，指条明路（欢迎自由发挥）： * 「功能篇」：题库、测评机、排行榜、编辑器… 哪个让你血压飙升？ * 「社区篇」：氛围、活动、推荐机制… 哪里让你想“原地退站”？ * 「运营篇」：希望我们多整活？多发福利？还是… 少整点烂活？🤣 一句话：今天我们不开夸夸团，专心 “Debug ACGO”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 参与姿势： 1️⃣ 带话题 #1024吐槽节# 发帖或直接评论本帖 2️⃣ 尽情输出你的“血泪体验” + 你心目中的完美改进方案 3️⃣ 支持各种形式：小作文、段子、表情包、灵魂拷问… 越真实，越有力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 而我们，郑重承诺： * 所有高赞、走心的吐槽，我们保证逐字阅读，跪着回复！ * 那些闪闪发光的金点子，将直接进入 「ACGO优化清单」 （是真的会排期的那种！） * 被我们“盯上”的优秀吐槽官，还会收获一份 “忍住别哭” 的小惊喜 🎁 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 活动礼品： 高赞奖：点赞最高的前三位，送上ACGO钥匙扣盲盒 金点子奖 ：我们将选2-5名，送上AK吧唧 优秀吐槽官奖 ：我们将选选2-5名，送上ACGO周边定制笔 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🗓 活动时间：10月14日 至 10月26日 💬 活动主旨：吐槽是门手艺，进步需要勇气。 毕竟—— ACGO的bug或许会迟到，但我们想修好它的心，永不缺席！ 🛠️ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

【新周边】把AC狗“贴”上冰箱！

> 限量版「ACGO拼图冰箱贴」已登陆，让你的每一次AC都触手可及！ 亲爱的AC狗友们，注意啦！📣 你们催更的赛事实物奖励，这次真的来大的了！ 从本月底起，除了积分与荣耀，你刷过的题、熬过的夜、AC的代码，都将化身为可以亲手触摸、自由拼贴的实体成就——ACGO拼图冰箱贴限量登场！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 精雕细琢，只为珍藏你的每一次AC 🧩 12块碎片，记录你从萌新到大佬的成长相册，更是只属于ACGO Oler的硬核勋章墙。4大高光阶段，精准对应你的信奥成长轨迹： 🐶 AC狗拼图规格：完整狗拼图高度约为20厘米，适合贴在冰箱或磁力墙上。 🎨 高透精雕亚克力：采用高品质亚克力材质，通过精密雕刻与全彩印刷，画面清晰锐利。 📦 单片独立封装：每一块拼图碎片，都拥有自己独立的专属包装袋。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎮 三大获取路径，总有一条适合你 获取方式 拼图来源 🏆 打比赛挣 • 全系列赛事覆盖！• 名次越高，拿得越多• 巅峰赛必掉稀有「巅峰王者」碎片！ 🎁 抽奖试试手气 • 每场赛事都有“幸运抽奖环节！• 名次不够？欧气来凑！ 🛒 商城直接补（待上线） • ACGO商城提供精准补给！• 缺哪块，买哪块，秒速完成收藏！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🏅 终极彩蛋：解锁「拼图大师」专属勋章！ 当最后一块拼图“咔嗒”归位，12块碎片完整合体—— 请务必、立刻、马上去ACGO社区晒出你的完成品！ 我们将为你解锁专属「拼图大师」荣誉勋章，永久点亮你的个人主页，向所有人宣告你的毅力与实力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 拿下你的第一块拼图 🌟 现在，就从本次欢乐赛#59开始，拿下你的第一块拼图吧👉 立即参赛 🌟 10月20日至10月31日，互动区留言互动，抽取5位幸运鹅送拼图碎片！

【天梯闯关】保卫战正式打响

> AC军团们注意！🚨 你们期待的「天梯闯关」新副本已加载完毕！ 🎯 全新玩法亮点抢先看： ✅ 剧情式闯关体验 - 专属剧情导入，沉浸感拉满 ✅ 渐进式关卡挑战 - 从第一关开始攀登，层层解锁 ✅ 实时代码竞技场 - 禁用复制粘贴，纯手写代码见真章 ✅ 智能奖励系统 - 通关即获金币，失败推荐专属题单 🕹 闯关须知： * 必须登录才能进入天梯系统 * 严格关卡顺序，必须先通关前一关 * 每关限时挑战，代码需现场手写 * 通关条件：每关所有题目全部AC！ 💎 闯关奖励： * 每关通关即得金币奖励 * 登顶天梯榜的玩家将获得限定成就 * 失败也不怕，系统智能推荐提升题单 据说能登顶的都是能手撕算法、脚踩异常的真·大佬！你的头发和AC率都在等你拯救！ ❓ 最新情报： > 1. 第二关 Happy Birthday! 样例无误； > 2. 第三关《奇妙的数字变化》 10.22 已更新； > 3. 通关获得的罐头，之后可以兑换社区商城（待上线）的物品哦； 👉 【立即挑战】：天梯入口 💬 互动话题： 1. 你觉得自己能冲到第几关？ 2. 最期待在天梯中遇到什么类型的题目？ 3. 来预测下谁会是第一个登顶的AC大神？ 4. 闯关截图合影留念！ 🎁🎁🎁 在评论区留下你的闯关宣言，随机抽3位幸运鹅送出ACGO拼图冰箱贴！10月31日公布获奖！

《AC之前的往事》1

其实是不想搞这个的 但是有点难过 所以想找朋友们谈谈心 第一个 我想和大家说说"我" 姓名：小冰果（不想说真实姓名） 年龄：13 小学：不说了 中学：海淀外国语 爱好：看《三体》 玩pvz 玩英勇之地 做c++ 一开始 我是一个XMW学员 我的任务就是学好c++ 让家长放心 接触了ACGO 发现了一个"能让我活下去"的地方 5年级的时候 孤僻离群 没朋友 还被校园80 特别喜欢编程课 觉得很开心 认识了@魏敬平这个入 当时有了一个朋友 5下因为被80转学了 不在乎 认识了陈匡则，罗希，王乐威这几个朋友 其实没什么 就是顺带提一笔 主要的事还是后面ACGO的事 第二部分 来到了ACGO 是一个无名小辈 大部分认识的都是小马王集训营 类似的@听取WA声一片（C1103）@TN Hacker 还认识了一个大佬@滚蛋吧c++加入了他的团队 第一小部分是关于他的 你好 对不起打扰你了 问题1：你好厉害啊 但是没上榜 算是社交界的大佬吧 我见过你 在去集中营的班车上 没敢说 看起来你很普通 去集训营后 你又表现得很厉害 对比当时的我 其实很绝望 你肯定没注意到我 我是班里的小透明 好像扯远了 自己理解吧 这里面藏了个问题 离开这里 去你想去的未来 第二小部分 @༺ཌༀ我要上南开ༀད༻ 她才6年级 却比我这个初中生做的更好 她的6年级内卷日记很火 写出了悲欢离合 却没有绝望 可我不一样 总是闲着 想紫砂 陈匡则没有错 只是说出了我的内心 对不起大家 我骗了你们 你们都很开心 我只是一个死了没人管 活着没贡献的人 我很崇拜她 可我论辈分比她大 这没什么错 放手去做 不要管我 第三小部分 @张静之 你是一个同样爱玩游戏的人 也是一个同样优秀的人 我不如你 我只是一个在ACGO出题发布内心想法的人 只能靠游戏麻痹自己 哈哈哈哈哈哈哈哈呜呜呜呜 在我心里你很重要 可是我在你心里可能只能算个过客吧 我中了！我中了！我中了！！！！ 第三部分 问题 也是问大家 你么觉得我是什么B东西 随便骂我吧 发泄你们的想法 谢谢大家 以后会更新的！这是冰果自己发的！保真啊！ 下面是小记 @AC君@AAA混凝土批发ppl哥@一只德意志联邦球 随便找三个人 下一篇:传送门

远征·永夜孤光(1)

wdf上榜了？！ > 第一章·光影(1) 一个小小的水洼里的一条鱼，它努力地向外跳，努力寻找新的水源，在黑暗的夜里寻找着，它跳上了干燥的马路，鳞片在昏黄的灯光下闪着白光。它相信他一定能找到水源，前面确实干燥的马路，像宇宙一样广袤无边……它艰难地呼吸着，暗黑的夜中时间仿佛停止了，它用最后一丝力气再跳一次，没有到达水洼，它最后一次仰望星空，看到美丽而灿烂的星空，一颗颗星闪烁着，用它们的躯体燃烧着生命……小小水洼里的一条鱼满意地闭上了眼睛，它不再渴望水洼，它渴望灵魂永远在无边的宇宙中翱翔…… 林尽是个十几岁的少年，他在回家的路上走着，他捡起了那条鱼，看着这早已没有生命的躯体在昏黄的路灯下闪着银光，他慢慢地吧鱼放进一个浅浅的小水洼里，抬头仰望星空：“人类渺小而脆弱，在宇宙中，它们连一粒灰尘都算不上，但是我相信，人类不会被那些毁灭的力量摧毁，人类很坚强。” 林尽继续往回家的路走着，所有路灯突然熄灭，原本在这夜晚还有一丝灯光的安慰，现在这些灯光化作了一缕烟云，消失在着无边的黑夜里……他感觉整个世界都暗了下来，唯独天上的北极星是给他指路的灯塔。 林尽再次抬头仰望星空，他好像看到在这个黑暗的夜突然显出一种红色，像是宇宙的伤疤。他不敢相信，他认为自己产生了幻觉。可是再次抬眼一看，在这个红色裂口中伸出一个像龙卷风一样长长的光束。他很害怕，他努力地向佳的方向跑去，无边的暗夜下起了雨，像是晶莹的泪打在他身上。天上，这一束光快速地向地上伸展，层层光束中伸出一个长长的圆柱体，正向林尽家的方向深去…… 天空流着蓝白色的血，这黑暗而宁静的夜变成了恐怖主义者思想中的残夜。此刻，是林尽人生中凄冷的黑夜，他望着家，那乌黑的圆柱体正在将他的家毁灭！一片片细小的碎片随着残存的风轻轻扬起，飞到了无光的角落……“不！我的爹和娘！”他用尽力气叫喊着，好似在这天底下只有他一人在哀嚎…… 天上残存的星云不再漂浮，地上的花儿也不再开放。他看到了他的家人：他们正被吸附在圆柱体上向悲凉的宇宙伸去！他们叫喊着，希望微弱的声音刺破黑暗，给一段悲惨的童话画上一个句号。他拼命奔跑着，像家的方向奔去，他希望那片原属于家的土地能带给他意思安慰。 星云中的恒星继续燃烧自己的生命发出光芒，宇宙的运行依然依旧。林尽说他很爱宇宙，他喜欢一颗颗灿烂的恒星，他喜欢极致的浪漫发出的无边的美。可是他不再仰望星空，因为他知道这些星云能孕育出恐怖的野兽，它们发出的低吼奏响了宇宙级的安眠曲…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 目录 > > > 好心人加一下他的团队

巅峰赛 #26 T1,T2,T5 题解

其实就是为了让我的 T5 有趣解法能进讨论区而发的（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 * 思维：普及- * 算法：普及-（快速幂） * 模拟：入门 * 综合：普及- 好骗兄弟，好骗。 自行模拟，可以发现无论如何摆放齿轮，结果一定是合法的。 所以总情况数为 2hw2^{hw}2hw。 时间复杂度：O(log⁡p)O(\log p)O(logp)，其中 p=998244352p=998244352p=998244352。 T2 * 思维：普及- * 算法：入门/普及-（无） * 模拟：入门 * 综合：普及- 考虑贪心，先试试能不能放第一个盒子，如果可以就放，不可以再试试能不能放第二个盒子。 如果有一个数能放第一个盒子，但你把它放了第二个盒子，显然不优。 时间复杂度：O(∑n)O(\sum n)O(∑n)。 T5 * 思维：普及- * 算法：普及+/提高（树状数组，树形 DP） * 模拟：普及+/提高 * 综合：普及+/提高 好玩，以后多出这种题。 我们可以离线所有查询，然后搜索整棵树，在搜索完后合并所有子树的信息。 这样的话查询一定得在 O(log⁡n)O(\log n)O(logn) 左右，我们可以使用 map 和权值树状数组存储一个节点的信息。 map 用于记录每种颜色出现了多少次，权值树状数组用于查询出现次数小于等于 kkk 有多少种颜色。 具体实现就是这样的： 然后考虑如何合并一个点的所有子树的节点。 把子树的信息全部合并在这个点上？很显然这样子单次合并时间复杂度是 O(sizelog⁡size)O(size\log size)O(sizelogsize) 的，可以构造出一条链来将这种做法卡到 O(n2log⁡n)O(n^2\log n)O(n2logn)。 我们可以选定子树大小最大的子节点，然后把所有信息合并到它那。为什么这样是对的呢？我们可以假设当前节点子树大小为 nnn，最大子节点的子树大小为 mmm，则其它的树大小绝对不超过 mmm。则时间复杂度的函数可以如下表示： F(n)≤O((n−m)log⁡n)+nmF(m)F(n)\le O((n-m)\log n)+\frac{n}{m}F(m) F(n)≤O((n−m)logn)+mn F(m) 显然，当 mmm 与 nnn 是同一个数量级时，只需进行 O(n−m)O(n-m)O(n−m) 次合并，而递归其它子树的时间复杂度可以忽略不计，总时间复杂度约为 O(nlog⁡n)O(n\log n)O(nlogn)； 当 nnn 与 mmm 不是同一个数量级，经主定理可得时间复杂度为 O(nlog⁡2nlog⁡nmn)O(n\log_2 n\log_{\frac{n}{m}} n)O(nlog2 nlogmn n)。 所以这个做法的时间复杂度为 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 接下来就是如何实现了。 我们可以用一个 vector 数组，当递归到叶子结点时，在 vector 里面加入一个节点，包含它这一种颜色，并返回下标；否则先递归子树大小最大的子节点，获取它返回的下标，然后将其它向下递归，将获取的下标合并至最大的子节点上，最后返回存储最大子节点的信息的点下标。 最终代码如下： 时间复杂度：O(nlog⁡2n+qlog⁡n)O(n\log^2 n+q\log n)O(nlog2n+qlogn)。

#创作计划#学术计划VOL.2 双指针！

双指针！ 前言： > 这是Stars_Seeker推出的学术计划系列的第二期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句作者语文不好（，只有透彻又不完全透彻的知识awa。 > 写的这么差的帖子肯定是AI（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 双指针是什么 双指针可以看做对于枚举的一种优化。 对于两个指针如果分别从 1 到 n 枚举，那么两重循环嵌套，复杂度是 O(n^2), 但在一些具有单调性的题目中，可以使 i 指针和 j 指针都只需要从 1 到 n 遍历一次，复杂度分别为 O(n) , 总复杂度也是 O(n) 。 例题 1: P1147 连续自然数和 思路：构建前缀和数组，由于数字都大于 0，那么前缀和数组存在单调性，可以考虑双指针 i 指针移动时候，为了使得区间和仍然接近 n，j 指针只会向右移动，因此 i 指针和 j 指针都只需要从 1 到 n 遍历一次， 复杂度分别为 O(n) , 总复杂度也是 O(n) 。 代码实现 例题 2: P1102 A-B 数对 思路： 先排序使得数组存在单调性， 然后 i 指针从 1 到 n 扫一遍，复杂度为 O(n) , 每次找到符合条件的最大的 j ，将对应的数量加入答案，为了了解当前的 j 是同类数字里出现的第几个数字，可以另外开一个 cnt 数组来记录。为了保持 j 指针尽量大并且满足 a[i] - a[j] >= c ，当 i 指针向右移动时候, j 指针只会不变或者向右移动，那么 j 指针的总移动次数也是 O(n) 。 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 是的没错，你没有听错，第二期结束了！ 比第一期稍微长了一点，因为加了2道例题。以后字数不够的时候凑字数就这么写 ））） 本篇文章中“代码的注释”部分内容是作者它询问了它的教练，所以会看起来很权威。 如果文章中出现质量问题或者还有其他思路,欢迎在评论区讨论 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ <-上一篇学术计划

获奖公告｜ACGO十一挑战赛#23

获奖公告｜ACGO十一挑战赛#23 名次 用户ID 参赛者 礼品 1 3827769 @户晨风66 ACGO盲盒 + ACGO鼠标垫 + ACGO U盘 6 4978427 @130****7891 ACGO盲盒 + ACGO鼠标垫 + ACGO定制笔 7 5249369 @我要爆杀所有人 ACGO盲盒 + ACGO鼠标垫 + ACGO定制笔 9 3971643 @忘川秋库 ACGO盲盒 + ACGO鼠标垫 + ACGO定制笔 11 1943184 @egogaming ACGO盲盒 + ACGO鼠标垫 + ACGO定制笔 14 5097218 @jmy2012(2) ACGO盲盒 15 3009343 @Astrasilent ACGO盲盒 16 2182324 @zjr ACGO盲盒 17 5252334 @153****5677 ACGO盲盒 19 1590033 @AAA混凝土批发ppl哥 ACGO盲盒 20 4850952 @ph22zhongchen ACGO盲盒 22 4763653 @CEGO.tyx ACGO盲盒 26 3238624 @Enter_Name_Here ACGO盲盒 27 2226184 @夏夏夏夏夏夏夏夏夏夏夏夏夏夏夏娃 ACGO盲盒 28 3172666 @不会C++的noah ACGO盲盒 29 4372216 @183****1200 ACGO盲盒 🎁 获奖信息填写 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ⚠️ 赛事违规公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 55 名用户存在疑似 AI 生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 用户ID 违规选手 违规次数 4252088 @无敌的鳖佬仔给老爷爷猜猜被 4 4326901 @Edge 4 4926857 @盛翰祺 4 4956019 @Gold（有关必回） 4 5031884 @枫 4 1293833 @Banny 3 2736262 @Avelina 3 3318585 @twitter 3 4326914 @ld returned 1🌌 3 4372216 @183****1200 2（原先3次，复核成功改为2次） 4456314 @AC坤(100.00） 3 4592666 @༺ཌༀwonder2013ༀད༻ 3 4955978 @༺ཌༀཉི༒白·羊༒༃ༀད༻ 3 4958593 @༺ཌༀཉི复仇者_金雨晗༃ༀད༻ 3 4978429 @AAA冰块批发AI哥 3 5014448 @刘骋原 3 5081613 @我不是AC君 3 5148234 @b_donk 2（原先3次，复核成功改为2次） 527747 @ZhangCxuan vOwOv 2 774357 @🕈.👎.☝✌💧❄☜☼ 2 795832 @༺ཌༀ༒复仇者—黑客༒ༀད༻ 2 880830 @what！ 2 959560 @对方正在输入... 2 1015995 @√ 2 1195034 @复仇者_零 2 1472264 @小桂子GUINEVERE 2 1828641 @BAIZE 2 1846820 @天之神_ZDZL_小徐同学(回关 2 1896550 @アイドル人 2 1915048 @‌NovaBlade 2 1975597 @咕咕咕 2 2684257 @谁来教我C++ 2 2843748 @口味改vector(>ω<) 2 3310550 @北辞 2 3475635 @iiilll01 2 3621376 @🥥 2 3634791 @Ajax 2 3869215 @珠江新城——张基振 2 3971643 @忘川秋库 1（原先2次，复核成功改为1次） 3999499 @狂拽魔神 2 4238026 @时间刺客 2 4323608 @蔡栋旭 113室 老登 2 4326906 @LOVEKlee1314 2 4337775 @芙宁娜·德·枫丹 2 4348708 @‮🐱‍🚀 2 4419090 @AAA忘川秋库的秋裤批发哥 2 4437139 @☭中华c++ HP（互关） 2 4454967 @Crisit 2 4481182 @复仇者_sxwwsด้้（加团队 2 4504793 @༺ཌༀ`(>﹏<)′ༀད༻ 2 4509049 @小黑子 2 4573413 @AAA牙刷批发商 2 4673370 @༺ཌༀཉི༒元༒帅™༒༃ༀད༻ 2 4690036 @喵仔牛奶 2 4722696 @一只人畜无害的狗 2 4724944 @天之神——集训营一小只 2 4740425 @杨曙宁 2 4747742 @古希腊掌管AC和WA的神 2 4787141 @瀚高祖 2 4787172 @AAA混凝土批发ppl哥 2 4793393 @༺དༀ༒吕哲铧༒ༀཌ༻ 2 4798866 @Lexore_ 2 4851507 @yaonainai 2 4911730 @复仇者_shazi一只（不加团） 2 4958296 @天之神_星河_枫原万叶 2 4961547 @‏‮™☯一合神星༻དༀ瞳ༀཌ༺ 2 4982181 @鲤鱼Ace·TADC 2 5006148 @114514 2 5119926 @꧁NX꧂ 2 5156723 @Scarlett2025 2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 申诉机制 请在10月30日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核志愿者：@AAA冰块批发AI哥 本轮赛事审核&出题老师：@NoonMaple ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📎 ACGO 官方赛事公平审核规则

远征目录

> 永夜孤光 第一章·光影

#创作计划#迪杰斯特拉算法精讲

！！！ 不是这玩意咋上榜的 第零篇？\HUGE{第零篇？}第零篇？ ----------------------------------------------------第一篇---------------------------------------------------------- 前言： 可能更好的学习体验？ > 本文适合深色模式食用 本帖分为三个部分， 1.算法讲解 2.代码解析 3.真题演练 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 作者的话： 额，被老师逼迫了，所以来写帖子 顺便水个精华帖 。我会写四篇帖子。三篇是单源最短路，一篇是全源最短路。这是第一篇迪杰斯特拉。我觉得只讲思路和代码，不讲例题就不是一篇好的精华帖，所以，这个帖子被分为了三个部分，算法讲解，代码分析和真题演练。作者还苦修了一国庆的markdowm排版，大家可以评价一下这一篇帖子。嗯，我觉得可以给个头秃（虽然不是比赛）： 忘穿秋裤的回复套路，可以发现没有剪辑的痕迹，所以你懂得： 事实上忘穿秋裤已经被榨干了（BUSHI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文： 第一部分，算法讲解。 先来讲讲迪杰斯特拉的创作背景吧。（内容参考了AI总结）： 迪杰斯特拉在195619561956-195919591959年设计该算法时，主要目的是解决荷兰东部城市鹿特丹到格罗宁根的汽车路线规划问题。这一需求推动了算法的诞生，其核心在于通过贪心策略和优先队列优化实现高效路径计算。 ‌ 迪杰斯特拉是求单源最短路径的一个算法，整体采用了贪心\color{red}贪心贪心的策略。该算法可以通过优先队列进行优化，本帖只讲他未优化的用邻接矩阵实现的算法（其实是不会写优化(doge）。如果不知道邻接矩阵怎么写可以在帖子下方评论，我会考虑写一个简单的邻接矩阵的讲解，但是就不标创人计划了。 先 口胡 口头讲解一下。从起点出发，首先将起点设为 000 ,其他点设为无限[1]。将当前点标记为已走过，遍历当前节点的相邻点，我们可以计算出： 设 kkk 为当前节点的最短路径，www 为遍历到此节点所计算出的路径，该节点这一轮遍历的结果为： min(k,w)min(k,w) min(k,w) 遍历完所有相邻点时，我们在其相邻节点中选择路径最短的点，重复上述操作，知道所有节点遍历完成。迪杰斯特拉算法的时间复杂度是 O(n2)O(n^2)O(n2) 。需要特别注意，迪杰斯特拉算法无法\color{red}无法无法处理负权边[2]，具体原因见我下面的讲解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注：红色部分为初始化内容，其余部分为正式遍历 1.\color{red}1.1. 好的，保留节目，我画了一个简单的有向图，用于模拟迪杰斯特拉算法的实现过程。同时，我直接按照上面我讲的初始化了。同时，为了防止你们眼睛x掉，我特意用了3天换了个材质 2.\color{red}2.2.从起点开始，初始化[3]。输入这个图，构建邻接矩阵。 1. 正式开始遍历。先从节点 AAA 开始遍历，A的邻居顶点有 BBB 和 CCC 。从 AAA 到 BBB 的距离为 222 ，因为 2<无穷2 < 无穷2<无穷 , 所以我们把 disdisdis 数组中 BBB 的位置设为 222 。按照上述操作，将 disdisdis 数组中的 CCC 设为 555 。 2. 如图，可得 AAA 相邻的节点中， BBB 的距离是最短的，所以我们从节点AAA开始遍历节点 BBB 。 按照上述方法遍历节点 BBB 的相邻节点。当前节点路径长度为前一个节点的路径长度加上边的权值。所以我们可得在 disdisdis 数组中， DDD 的数值为 333 ， EEE 的数值为 888 。同时，将节点 BBB 设为已访问。 3. 这样节点 BBB 的遍历就完成了。在 disdisdis 数组中寻找未访问且当前路径最短的节点，可以发现是节点 DDD 。那么我们从节点 BBB 到节点 DDD 。 4.更新节点 DDD 的所有邻居节点的当前最短路径。这里不详细解释了。同时记得把 DDD 标记为已访问。 5.可以发现节点 EEE 的最短路径从 888 变为了 444 。节点 FFF 的最短路径从无穷变为了 999 。那么节点 DDD 就遍历完成了。寻找路径最短且未被访问过的顶点，为节点 EEE。那么从节点 EEE 开始访问。这里不做详细解释。 6.顶点 GGG 的最短路径从无穷变为了 141414。选择当前路径最短且未访问的顶点 CCC 。 CCC 没有邻居，将 CCC 设为已访问。寻找下一个符合要求的节点，为节点 FFF 。 7.从节点 FFF 开始遍历，节点 GGG 的最短路径从 141414 变为了 101010 。 8.最后访问终点 GGG 。没有可访问的节点。那么该图的迪杰斯特拉算法结束。通过 disdisdis 数组可得每个节点的在最短路径。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：代码解析： 首先我们要初始化。详见[3:1]。 接下来开始遍历所有节点，这是一个大 forforfor 循环。我们先选择当前所要遍历的节点 uuu 。 开始遍历 uuu 的邻居节点。如果有这个节点，我们更新[4]该节点。 综上所述，迪杰斯特拉的核心代码为： 最后，整体代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分，真题演练。 先看题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目背景 本题测试数据为随机数据，在考试中可能会出现构造数据让 SPFA 不通过，如有需要请移步 P4779。 题目描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入格式 第一行包含三个整数 n,m,sn,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。 接下来 mmm 行每行包含三个整数 u,v,wu,v,wu,v,w，表示一条 u→vu \to vu→v 的，长度为 www 的边。 输出格式 输出一行 nnn 个整数，第 iii 个表示 sss 到第 iii 个点的最短路径，若不能到达则输出 231−12^{31}-1231−1。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【数据范围】 对于 20%20\%20% 的数据：1≤n≤51\le n \le 51≤n≤5，1≤m≤151\le m \le 151≤m≤15； 对于 40%40\%40% 的数据：1≤n≤1001\le n \le 1001≤n≤100，1≤m≤1041\le m \le 10^41≤m≤104； 对于 70%70\%70% 的数据：1≤n≤10001\le n \le 10001≤n≤1000，1≤m≤1051\le m \le 10^51≤m≤105； 对于 100%100\%100% 的数据：1≤n≤1041 \le n \le 10^41≤n≤104，1≤m≤5×1051\le m \le 5\times 10^51≤m≤5×105，1≤u,v≤n1\le u,v\le n1≤u,v≤n，w≥0w\ge 0w≥0，∑w<231\sum w< 2^{31}∑w<231，保证数据随机。 Update 2022/07/29：两个点之间可能有多条边，敬请注意。 对于真正 100%100\%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。 图片 1 到 3 和 1 到 4 的文字位置调换。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这道题我们的代码是过不了的。事实上，你提交的时候只会得70分或60分。因为正解是邻接表。 很简单，板子题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 再看一道。 题目和上面一样，不过变成了无向图。这里就不搬了。 那么无向图怎么做？ 和有向图一样。disdisdis 函数是不变的。但是，在输入的时候我们要考虑这一问题。可以发现在邻接矩阵中，无向图会有两边的储存。比如 mp[u][v] 与 mp[v][u] 是一样的。但是有向图中这两个位置的值有一个是 000 。所以我们只要输入双向边即可。这里做了重边处理： 那么本帖就到这里结束了，谢谢各位的观看 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本贴如有错误，请私信贴主。 彩蛋： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二篇\HUGE{第二篇}第二篇 第二篇→ 注解： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 在c++中，无限可以用0x3f3f来表示，你可以不断地加上3f，但是建议你叠加时不要超过八个3f（即0x3f3f3f3f3f3f3f3f ），在往上叠加就没用了，而且可能会CE。 ↩︎ 2. 即边的权值为负的边 ↩︎ 3. 将$ dis$ 数组中除起点外的其他点设为无穷，起点设为 000 。visvisvis 数组中讲起点设为 111 ，其余点设为 000 。即已访问与未访问。 ↩︎ ↩︎ 4. 检查 uuu 点到该点的距离，如果小于原本该点的距离，则更新为点 uuu 的距离加上节点之间边的权值 www 。 ↩︎