挑战赛#23结束了

无人AK…无人AK…无人AK… …有25个人AK了？！还有六个人6次提交就AK了？！…有25个人AK了？！还有六个人6次提交就AK了？！…有25个人AK了？！还有六个人6次提交就AK了？！

Stars_Seeker的生活习性3.0

榜2了)更新版本：3.5 看到我就进来点个赞吧QAQ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3.5版本增加了小剧场（ 如果你也想把自己的经历加入小剧场，可以评论并@我~ 大型纪录片：STARS_SEEKER的生活习性 广告： > > > > > > > AI帖子（：快干掉他！ ：( 加团传送门 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 1.蓝色裤衩猫 > > 这代表作者它正在认真的学IO(吗)，请勿捕捉！！！ > 2.可爱黄桃罐头 > > 纯欠揍发典，可以随时捕捉（ > 3.M豆 > > 这代表它可能犯错了，希望得到力量原谅（ > 4.可爱特暴龙 > > 就是wyy，表面一张可爱的脸awa 但实则得罪不知多少人（ > 5.邪恶小鼻嘎 > > 表示它在当喷子，或者攻击其它的不明生物，不要捕捉，不然会攻击你 ） > 6.小嘴巴 > > 6，反正可以捕捉（ > 7.火星人 > > 别问他是谁，问就是男朋友（ > 敢捕捉我让他去你家偷你马桶盖。。。 > 8.鸟京 > > 被别人碾压式的攻击了，可以捕捉安慰qwq，最伤感的一集。。。 > 9.饿啊 > > 也别问，问就是红狼（ > 10.meme猫们 > 。。。。。。 > 就是它发典的另一种方式（ > 11.自己 ( ) 开？ > > bro现场拍的，你猜重庆到成都有多远？ > 别捕捉，因为它在fq（ > 12.弗瑞控（ > > 我可是正宗的弗瑞控。。。 > wyy 可以捕捉 ） > 13.可爱小狗 > > 如果它换成了这个头像，说明它在抵御别人的攻击（ > 哎呀骇死我力（ > 14.zgr4件套（ > > 哎哎呀呀骇骇死死我我力力！ > > 伤心的zgrQAQ > > 开心的祖国人 > > 秒切战斗脸（ 如果它用了最后这个头像，还有人敢捕捉，那说明事情没这么简单了（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二周目 STARS_SEEKER常用的背景 1.你知道吗，AI太好用了 ） 2.天空属于( ) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -猎奇区- 已获得他们的同意（ 1.硬菜肘子（ 2.Stars_Seeker（ 自己说自己（ 666这么多的粉丝，要是都给我该多好啊（ 。。 > > > > > > > 我也知道很猎奇，别喷我（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小剧场 记得小学的时候一次课间，氪癌的同学正在讨论自己最喜欢的超级英雄是谁。。。 A说：钢铁侠！！！ B说：美国队长！！！ C说：蜘蛛侠！！！ 然后，他们就来问我，问我最喜欢的超级英雄是谁？ 我思考片刻后，说 祖国人

泪奔

tgd 臭滚蛋吧c++ 答应和我一起删帖还发 嘴脸 cutl+C这个 世界再见 哈哈。蟹蟹你们

论正常的小说主角为什么永远死不了

宣传：链接描述 反派视角： 第一世（反派）反派用剑刺穿了主角的左胸。但是主角的心脏不在左胸。反派卒 第二世（反派）反派用剑刺穿了主角的右胸，但是主角的心脏在中间，反派卒 第三世（反派）反派用剑刺穿了主角的左右胸和中间，但是主角的心早已提到了嗓子眼，反派卒 第四世（反派）反派用剑砍下了主角的头，但是主角变成了刑天，反派卒 第五世（反派）反派把主角剁成了臊子，但是天空中响起一片声音：“我重生了，这一世…”反派卒 第六世（反派）：反派把主角剁成臊子后在主角重生的位置插了一把剑，主角被剑刺死了，但是主角的系统跑出来把主角复活了，反派卒 第七世（反派）：反派又在主角复活的位置插了把剑，主角不断地复活，第十九次杀死主角时，主角系统自爆，反派卒 第八世（反派）：反派刺中了主角的心脏，但是主角的梦中情人挡下了这一剑，反手刺向了反派，反派卒 第九世（反派）：反派先杀死了主角的梦中情人，被梦中情人的系统击杀，反派卒 第十世（反派）：准备动手干掉主角的时候突然想起之前的事情，心脏病突发，反派卒 欢迎补充 不要钻牛角尖了，正常是不会死的，当然，结尾可能会。 彩蛋： 被AtCoder Better耍了，调了半天，发现。。。

中文d'p能打出什么？

发出你d'p的第一个词语！

萌新刚学 OI，A+B 求条

rt，我的做法是这样的： * 当 a=1a=1a=1 或 b=1b=1b=1 时，通过“一一得一一二得二...”，可得出答案为另一个数，直接输出即可。 * 否则输出 aaa 与 bbb 的和。 对拍了 303030 组了都没拍出结果，求大佬帮助。

体育の日记

> 本人体育巨差无比求放过QAQ长期悬赏如何提升跑步速度，天赋怪依旧拉出去斩了 > > 先声明一下可能这个帖子就相当于日记了hhh > 也许不定时更新 前情提要 * 本人7下的时候第一次开学800跑3分40 * 在7下最后一次800跑3分14（当时没掌握技巧而且没全力跑，补药喷我） * 暑假的时候除了xmw集训营天天抢饭抢手机没跑步 感谢xmw提供的抢饭场地（bushi * 8上第一次800 3分23（跑完就后悔了第3圈应该加速的） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ OK正式开始 9.24 两天就校运会了，跳舞的干嘛呢这是还改动作虽然很简单 今天整那个20公斤的什么东西，要提起来深蹲，一组15个，一共3组，每组做完都要跑一段 累死了直接 （虽然做完这个跑200的时候跑到了30多秒吧，具体的有点忘了） 9.25 OK啊起来也是直接陨落了（ 腿有点似了（酸成啥了 哎对了家人们，老师昨天说腿有反应就做10个快速蹲起和10个高抬腿 我有一计 OK也是骗到3个同学了 让他们做蹲起和高抬腿之后问有没有感觉身体更疼了hhh hhh虽然我也做了30个蹲起（ 撕这个舞蹈和蹲起刚上了吗我请问呢 做一次近20个蹲起你要干啥 明天还能活着跑800吗 彩蛋：其实800是我被迫自愿报名的，望周知 9.26 今天校运会 我只有两项任务：跳舞和800，发现都在最前面，也就是说我干完800就结束了hhh OHHHHHHHH WOK 800 3分05！！！ 然后就一直休息了 骗你的跑完就后悔了，感觉可以再快一点 我晚上赶着上课的时候居然跑的动运动会跑的还是太慢了 对了我全校第5(# ^ . ^ #) 呃呃呃同学的苹果手机怎么打屁股肉的时候总是断触啊（ 9.28 我讨厌调休 今天整了3组跳绳+仰卧起坐 跳绳真的不是给人跳的，尤其在我的鞋带自己开了的情况下（ 然后跑200 36秒hhh 9.29 wok了今天跑121 就是200米400米200米 不过成绩倒是还行，分别是35,1分23,34 34啊！！！wok了老师神预言啊，跑之前还说往34的地方靠 不过400第一圈没怎么用力（第一圈42秒 eee家人们觉得我还能活吗 对了明天研学(#^ . ^#) 9.30 今天研学去房山 路上挺快的 还行腿不疼 hhh和同学玩爽了 就是全班只有30个人在研学 有个项目它要两个人两只手分别拿绳子紧绷，让小球在上面滚 被我们改成跳大绳、跳绳和跳皮筋了（ 放学挺早2:30就到校门口了 还有国庆假期爽了 怎么还有十一挑战赛啊 国庆作业某个卷王在周一的时候就把语文的写的只剩半篇作文了www 一笔没动呢还

备考GESP，半退

祝我上南开 看状态请看头像： 1. 南开校徽 说明很无聊，非常想跟人说话，我一定会关注你。 2. 南开教学楼 说明在做题，尽量不要打扰我，我没时间回复你。 3. 开满海棠花的校园 说明在发癫，可以来跟我说话，我很高兴见到你。 4. 我是看南门的 说明在怼人，最好不要打扰我，我可能会误伤你。 5. 和小号同一头像 说明不在线，有事可私信留言，我上线就回复你。

#创作计划# Tarjan 学习笔记

TARJAN 强连通分量学习笔记 可能更好的阅读体验 前言 > 声明：跳过本部分的阅读并不影响您学习算法。 其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。 大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。 于是我就决定先放一放。 几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。 记录 > 如果您还能看到这段话，代表笔者还打算继续更新。 > 目前计划：更新边双点双（会重新写一篇博客）。 * upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。 * upd 2025.09.27 更新完了除例题外的所有部分。 * upd 2025.09.29 写完了所有部分。 * upd 2025.10.06 发现了一处笔误。 强连通分量 概念理解 * 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，同时节点 vvv 也存在一条路径到达节点 uuu，则称 uuu 和 vvv 是强连通的。 * 强连通图：如果一个有向图 GGG 中，所有节点互相强连通，则称 GGG 是强连通图。 * 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图 GGG，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。 其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。 以上图举例，我们认为 {a,b,c,d,e}\{a,b,c,d,e\}{a,b,c,d,e} 属于同一个 SCC，而并非两个 SCC。 算法讲解 让我们先画一个图。 为了引出算法，让我们再画一个 DFS 搜索树。 由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。 假设按照 {a,b,d,c,f,e}\{a,b,d,c,f,e\}{a,b,d,c,f,e} 的顺序进行 DFS。我们讲所有指向未被搜索的边叫做树边（如图中黑色边，且必须由父亲指向儿子），而指向已被搜索的边叫做非树边（如图中黄色边）。 好，接下来让我们直接推出一个定理。 * 不存在两个节点 uuu 和 vvv，满足两点不为祖孙关系，且在 uuu 和 vvv 的子树中有非树边互相连接。换句话说，如果在 uuu 的子树中有一个点由一条非树边指向 vvv 的子树的某个点，那么 vvv 的子树中就一定没有一个点由一条非树边指向 uuu 的子树的某个点。 证明： > 因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。 为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。 一般用代码这么实现： 然后再定义一个 SCC 中的根为其中 dfn 最小的节点。 让我们再引出一个定理： * 一个 SCC 中的所有点必然出现在其的根的子树中。 证明： > 使用反证法。 > 如果一个 SCC 中的点 xxx 不在根的子树中，而是根的祖先，那么 xxx 的 dfn 必然小于 SCC 的根，矛盾。 > 如果一个 SCC 中的点 xxx 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。 > 故证毕。 至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。 那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。 只要当存在一个节点 xxx 满足 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么它必然是 SCC 的根。 上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。 或许你会觉得很晕，让我们回到最开始的图来举例吧。 在上述图中，SCC 有三个，分别为 {f},{e},{a,b,c,d}\{f\},\{e\},\{a,b,c,d\}{f},{e},{a,b,c,d}；其中，按照 {a,b,c,d,e,f}\{a,b,c,d,e,f\}{a,b,c,d,e,f} 的顺序，dfn 值分别为 {1,2,4,3,6,5}\{1,2,4,3,6,5\}{1,2,4,3,6,5}，low 值分别为 {1,1,1,1,6,5}\{1,1,1,1,6,5\}{1,1,1,1,6,5}。正好符合我们的“猜测”。 让我们看看 low 的更新步骤。 * 如果节点 uuu 可以通过一条边访问一个未被访问的节点 vvv，那么该边为树边。我们需要先搜索节点 vvv，然后更新 lowu=min⁡{lowu,lowv}\text{low}_u=\min\{\text{low}_u,\text{low}_v\}lowu =min{lowu ,lowv }，因为树边并不影响我们对于“经过最多一条非树边”的限制。 * 如果节点 uuu 可以通过一条边访问自己的祖先 vvv，那么该边为非树边。我们更新 lowu=min⁡{lowu,dfnv}\text{low}_u=\min\{\text{low}_u,\text{dfn}_v\}lowu =min{lowu ,dfnv }。注意必须得用 dfnv\text{dfn}_vdfnv 更新，因为已经消耗了“最多一条非树边”的限制。 * * 如果节点 u,vu,vu,v 没有祖孙关系，那么什么也不做。 然后是回溯，我们需要再引入一个栈辅助。每个节点 xxx 在被访问时就先压栈，当其把所有边都访问完之后开始回溯。判断如果 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么该节点必然为 SCC 的根，我们只需一直弹栈直至弹出节点 xxx，中间的所有节点均为同一个 SCC。 怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点 vvv，一定会在此之前先被弹栈。因为如果 vvv 与 xxx 不强连通，那么必然是 lowv\text{low}_vlowv 为一个大于 dfnx\text{dfn}_xdfnx ，小于等于 dfnv\text{dfn}_vdfnv 的数（因为节点 xxx 是一定可以通过树边直达 vvv 的），既然时间戳比根 xxx 晚，所以就能很轻易的得出时间戳为 lowv\text{low}_vlowv 的节点会在 xxx 回溯之前将 vvv 弹栈。 上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。 为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。 例题讲解 P2863 [USACO06JAN] THE COW PROM S 传送门 一个很板很板的题，再弹栈的时候判断一下 SCC 的元素即可。 具体请见代码。 P3387【模板】缩点 传送门 首先我们要知道一个关于 SCC 的定理。 * 一个点必然可以通过若干条路径遍历完 SCC 内的所有点并回到起点。 这个很好证明，强连通嘛，过去回来。 那么一条贪心策略就呼之欲出了。 > 每到一个点，就将其 SCC 内的所有点都遍历一次。 不仅白白更新了答案，又回到了起点，稳赚不赔。 然后我们就引出了连通性中一个最常见的分支，也就是缩点。 在本题中，缩点实际上就是通过将每个 SCC 缩成一个点，将原图化简成一个 DAG（有向无环图）。 DAG 能干的事可多了，因为它可以进行拓扑排序，这样我们就可以进行 DP 了。 回到这道题中，我们可以将每个 SCC 缩成一个点，同时将权值累加，最后跑一个类似于 LIS（最长上升子序列）的 DP 即可。 P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 传送门 "牛牛 OJ"的题还是不错的。 容易发现，“喜欢”其实就是可达罢了。同样是因为 SCC 互相可达的性质，这题依旧可以缩点。 缩完点之后，我们可以保证最多只有一个“点”满足所有点均可达。因为如果存在两个点，那么就出现环了。 但是考虑到我们找这个“点”不是很方便，可以考虑到这个“点”的另外一个性质，那就是出度为 000。同样的理由，如果出度不为 000，那么就有环了。 于是我们可以写出这个一份代码： 但是这样并不能直接 AC，我们犯了一个很容易忽视的细节，那就是出度为 000 的点不一定只有一个，因此还需要特判，当存在多个出度为 000 的点时直接输出 000。 参考资料 《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本文共计 994099409940 个字符，从构思开始共计花了 555 天，每天码字时间大于 111 小时，制作不易，求赞 awa。

#名人砖访 VOL.2 滚蛋吧c++

> 666上榜4了 > > > 555掉到榜5了 > > > > > 666榜7 前两天发不了名人专访1，现在更VOL.2了！！！！！顶！！！ 这次是滚蛋吧c++（他名字加了反转，@太难了） 不说肥话，开始正题吧！ > 先上总结 > > 滚蛋吧c++是一个典型的作业少年，热爱钢琴、撸猫、作业！！！！！！作业！！！！！作业！！！重要的事情说三遍。天文热爱者，小说热爱者。 钢琴10级的大佬\COLOR{LIGHTGREEN}{钢琴10级的大佬}钢琴10级的大佬 首先，资产问题 好吧 这次没那么炸裂 BER我说第二个问题有问题吗？ 反正我得说我作文确实不行，30分满分，我能考出20分好成绩 不是这么爱学习，模范学生啊 爱编程吗？ 为什么感觉这么不对劲？？？ 最后一个问题：咋么知道ACGO这么个东西？ 经典回答好吧 求关，必回关 好玩的传送门 某件搞笑的事：我把标题写成专访了，然后改成了转访