选手们好!这里是赛时答疑帖,感谢大家参与本场比赛! 此处是所有比赛: 1. 测试赛 2. 在赛时,如果遇到有关题目的疑问,可以在这里询问或联系我们,我会尽量解答。在提问时请尽量注明提问的题目,这有助于我们更好的解答您的疑问 特别地,如果您对数据强度或正确性存在疑问,或您认为出现重题之类影响比赛公平的情况,请私信本人而不要在此处讨论 再次感谢大家参与这场比赛,祝大家 AK！

本篇节选自OI WIKI 引入 DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法．所谓深度优先，就是说每次都尝试向更深的节点走． 该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况．\color{red}{用途完全不同，很少有能混用两种算法的情况．}用途完全不同，很少有能混用两种算法的情况． DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样． 过程 DFS 最显著的特征在于其 递归调用自身\color{red}{ 递归调用自身}递归调用自身 ．同时与 BFS 类似， DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次． 符合以上两条规则的函数，便是广义上的 DFS． 具体地说，DFS 大致结构如下： 以上代码只包含了 DFS 必需的主要结构．实际的 DFS 会在以上代码基础上加入一些代码，利用 DFS 性质进行其他操作． 性质 该算法通常的时间复杂度为 𝑂(𝑛 +𝑚)，空间复杂度为 𝑂(𝑛) O(n)，其中n 表示点数，𝑚表示边数． 注意空间复杂度包含了栈空间，栈空间的空间复杂度是 𝑂(𝑛)的． 栈实现 DFS 可以使用 栈（Stack）\color{red}{栈（Stack）}栈（Stack） 为遍历中节点的暂存容器来实现；这与用 队列（Queue） 实现的 BFS 形成高度对应． 递归实现 函数在递归调用时的求值如同对栈的添加和删除元素的顺序，故函数调用所占据的虚拟地址被称为 函数调用栈（Call Stack） DFS 序列 DFS 序列是指 DFS 调用过程中访问的节点编号的序列． 我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）． 一般图上 DFS 对于非连通图，只能访问到起点所在的连通分量． 对于连通图，DFS 序列通常不唯一． 注：树的 DFS 序列也是不唯一的． 在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树．DFS 树是原图的一个生成树． DFS 树 有很多性质，比如可以用来求 强连通分量．

大家自己想

这一篇是算法的网3的下一篇。 观前须知： 1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。 2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。 —————————————————————————————————————————— 这是我们的网现在的样子： 我们接着上一篇提到的，来讲一讲旅游巴士的第二种做法。 喔喔喔喔喔喔喔。我有点恍然大悟了。 分层图本身可能比不是一定要把每个点都以在图上添加k个来实现的。（比如说P4568飞行路线） 它也可以是：一个点有k个状态。 而dis[i][j]就是表示第i个点的j个状态。 这是我上一篇写的： 它的第二维就是状态。虽然是n个点，但实际上是k*n个点的分层图。 哦。所以没有第二种做法。 原来如此。 好的，那我们看下一题吧。 陌路寻诗礼 唔。我好像没见过这种要求。好神奇啊。 这道题目的要求是：给出n（节点数）,m（边数）,k（边权取值范围）和m条边。 问：如何安排m条边的边权，使得从点1到其他城市的最短路径为1. 我的初步思路是跑BFS，然后在跑的过程中给边加边权。 那么如何赋值边权呢。 我不会。 啊啊啊啊。怎么构造啊。 想太久了没想出来又去看题解了。我觉得我好**。但关键是不看也做不出来。 怎么办啊。 那我多做一点最短路绿好了。我觉得只练十题太少了。练二十题好了。 牛的旅行 社交网络 道路选择 最长距离 黑暗城堡 (上面的这些是前面的十多题遗留的，下面的十题是新选择的） 团 图上交互题 car的旅行路线 最优贸易 灾后重建 房间最短路问题 跑路 Cleaning Shifts S 电话 采蘑菇 好的，题挑完了，我们接着看陌路寻诗礼。 好的，我看完题解了。 其实这个题解让我感觉很诡异：就是我觉得，这个思路似乎是不难想的，或者说理所应当的。但是同时我认为，这个做法像是从天上掉下来的一样。（也就是我当时在想题的时候，从来没有想过这个方面） 它居然是可以直接加的嘛……好震惊。 我再看完之后的感觉是很奇怪，因为在我的大脑里潜意识认为这种做法行不通的。（如果有大佬知道这是怎么回事，欢迎指点qwq）。 而且，这道题目的代码实现也非常非常地简单！ 只要在原有的模板上做一点点更改就好了： 我不会告诉你我调了半个小时就因为 并且，可喜可贺的是在我调错的时候，我重新搞懂了这个思路，我明天来分析它！ 好吧。我突然奋发图强了。所以我今天晚上就来分析它。 这个题解的楼主给你的感觉是：四两拨千斤。 但是实际上它很复杂。接下来我会从两个角度去分析： 一.文字本身 这句话看似普通又平常，但是想到它其实并不容易哦。 当你一开始做的时候，需要给每条边去赋值。你可能就得想：欸，我是要赋值最大值还是要赋值最小值，或者是中间值？（甚至如果你想的偏一点，你甚至可能根本想不出要赋值，可能回去想一些乱七八糟的方法，构造题本身就很容易很容易跑偏） 有一个突破口可以（更容易）想到它： 当k只能等于1，那么就直接赋值为1，然后融入一部分最短路计数的代码，去看有没有相同值。 这部分做完之后，你再去看接下来怎么做，就会更容易联想到。 接下来的部分我会从代码的角度去分析： 我上面的那版代码，是我已经更具这份题解提供的代码修改过的。 我现在将两份代码（我原来的和我现在的）进行对比。 现在的： 原来的： 接下来，我们一处对比一处对比地分析一下： 1.我将len变量删除了 并且把要加的len改成了"+1"。 这是因为，在dijkstra中，每条边能够对它所连接的点进行更新的机会永远都只有一次。 (因为每个点在Dijkstra里面也只会被遍历一次） 而第一次被遍历时，这条边的初始值也只能是1。 2.直接填写2 这边的逻辑和上面的逻辑是一样的。直接增加1就好了。 虽然我前面那些都写得很简单很轻松，但是其实头脑风暴了很久。 所以在这里得建议是：大家做完一道题之后可以去看看题解写的代码。有一些代码写的简短漂亮，那么它背后的思路可能也更好。 我当时发现后面可以直接填2得时候我都惊呆了。好妙得构造啊。 这道题我一直没有注意道德是：在dijkstra中，每条边只会进行一次遍历（单向边哦）。 不过这个也是只在模板上进行更改，并没有与算法进行美妙的联动。但是思想上有提升。 所以网没办法更新qwq。 好吧，我们看下一题吧。 采蘑菇

玩三角洲——航天的帮我找个人 我最近见到一个ID是:山人自有妙計， 有知道的人可以私聊我。

我和“青云仙宗”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！ 点击链接

可能double会把一些大的数字变成科学记数法

问：这题样例是不是有问题,答：作者给我擦冰鞋

我们都知道，编程猫社区和ACGO讨论都是两个互动性平台，但不知道编程猫关了那么多功能，导致我连小说都发不了了 观察ACGO之后，发现也有发小说的，所以我想建议ACGO专门建立一个“图书馆”，把每个人的小说放在各自的一个合集里，并留出评论，讨论位置的作品第一难找，第二影响找别的类型的个帖子 所以提出该建议

用中文打出你键盘中间那行字母（标题） 我：爱 上 对 方 过 后 就 哭 了 同学：爱 上 大 粪 过 后 就 啃 了 {哈哈哈哈} 打在评论区 不同但通顺的就上榜

c++struct重载操作符 奇妙网站 请不要删帖，此为个人的记事本（我真不知道要把东西放哪了）

不要傻傻的加数字和了，只要模9就行了！ 如果是零，那就变成九！ 就是这么简单！

竞赛时间：2026-04-18 20:12 至 2026-05-18 20:01 (时长：29天23小时49分） 竞赛入口，邀请码:AMFD ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📜 赛事介绍: * 本次公开赛题目比较水，都“很难” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 奖励说明。。。 * 由于题目过于简单所以没有奖励 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 出题人 > @毒豌 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 公平竞赛公约 * 由于题目过于简单所以可以使用AI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ❓ 是否需要帮助？ * 如有任何疑问或需要帮助，请联系 队长 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后祝各位选手比赛顺利！{\COLOR{CYAN}最后祝各位选手比赛顺利！}最后祝各位选手比赛顺利！