猜谜

备考GESP，半退

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

不是哥们，为什么下架我的帖子

666盐都不盐了，我这水帖进热榜了（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我认为我的帖子没有违反任何一项规则，为什么下架了？

距离挑战赛开始已经过去六十一个小时了

无人AK…无人AK…无人AK… …有12个人AK了？！还有一个人6次提交就AK了？！…有12个人AK了？！还有一个人6次提交就AK了？！…有12个人AK了？！还有一个人6次提交就AK了？！

互动24｜# CSP人间真实

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

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

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

#创作计划# Tarjan 学习笔记

TARJAN 强连通分量学习笔记 可能更好的阅读体验 前言 > 声明：跳过本部分的阅读并不影响您学习算法。 其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。 大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。 于是我就决定先放一放。 几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。 记录 > 如果您还能看到这段话，代表笔者还打算继续更新。 > 目前计划：更新边双点双（会重新写一篇博客）。 * upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。 * upd 2025.09.27 更新完了除例题外的所有部分。 * upd 2025.09.29 写完了所有部分。 强连通分量 概念理解 * 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，则称 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。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本文共计 987998799879 个字符，从构思开始共计花了 555 天，每天码字时间大于 111 小时，制作不易，求赞 awa。

和平宣言

我不引战了啊，我的世界和迷你世界都很好玩啊，你们不要引战了，我希望迷你世界的玩家以后能跟mc玩家和平相处啊，游戏之间呢，和平，和平，好吧，别引战了啊。

#创作计划#字符串哈希详解

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 加精了\tiny 加精了加精了 本篇讲解哈希算法，这是一种在很多领域都有运用的算法。 > 目录 > > > > 1.简介 > > > > > > 2.关键性质 > > > > > > 3.核心思想 > > > > > > 4.单哈希算法 > > > > > > 5.双哈希算法 > > > > > > 6.无符号长整型溢出法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 1. 简介 哈希算法在编程竞赛中的主要应用是把一个字符串映射为一个数字（通常会取模）来把O(n)O(n)O(n)的字符串比较问题转化为O(1)O(1)O(1)的数字比较（当然预处理不是O(1)O(1)O(1)的）。 PART 2. 关键性质 哈希算法主要有以下性质 1. 确定性 * 相同的输入必定产生相同的哈希值（也是哈希算法的基础） 2. 高效性 * 计算哈希值的过程应该很快 3. 雪崩效应 * 输入的微小变化会导致输出的巨大差异 * 例如"aelloaelloaello"和"hellohellohello" 的哈希值应该完全不同 4. 抗碰撞性（这个指标是用来判定哈希冲突的） * 弱抗碰撞性：给定一个输入，很难找到另一个不同的输入产生相同的哈希值 * 强抗碰撞性：很难找到任意两个不同的输入产生相同的哈希值 PART 3. 核心思想 哈希算法的核心思想在于，将字符串的每个字符对应成0~25的数字，再将整个字符串映射为一个kkk进制数（kkk通常取128128128）模一个大质数（比如1e91e91e9、998244353998244353998244353）。 具体实现不难，只需预处理128128128的幂次就可以轻松实现。 PART 4. 单哈希算法 单哈希算法即只用一个数作为模数。 实现并不难，模板代码就不给了，给出一道例题 PART 5. 双哈希算法 这是我们重点讲解的算法。 要想学习双哈希算法我们首先得了解—— 哈希冲突\HUGE 哈希冲突哈希冲突 相信很多读者会发现：哈希算法是基于映射和取模的，那岂不是很好hackhackhack？只要构造两个取模后相等的字符串不就好了？没错，这就是哈希冲突，双哈希算法就是用以解决哈希冲突的。 那么我们如何解决哈希冲突呢？很粗暴，就是用两个不同的模数来判断，如果两个字符串所映射的数字模两个数都相等，那么他们大概率就是相等的。 这时候，聪明的同学就说了，主包主包，那还是可以hackhackhack啊？大家大可放心，到现在还没有人成功hackhackhack掉双哈希（bzojbzojbzoj上就有一道这样的题，一直到它倒闭都没人做出来），因为如果有这样的数据，字符串会长到不可想象，所以双哈希是绝对可靠的。 就算不可靠你可以再模一个，自创三哈希 > 注：一个实用技巧，哈希在实战中常常使用前缀的形式，详见后面的代码。 下面给出一道例题 代码： 我在其中封装了两个哈希结构，不会封装的也可以分开写。 PART 6. 无符号长整型溢出法 双哈希固然好用，但是实现非常困难也没多困难，所以，我们隆重推出懒人写法—— 无符号长整型法，即unsignedunsignedunsigned longlonglong longlonglong。 这个算法基于无符号长整型溢出后自动取模的特点，但是有小概率被卡CSP被卡别怪我 还是给一道例题 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大概是史上最短创作计划了，萌新有什么看不懂的可以在评论区留言，也欢迎大佬给出珍贵的建议，@AC君求精。

好心人帮我找一下

搞好了,

CSP-J/S 2025游记（10.2更

10.2更 热度要没了！！顶上去！！ 南开大学 & 快去写C++【合作赛#1】 邀请码：KPRR 加团（目前300人） AC君给我点赞置顶了！！！ 注：后续还会持续更新复赛模拟赛和准备 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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，跟估分差不多，希望能进复赛。 DAY -35 今天优先晋级分数线出来了，也是成功的两个组都稳进了，太开心了！！ DAY -34 上午依旧模拟赛，130分爆冷 下午 GESP，飞翔杯没打成（感觉这次人好少，官方下次能不能选个好一点的时间555） DAY -31 初赛分数线出啦！怎么这么低 J 才59.5 DAY -30 一天打三场模拟赛也是醉了…… 上午场 30 分遗憾离场；下午 188 分依旧是一坨，幸好晚上的比较简单，成功拿到 265 分（虽然也不高555 DAY -29 今天休息一天，打了场羽毛球，累趴了 最后，也祝大家 RP++ 考出好成绩！！~