阅前说明: 单源最短路与多源最短路: 单源最短路:求从一个固定起点出发,到图中任意顶点的最短距离. 多元最短路:求从任意起点出发,到图中任意顶点的最短路距离. *当然,求单源最短路的算法重复执行n次(n是总顶点个数)就是多源最短路算法.而多源最短路算法在无时间限制的情况下,也可以用作单源最短路算法 松弛: 最短路的核心思想. 操作方式:以某一个顶点作为中转站,更新与这个顶点相邻的其他顶点的数值 (这种操作称为对中转站顶点的松弛) (上述说法选自Yuilice老师的最短路算法,这里会配图更详细的解释这个说法) 比如这张无向图(标明的数字是路径长度): 现已知想要从点A走到点D有一条路:A -> C -> D (路径长度:25) 那现在取点B作为中转站进行松弛,发现: A -> B ->D 这条路径长度为22. 那么就将点A到点D的最短距离更新为22 一.Dijkstra 最短路算法的一种,单源最短路算法,基于贪心思想.但同样,其缺点也因贪心思想而诞生. 其主要过程:不断挑选与起始点距离最近的点,并利用挑选到的点与其他顶点进行松弛.(每个点只会被挑选一次) 贪心思想的体现:挑选与起始点"距离最近的点" 贪心思想带来的缺点:无法处理负权便 可以使用堆优化时间复杂度:在挑选与起点距离最近的点时,利用优先队列"priority_queue" 时间复杂度: O(mlog⁡n)\textstyle O(m \log n) O(mlogn) 例题:P4779 【模板】单源最短路径（标准版) 代码: 二.SPFA 最短路算法的一种,单源最短路算法,铃铛人的优化.与DIJ不同,SPFA的松弛从边入手,将每次产生了变化的边的点放入队列. 也因此,SPFA与DIJ不同,它可以解决负权边,也可以判断负环. 优化:相比于Bellman,SPFA不会对没有发生变化的边进行无意义的松弛(取自Yuilice老师的最短路算法 判断负环:SPFA中,一个点不会被加入队列超过(>=)n次. 例题:T18691.小码君的太空基地【SPFA】 补充:注意到SPFA和Dijkstra都有一个叫vis的数组(从个人角度来说,我认为SPFA和Dijkstra的代码长得还是挺像的,所以要注意区分.)不同点在于,SPFA的vis[i]代表的是i这个顶点是否在队列中;而Dijkstra的vis[i]代表的是i这个顶点有没有松弛过. 三.Floyd 最短路算法的一种,相对于SPFA和Dijkstra来说,是多源最短路算法.和动态规划有异曲同工之妙. 优点在于代码简单易写易理解.缺点在于时间复杂度高达O(n3)O(n^3)O(n3) 操作方式:三层循环,第一层循环枚举松弛顶点,第二层循环枚举起点,第三层循环枚举终点. 例题:A29680.最短距离查询【Floyd】 智慧代码: *本篇学习讨论部分内容基于Yuilice老师的最短路算法 嗷嗷嗷嗷嗷窝最短路算法梦开始的地方,预习的时候就逮着这篇疯狂学 感谢老师 并且感谢 BaiRX 同学提出的 这篇学习讨论的漏洞 万分感谢!(●'◡'●)

十天之内，（截止6月7日）死神团各项职务随你体验！（想要的向我发私信） 各位先到先得！！！！ 打个广告

招人啦招人啦 https://www.acgo.cn/application/1767458705509044224 在此插一句第一个同意的将成为培训部部长！

所以别问我为啥掉榜三了

《11451419198101》 《1145141919》

最近大家估计也刷到了 码上开聊VOL.9 | 何景天 这一期新出的 码上开聊。 我也是偶然发现啊，这一期码上开聊有个 “隐藏梗”，也是非常的魔性。希望大家能“一点就通”。接下来废话不多说，咱们直接上梗好吧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 首先，请大家打开这一期的 码上开聊 ，链接我已经准备在下面了，直接点开即可。点开后呢，大家看到这里↓↓↓ > 大家看，这里的 感想 是 “出题比做题爽多了！” 注意看 “爽多了！” ，它让你想起了什么？ > 如果大家和我想的一样，都是“卫龙魔芋爽，热量低了，爽多了……”那就扣一；如果没想到，扣二；如果想到了别的，那就扣三并说一说你想到了什么 [展示榜1] ，有精彩回答我也会放到上面好吧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 接下来是大礼包—— 菜单 彩蛋环节（口误）： 卫龙魔芋爽，热量低低低低低低，低低低低低低，低低低低低低低啦！卫龙魔芋爽，热量低了，爽多了！（重复循环ING……） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 怎么样，这个 “隐藏梗” 是不是很**？（有同学说炸裂，好有同学说中二，如果还有什么认为别的，那就扣五并说说看 [展示榜2] ） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 喜欢就点个赞吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本帖附带链接： 戳我打开 码上开聊VOL.9 | 何景天 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 备注：此为 逆天世界，无奇不有！（3） 本系列其他链接： 逆天世界，无奇不有！（1） 逆天世界，无奇不有！（2） 广告（是本人的另一个系列，不是团队！） 点我加入洋葱村 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小冯真的非常感谢大家（），大家已经把这个帖子炒到了排行榜NO.7，欢迎大家点赞+评论哟！ 小冯还会继续加油的！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 作者官宣： 本文无任何打广告、推销等影响公共秩序的意思，仅只是奇思妙想和一个小发现。 请大家不要误解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 预告： > 1.FKC的 逆天世界，无奇不有！（4） 即将出炉！大家敬请期待！ > 2.码上开聊NO.10已经出来了，这是第一个两位数码上开聊哟！

还有人过儿童节吗？

仅使用头文件 代码未简化，勿喷 适合新手食用，简单易懂 T1 if语句 T2 数组处理，但是好像不那么复杂？ T3 计数就完了 T4 6题里最难的（个人向） T5 本题关键在于：使用1, 2, 4, 8, ..., 2k这样的二进制数可以组合出任意不超过(2k+1)-1的数。 T6（讲的细一点）其实暴力就完了 1.准备工作 2.枚举所有子矩阵：对于每个可能的子矩阵，确定其行和列的范围。 3.判断平衡：如果0和1的数量相等，则该子矩阵是平衡的，计入总数。 完整代码： 献上彩蛋 蟹蟹各位 本人第一次发帖，给个赞呗

小码王智能学习系统的网址是多少

T1：模拟题 由数学知识得，凸 nnn 边形有如下特征： * 内角和等于 (n−2)∗180°(n-2)*180°(n−2)∗180°。 * 任一内角小于 180°180°180°。 直接判断即可。 T2：Nim游戏模板题 由Nim游戏结论，一个状态是必败状态当且仅当 a1 xor a2 xor a3 xor ... xor an=0a_1 \ xor\ a_2\ xor\ a_3 \ xor \ ... \ xor\ a^n = 0a1  xor a2  xor a3  xor ... xor an=0，其中 xorxorxor 表示异或。 因此首先判断： * 如果上述异或和为 000，则当前为必败状态，怎么走都赢不了，答案 000。 * 否则，设上述异或和为 ttt。枚举 aia_iai ，判断能否通过减少 aia_iai 使得操作后异或和为 000，即将 aia_iai 换成 ai′<aia_i' < a_iai′ <ai 后，ai′a_i'ai′ 与剩下的数异或和为 000。由异或性质得充要条件为 ai xor t<aia_i \ xor \ t < a_iai  xor t<ai 。 T3：思维题 由于原问题是在一棵树上，由树的性质，每一个限制对应的边必然是一个割边（即去掉它后剩下两部分（或称为两个半区）不连通）。考虑若设定 (x,y)(x,y)(x,y) 这条边中 xxx 是父节点，那么相当于根节点只能在 xxx 所在半区。 因此我们考虑这样的策略：对每一个限制，把限制边割掉，给子节点所在半区打上“不可能存在根节点”的标记，最后在没被打上标记的连通区域（显然只可能有一个）统计它的数量。 实现方式很多，可以直接模拟，当然我比赛时使用的是并查集。 T4：组合题 首先将所有选手按实力从小到大排序，接着考虑对于排名为 iii 的选手（由于从小到大，最弱的排名为 111），倘若他进入第 kkk 轮，简单推导得到他必定是这个位置对应的 2k−12^{k-1}2k−1 个人中最强的，因此我们必须要安排 2k−1−12^{k-1}-12k−1−1（减去那个人自己）名实力比他弱的选手填充掉这个位置，剩下的对他没有影响。 因此，这个排名为 iii 人最高能进入的轮数 kkk 是满足 2k−1≤i2^{k-1} \le i2k−1≤i 的最大的 kkk，设 x=2k−1x = 2^{k-1}x=2k−1，则有这个位置的答案为 Ci−1x−1×Axx×A2n−x2n−x×2n−k+1C_{i-1}^{x-1} \times A_x^x \times A_{2^n-x} ^{2^n-x} \times 2^{n-k+1}Ci−1x−1 ×Axx ×A2n−x2n−x ×2n−k+1。 表示的是：在第 kkk 轮对应的 2n−k+12^{n-k+1}2n−k+1 个不同的区域内随便选一个，在可以被选的 i−1i-1i−1 个人中选出需要的 x−1x-1x−1 个进行全排列，其中这一区域的 xxx 人需要全排，剩下与之无关的 n−xn-xn−x 个人也要全排。 套公式即可。 T5：思维题。 首先注意到随着 lll 的增加，答案必定单调不增。这启示我们预处理出每一个 lll 对应的 kkk 的最大值，其中双指针维护当前的最大答案。 我们考虑 l=1l=1l=1 时，答案必定是其中的最大值。当 lll 更大时，答案只可能比它更小，而可能的答案只有 nnn 个。因此我们可以尝试能否 O(1)O(1)O(1) 判断第 iii 大的数能否作为长度为 lll 的连续序列的最小值。 因此我们先钦定某一个数为连续序列的最小值，那么我们一定不能取比它更小的值，因此我们可以维护这个数左边和右边第一个比它小的值的位置（分别设为 li,ril_i,r_ili ,ri ），那么只要左端点大于 lil_ili ，右端点小于 rir_iri ，就一定可以以这个点作为最小值。极限情况下，我们分别取它们的相邻位置，就可以得到长度为 ri−li−1r_i-l_i-1ri −li −1 的以这个数为最小值的连续区间。 上述维护的值可以用单调栈实现。这样我们只需要判断 ri−li−1r_i-l_i-1ri −li −1 是否大于等于当前的 lll 即可判断这个答案成不成立。 T6：博弈论 首先看题，很明显这个游戏符合公平博弈游戏的经典特点（双方都知道全部信息，双方进行的操作相同，具有明确的终止状态）。这种游戏的特点是：每一个状态都必定是必胜态和必败态的其中之一。其中必胜态指的是游戏进行到这个状态时先手有必胜策略，必败态指的是这个时候先手无论怎么操作都必败（双方智商足够高的情况下）。且必胜态必定有一个策略能在下一步转移至必胜态，必胜态也必定有一个策略能在下一步转移至必败态（不懂的可以学一下博弈论）。 回到这个题，首先我们注意到一个性质：若在某个状态下，存在一个节点连有两个以上的叶子节点，那么这个状态必定是必胜态。这是很显然的。比如我们规定其中一个叶子节点是S，那么我可以选择只删除S这个节点，那么如果之后的状态是必胜态，那我就必胜了。否则如果是必败态，我们发现在剩下这个树能进行的操作和我现在保留S这个叶子结点能进行的操作完全相同，根据我上面提到的性质，必定存在一种同时删除S和剩下一些叶子节点的策略，使得下一步还是必胜态。也就是说，我们可以先判断初始状态是否有一个点连有2个以上叶子结点，如果有，那么直接判Alice赢。 那如果没有呢？这样我们可以把问题转化为：找到一种策略使得在我先手时可以使某个点连有两个以上叶子结点。这和原问题是等价的，因为至少有一个人可以实现这一目标，而能实现这个目标的必定赢。于是容易想到维护初始时每个节点至第一个连有两个以上子节点且是这个节点祖先的节点的最短距离（也就是从这个地方一直删除到满足要求最少需要多少步），第 iii 个设为 fif_ifi 。考虑若有叶子节点的 fif_ifi 是 111，就等价于满足了这个需求，即必胜。否则，若所有叶子节点的 fif_ifi 都是 222，那么他无论怎样操作下一步都必定出现一个 fi=1f_i=1fi =1 的点，即必败。此时若又存在若干个 fi=3f_i=3fi =3，那么他需要把必败留给对方，就可以把所有 fi=3f_i=3fi =3 的都删掉，即必胜。若又又又存在 fi=4f_i=4fi =4，那么他第一步可以把所有 fi=3f_i=3fi =3 全部删除，只剩下 fi=2f_i=2fi =2 的。这样另外一个人只能删 fi=4f_i=4fi =4 的将其变为 fi=3f_i=3fi =3，而此时转回来后又必胜了。我们注意到这些策略都是以先手删除 fif_ifi 为奇数的点为基础，这样就不难猜出这样一个策略： * 若存在叶子结点 fif_ifi 为奇数，则将所有 fif_ifi 为奇数的叶子节点 −1-1−1，这样所有叶子节点 fif_ifi 都是偶数。 * 否则，由于你必须删除一个叶子结点，故你怎样操作都会使后一步出现 fif_ifi 为奇数的叶子结点。而且你还不能删除 fi=2f_i=2fi =2 的叶子结点，因为这样对面直接就赢了。 因此，这样进行若干次后，必然会剩下一个叶子结点 fif_ifi 均为 222 的情况，此时谁先手谁输，而这种情况必定是由存在 fif_ifi 为奇数的对手状态转移而来。这样，我们只需要判断是否存在叶子结点 fif_ifi 为奇数，就可以判断谁赢。

A76与A80一样？

int a,b; cin >> a >> b; int n,sum=0; for(int i = a;i <= b;i++){ n = i; while(n > 0){ sum += n%10; n/=10; } } cout << sum; return 0; }

小黑子，露出鸡脚了吧！

这是什么题目？我看都没看懂。

翠蝶无声，陨落在秩序中 柔情被刻度尺无情衡量，碧色的蝶翼被肢解 紫色药水也无法挽救心底的隔阂 难道，差异终究无法弥补 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本人文笔稀烂，就写到这里 以下是互动内容： 1.诗中每个加粗的词象征一种人格，知道的可以打出 2.分享一下对各种人格奇葩的刻板影响吧（仅娱乐请勿人参公鸡）

我 3557085 做出了 T38541.南镇挖钻石I

用户唐瑀轩请注意，你已经踢了两位同学，现在被列为黑名单成员。应禁言30y

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------今天是端午节，所以祝大家端午安康呀！！！ヽ(￣▽￣)ﾉ