斐波那契数列

互动｜分享你用AI干过的“神级操作”

互动｜分享你用AI干过的“神级操作” hi，AC狗友们 AI时代，连懒人都能开挂！写作业、做笔记、催队友、编曲……今天，它全包了！ 玩法超简单： 在评论区，分享一个你用AI干过的“神级操作” —— 越实用越欢迎，越“又懒又爽”越好！ 举个栗子： * 把老师60页PPT变成3句重点+10道押题：“我用了30秒，AI用了0.3秒。” * 把乱哼的旋律变成一首完整的Lo-fi beats：“现在它是我的学习背景音，比白噪音还上头。” 你可以写： * AI帮你“偷懒”的真实操作 * 一个离谱但实用的AI用法 * AI把你的某个日常变宝的故事 奖励 活动截止，评论区符合参与条件的留言 点赞TOP5 每人获得：罐头 × 50 幸运奖5名 每人获得：罐头 × 20 ⏰ 时间 即日起至 2026年4月20日 分享一个你用AI干过的“神级操作”，越实用越欢迎！ 往期互动

愚人节限定互动｜假如报错信息学说人话

愚人节限定：假如报错信息学会说人话 hi，AC狗友们，愚人节要到了，连编译器都在开玩笑！CE、WA、RE……，它们不装了！ 🎯 玩法超简单： 在评论区，给任意一个报错状态“写一句内心独白”，让它变得有梗、有戏、有灵魂。 举个栗子🌰： * CE（编译错误）：“兄弟，你分号呢？我等你等了三千年。” 你可以写： * 报错的“真实OS”（内心戏） * 报错和代码的“对话” * 报错给你发的“微信消息” 🎁 奖励 活动截止，评论区符合参与条件的留言 点赞TOP5每人获得：罐头 × 50 @Minecraft，@橙子同学，@༺ཌༀ我要上浙大ༀད༻，@天之神_†赛伊德†，@AC君 随机抽取5人，每人获得 罐头 × 20 @（百小1."QYM".4育才）回，@虚无·和平精英，@WeiChenrui，@不喜欢抢钱的抢铁抢段，@ZYC的Best friend ⏰ 时间 即日起至 2026年4月8日 💚 来吧，让那些折磨过你的报错，今天替你“说话”！ 往期互动

#创作计划#最小生成树的构造及应用

叠甲：没事干写一篇好玩，不喜勿喷，有问题欢迎指出，暂时已完结。 本文只讲KRUSKAL，我在VJUDGE拉了个比赛包含所有题目,A-R题为例题，S-Y为附加题。 前置知识：并查集，贪心，树的性质，请先行了解。 一、最小生成树的定义 > 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树．也即在图的边集中选择 𝑛−1𝑛 −1n−1条，将所有顶点连通。我们定义无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。 > FromFromFrom oi-wiki 二、KRUSKAL算法模板 Kruskal算法是一种贪心算法，非常好写，算法的思想是由边权从小到大遍历，只要两个节点还未联通，就把它们连上。维护连通性的问题，套用单次合并O(log⁡n)O(\log n)O(logn) 或者 𝑂(α(𝑚))𝑂(\alpha(𝑚))O(α(m))的并查集即可。加上排序的O(mlog⁡m)O(m\log m)O(mlogm)，Kruskal算法的总复杂度为O(mlog⁡m+mlog⁡n)O(m \log m + m \log n)O(mlogm+mlogn)。 贴上模板代码（即A题代码） 三、例题 B 这就是最大生成树的模板，排序规则改掉就行了。 Code C 跑WWW遍最小生成树，注意在输入时给每条边加一个第几周开放的参数，跑最小生成树时检测边的开放时间是否小于等于当前时间即可，这样就不用每周都排序了。 Code D 假设能使用kkk个卫星设备，就相当于让kkk个点直接连通，在最小生成树中，一定会用k−1k-1k−1条边。那么最优方案就一定是把原图中最长的k−1k-1k−1条边的边权取消，只需输出最小生成树中第kkk长的边即可。 Code E 题目要求我们最大化任意两个部落之间的距离的最小值，实际上这个最小值就是在不同部落的任意两个居住点的最近距离。不难想到在部落内部尽量连较短的边，不让更短的边放在不同部落之间。因为要分为kkk个部落，因此只需要n−kn-kn−k条有用的边（遍历到这条边时两节点还未被联通的边）即可，所以直接输出第n−k+1n-k+1n−k+1条有用边的长度即可。（就是连结两个部落的边中最短的） Code F 构造为图论问题，快速幂预处理连边，没了。 Code G 在线算法不知道怎么办，考虑离线处理，把所有查询的边都放进去排序，跑最小生成树，跑的过程中如果是原本就有的边直接正常处理，如果是查询边，检测这条边是否有用（即两个点是否已联通），如果有用就把Yes放入答案，没有就放入No，注意查询之间相互独立，所以就算有用也千万不要加边。 Code H 直接连边O(n2)O(n^2)O(n2)指定炸，考虑删边，例如当xi≤xj≤xkx_i \leq x_j \leq x_kxi ≤xj ≤xk 时，只需要连接iii与jjj、jjj与kkk，而不需要连iii与kkk。那么我们按x,yx,yx,y分别排序后将相邻点连边即可。可以证明如果一条边是有效的，那么一定不会在按xxx排序和按yyy排序后都被鉴定为无效边。 Code I 就是求在不用第一条边的情况下，第一条边的两个点联通的最小边权。跑第2−m2-m2−m条边最小生成树过程中检测第一条边两个点的连通性即可，注意如果最终都无法联通,输出10910^9109。 Code J 首先买了第 III 样东西，再买第 JJJ样的情况显然可以看做一条边权为KI,JK_{I,J}KI,J 的边，那么直接买一样东西花费AAA元的情况怎么办呢？这时候就可以引入一个超级源点，即000号点，这样就可以把这种情况构造为一条从000联向任意一点的边权为AAA的边了。 Code K 和J题几乎一模一样，挖水井就是向超级源点建边，修筑水道就是普通连边。 Code L 不讲了，L≈\approx≈K，但是注意这是远古题目答案末尾一定要换行！！！我被这个坑了20分钟。 Code M 笑点解析： 感谢PPL友情出演 接近正解的错误方法PPL已经给我们介绍过了，就是建两个超级源点分别代表港口与机场，然后暴力跑Kruskal，但是这样有个问题：我们的目标不是让包括超级源点在内的所有点联通，只是1−n1-n1−n号点的联通，因此可能会出现无效连边（明明1−n1-n1−n号点已经联通了还非要去连接超级源点）。 那么怎么办呢？注意到超级源点可以用也可以不用，那么枚举这两个超级源点的使用情况跑4遍Kruskal即可，注意可以给每条边一个编号，说明它属于机场边，港口边还是道路边，这样就不需要每次枚举使用情况都排序了。 那么为什么J、K、L没有这个问题呢？因为J、K、L题都必须使用超级源点，但是这道题就不一样了。 Code N 先不考虑额外的MMM条边，只看如何最小化生成树的ax+aya_x+a_yax +ay 之和，显然最优方案是一个菊花图，即将所有点都直接连向axa_xax 最小的点。如果不考虑额外MMM条边时，一条边不在最小生成树内，那么再加入MMM条边后，也一定不需要考虑，所以只需要连上原始生成树的N−1N-1N−1条边和额外的MMM条边并跑Kruskal即可。 Code O 不讲了，O≈\approx≈K，建边的公式不同，改一下就行了。 Code P 看完前面的题，你会发现Road真不难 首先因为村庄数少，不难想到遍历所有村庄的修复状态跑2k2^k2k次最小生成树，时间复杂度O(2kmlogm)O(2^kmlogm)O(2kmlogm)，48pts48pts48pts，考虑优化。 根据N题的剪枝方法，在不考虑村庄的情况下不在最小生成树内的边，有了村庄就更不可能在最小生成树内了。那么就可以预处理跑一边Kruskal，将最小生成树内的边放入新的边集，可以大幅缩减边数(1.1×106→1.1×1051.1\times10^6\to1.1\times10^51.1×106→1.1×105)。 根据M题的方法对包含村庄边在内的所有边进行预编号和预排序，这样就不用排2k2^k2k次序了。 最终时间复杂度O(mlogm+2knklogn)O(mlogm+2^knklogn)O(mlogm+2knklogn)，也可以加上启发式合并O(mlogm+2knkα(n))O(mlogm+2^knk\alpha(n))O(mlogm+2knkα(n))。 Code Q 首先肯定是优先连载重限制较大的边最优，所以先将边权从大到小排序，然后用Kruskal重构树。它和普通的Kruskal有区别的一点是Kruskal重构树不是直接连边，而是创造一个虚拟节点，点权就是连接这条边的边权，让连接的两个点成为它的左右儿子，查询两个点路径的最小边权的最大值的问题就转化为查询两个点树上路径经过的虚拟节点的点权的最大值。 下列是关于Kruskal重构树的性质(从PPL那里偷来的)： 结论：对于一个非叶节点 uuu，其点权必然大于其所有祖先的点权。 证明：若uuu的一个祖先的点权大于 uuu 的点权，则 uuu 的祖先必然先被加入重构树，成为 uuu的子树，矛盾。 推论111：对于两个叶节点 uuu , vvv ,其在重构树上的简单路径中点权的最小值必然是两点 LCA 的点权。 证明：两点 LCA 必然是两点简单路径深度最浅的节点。 推论 222：对于两个叶节点 uuu , vvv，其在原图上所有路径边权最小值的最大值必然是两个节点的 LCA 的点权。 证明：若原图上存在一条路径边权的最小值比两点 LCA 的点权（由推论2，该值即两点在树上的简单路径的最小值）更大，则那条边必然比两点 LCA 的点权那条边更早加入重构树，即那条边也应是重构树的一个非叶节点，矛盾。 所以朴素倍增求LCA即可。 Code R 不讲了，R≈\approx≈Q，上题是最大生成树，这题是最小生成树，没了。 Code 大家觉得我有必要写S-Y吗（实际上除了S我一道都不会）

#创作计划#浅谈 AVL 树和红黑树－1

> 请不要发布无意义评论，否则会删评。若发布大量发布类似“qp”“ddd”等评论也会删，发布一次无所谓 > 本篇讲一些前置知识，有点杂，排版和内容可能不是很好，语文也很差，请见谅。由于时间较为零碎，完成不知道要几个世纪了 前言（跳过本部分并不影响您阅读）： 先说一下我为啥写这个，AVL 树在 OI 中似乎啥用没有。但是我觉得学起来挺有意思的，对学红黑树或许有那么一丁点的帮助（？）。就当巩固一下平衡树再提升一下思维吧。 为啥我觉得指针比数组更看得懂呢🤔 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 概览 因为 ACGO 这边的同学知识面普遍较浅，我就讲的稍稍前面一点，但是总不可能让我给你讲输入输出的对吧。二叉树基础（指针），BST，平衡树的旋转操作，Treap（或许并没什么关联）。写的浅一点。鉴定为想水一篇精华帖。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二叉树基础 或许并没什么好讲的，但是因为我偏爱指针而且大部分人都不写指针我就来讲一下（吧）。 首先我们建立一个结构体，用于储存二叉树节点的信息，如下： 其中 Treenode(int v):val(v),l(nullptr),r(nullptr){} 是构造函数。我们每创建一个新的节点，调用这个构造函数就可以“初始化”这一节点。这里的作用是将该节点的值初始为 vvv，左右孩子指针初始为空。 接下来建立一个指针数组，用于存储指向节点 iii 的指针。 这里根据实际情况选择是否需要。像后文所讲的 AVL 树就不需要。 然后是输入，这里的输入方式是每行给出节点 iii 的左右孩子，若为 000 则代表它没有孩子。 前序遍历：顺序为根，左，右，递归即可： 中序遍历：顺序为左，根，右 后序遍历：顺序为左，右，根 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二叉搜索树（BST） 觉得有点跑题了赶紧回来 首先我们了解一下 BST 的基本概念。BST 是一种特殊的二叉树，满足以下性质： 1. 空树为 BST 2. 若左子树不为空，则左子树的所有节点权值小于根节点 3. 若右子树不为空，则右子树所有节点权值大于根节点 4. 二叉搜索树的所有子树均为二叉搜索树 看着很麻烦，但是你先别急。实现起来真的很简单。 节点结构体 不对赘述.具体请参考注释。 插入 主要是个判断，大概这样： 首先，如果与当前节点值相等：计数器加一，返回 如果小于当前节点：有左孩子，递归左孩子；否则新建节点 如果大于当前节点：有右孩子：递归右孩子；否则新建节点 别忘了增加子树大小。 查询前驱——小于 VALVALVAL 的最大数 和插入差不多，因为二叉搜索树保证了 左子树<根节点<右子树

互动｜用一句话证明你是信奥人

用一句话证明你是信奥人 hi，AC狗友们，玩梗时间又到啦！ 只要一句话，让懂的人会心一笑，让不懂的人一脸懵——你就是本届“黑话王者”！ 规则简单到像A+B Problem 在评论区留下一句只有信奥人才懂的梗/黑话/日常—— 可以是你的“当前状态”： > “我命由我不由CE” > “提交10次，AC 0次，心态9次” 也可以是你的“刷题习惯”： > “看到WA第一反应不是‘哇’，是‘Wrong Answer’” > “做梦都在想怎么优化那个O(n²)的循环” …… 🎁 奖励 活动截止，评论区符合参与条件的留言点赞TOP5每人获得， 罐头 × 50； @༺ཌༀ我要上浙大ༀད༻，@盛翰祺（不加团），@༺དༀ༒神.末日审判者༒ༀཌ༻，@格赫罗斯，@奶牛大学招生办 随机抽取5人，每人获得 罐头 × 20 @priority_queue‮， @Shirleynie，@浩云，@༺ཌༀ死·神ༀད༻，@上海交通大学-章老师 ⏰ 时间 即日起至 2026年3月29日 23:59 📮 参与方式 直接在本帖评论区留言，坐等点赞收割！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💚 来吧，让我看看谁的“信奥含量”超标！ 往期互动

眼前这个男人

眼前这个男人只是在 ppl 的犇犇后面回复了一句就被洛谷予以禁言十四天的奖励。 （或者说可能不是这个原因，我也记不得我有没有单独发过那个网站的链接。 和这个男人一起的还有 pipilong2024，yanghongzheng，Konglh1013，jodio9等人，具体可以参考洛谷陶片。 看来我要掉橙了，加油缓过来吧。 笑点解析：永远在红和橙之间反复横跳，本来以为过了一片题解可以稳住红一周的，结果被洛谷大手子制裁了，掉了五十估值（（（ 反正被禁言了，既来之则安之。等我期中考结束我要发力了。

就算结果已然注定，我也要放手一搏

可能更好的阅读体验 发现有些洛谷折叠框不能在 ACGO 讨论区很好的渲染，所以将就着看吧，更好的阅读体验可以直接看原文。 本文章会持续更新。 引言 * 2026 csp-s 同年龄选手省排 30+。 不敢说目标是进队，但再怎么样我也不想让童年的梦就此草草落幕。 PART 1 > 短期的目标是以每周六到下周五（恰好是一周，为什么不是完整的一周有个人原因）为一个周期，就近年真题单独训练部分知识点。 WEEK 1（4.4-4.10） > 图论 MST P14362 [CSP-S 2025] 道路修复 * 难度：蓝 * 耗时：浏览题解 fv9j9qo5 思路后 30min 调出 水蓝。 本题部分分非常充裕，考虑直接暴力枚举每个乡村是否进行城市化改造，再暴力求 MST 最小代价更新答案，可以得到 48pts 的高分，考场上我是对其又进行了一部分随机化乱搞拿到了 60pts。 考场代码又臭又长，也没有参考价值就不放了。 ::::error[48pts] :::: 注意到所有非原图 MST 的边无论是否加入城市化改造乡村的边，都是没有任何竞争力的，可以直接扔掉。 这步操作将一次 solve 的复杂度从 O(mlog⁡m)O(m\log m)O(mlogm) 优化到了 (nklog⁡nk)(nk\log nk)(nklognk)，可以得到 80pts，这里已经非常接近正解了。 ::::warning[80pts] :::: 注意到 dfs 函数已经无法优化了（严谨地表述是很难优化），算法瓶颈在于 solve 函数中的 sort。考虑提前排序好，若该边不在所选边的集合中，直接跳过即可。 ::::success[100pts] :::: P1967 [NOIP 2013 提高组] 货车运输 * 难度：蓝 * 耗时：一眼瞪出正解，实现花了 30min+。 * 二刷 这纯拼好题吧，咋这么板。 显然走一条限重小的边当且仅当它能连通两个连通块，不得不走。所以考虑直接对原图按边权降序排序后做一个 Kruskal，所有非树边没有任何价值。求出重构树后问题等价于求树上两点之间路径边权最小值，LCA 实现。 ::::success[100pts] Link :::: CF1245D SHICHIKUJI AND POWER GRID * 难度：绿 * 耗时：12min 双倍经验：P1550。 板板板。 考虑建一个超级源点，用于记录一个点是否通上电，然后暴力建边跑 Kruskal。 ::::success[100pts] Link :::: AT_ABC270_F [ABC270F] TRANSPORTATION * 难度：绿 * 耗时：忘了，30min-。 板板板。 与上类似，建两个超级源点。 ::::error[WA 1+15] Link :::: 注意到当 1−n1-n1−n 的点已经联通后，两个超级源点没有连通的必要。 继续只跑一遍 Kruskal 特判一些东西也是可做的，但是就 * 机场港口都不用 * 只用机场 * 只用港口 * 机场港口都用 分四类取最优值更清晰。 ::::success[AC] Link :::: CF1120D POWER TREE * 难度：紫 * 耗时：思考近一天无果浏览 z692g8r0 题解后 1h 内调出 难难难。 妙妙题。 这里只介绍本题中我认为最精华的转换部分，细节可以参考原题解。 注意到任意节点的子树内时间戳都是连续的，所以我们可以将每一个点所能控制的叶节点抽象成一个区间（为了使相邻叶节点的时间戳连续，这里只对叶节点计算时间戳）。 所以问题变为给定一个序列和若干个区间，每个区间对应一个代价，每次可以将区间内的元素任意加减，求将序列元素全部清零的最小代价以及方案， 不妨考虑差分，对于 [l,r][l,r][l,r]，每次可以将 dld_ldl 上的数全部移至 dr+1d_{r+1}dr+1 ，直到所有数都在 dn+1d_{n+1}dn+1 上（这里 ddd 为差分数组）。 再做一步转换：[l,r][l,r][l,r] 对应着连接 lll 和 r+1r+1r+1 的边，求使 n+1n+1n+1 与其它节点连通的最小代价。 MST 实现即可。 ::::success[AC] Link :::: P12375 「LAOI-12」MST? * 难度：绿 * 耗时：忘了。 这个就推式子啊，没啥好说的，静下心来慢慢推就会了。 ::::success[100pts] Link :::: P4768 [NOI2018] 归程 * 难度：紫 * 耗时：思考三天无果，结合多篇题解后实现花了 40min。 哎这东西其实超纲了，害得我花了十来分钟补了一下 Kruskal 重构树，这个就当例题去做了。 首先有一个非常显然的暴力，对于每一次询问暴力跑 Dijkstra，做一个简单的分层图存储当前节点是否还有车可以开。 ::::warning[40pts] Link :::: 注意到问题可以转化为先求出所有可以通过海拔高于 ppp 的边连通的点集，答案即为点集中所有点到 111 的最小距离。 后者可以先提前跑一遍 Dijkstra 预处理好每个点到 111 的最小距离，但是求点集就得靠黑科技了（。 当我们按边权降序建出 Kruskal 重构树后其必然满足以下性质。 一些定义内容可以参考 OI-wiki。 ::::info[一些性质]{open} * 结论：对于一个非叶节点 uuu，其点权必然大于其所有祖先的点权。 证明：若 uuu 的一个祖先的点权大于 uuu 的点权，则 uuu 的祖先必然先被加入重构树，成为 uuu 的子树，矛盾。 * 推论 111：对于两个叶节点 u,vu,vu,v，其在重构树上的简单路径中点权的最小值必然是两点 LCA 的点权。 证明：两点 LCA 必然是两点简单路径深度最浅的节点。 * 推论 222：对于两个叶节点 u,vu,vu,v，其在原图上所有路径边权最小值的最大值必然是两个节点的 LCA 的点权。 证明：若原图上存在一条路径边权的最小值比两点 LCA 的点权（由推论 222，该值即两点在树上的简单路径的最小值）更大，则那条边必然比两点 LCA 的点权那条边更早加入重构树，即那条边也应是重构树的一个非叶节点，矛盾。 :::: 这些性质就很重要。 当两个点能直接用汽车连通，必然满足两点之间存在一条边权最小值大于 ppp 的路径，换而言之，若两点所有路径边权最小值的最大值大于 ppp，则一定存在一条这样的路径，也就是一定能直接用汽车连通（代价为 000）。 故我们考虑直接从 vvv 开始往上慢慢跳，找到一个深度最浅的祖先节点，满足其点权仍大于 ppp，则所求点集即为其子树。 这一步可以用倍增加速。 ::::info[略证]{} 不妨设该点为 ttt。 * 对于所有 ttt 子树内的节点，由于两点之间简单路径的最小值（因为两点的 LCA 深度一定小于 ttt，所以至少是 ttt 的点权，可能更大，不会更小）大于 ppp，故一定存在一条路径使得其所有边的海拔均大于 ppp，可以直接用汽车连通。 * 对于所有非 ttt 子树内的节点，两点之间最短路径的最小值（两点 LCA 的深度一定大于 ttt，故该值一定小于 ttt 的点权）必然不大于 ppp（若大于 ppp 则 ttt 能继续往上跳），一定无法用汽车连通。 :::: 点集求出来了，到 111 的最小距离用一个简单的树形 DP 就可以实现了，每个点其子树到 111 的最小距离就是其两个子节点到 111 最小距离的最小值。 ::::success[100pts] Link :::: WEEK 2（4.11-4.17） > 图论 MST + Kruskal 重构树 > 看心情做几道蓝绿 MST，这周主要是把 Kruskal 重构树夯实掉。 P4899 [IOI 2018] WEREWOLF 狼人 * 难度：紫 * 耗时：15min 内想出 15pts 做法，浏览题解后套一个扫描线就过了。 想不到啊，导致我没能独立切图论紫的真正原因是数据结构没学好。 很显然对于每一个询问我们要求出从 SSS 开始人形所能到达的点集，从 EEE 开始狼形所能到达的点集，查有无交。 这个可以用两颗 Kruskal 重构树解决，边权恰好为两点的最小值和最大值，具体地懒得说了，非常好想，细节可以参考代码。 求交的花我一开始想到的是用 bitset 维护每个节点其子树下包含节点的情况，1 表示含，0 反之。 ::::error[15pts] Link :::: 然后注意到其实这个东西用扫描线离线处理一下就行，然后就好了（？） ::::success[100pts] Link :::: P4197 [ONTAK2010] PEAKS * 难度：紫 * 耗时：3min 以内想出图论部分，猜到有一个数据结构可以快速求区间第 kkk 大值，但是不会，看题解后套入主席树模板 AC。 我真得去学学主席树了，上题也能用这个。 “困难值小于等于 xxx”显然是 Kruskal 重构树。 用时间戳维护一下每个点其子树包含的叶节点即可。 ::::success[100pts] Link ::::

谁能帮我取个名啊

我身边的同学和朋友都说我的名字太猎奇了，所以我想请大家帮我取个名字。我的特征如下： 星座：处女座 爱好：看小说和听术力口 最爱的书：《某某》《二哈和他的白猫师尊》《她的山她的海》《一屋暗灯》(我同学说我是小黄人，真的吗？） 最爱的音乐：《脑蚀》《爱属性》《即刻轮回》《普通DISCO》《Time Machine》 最爱的游戏：florr.io 最爱的动漫：我不看动漫 最爱的主播：影视飓风 特长：感觉写作还可以，给一个软件投过两篇稿，都中了 同学对我的评价：老抽、神人一个、国一曼巴(我不认可这个) 我对自己的评价：亭亭玉立、善良大方、聪明不绝顶 麻烦各位在评论区给我想个名字，取得好可以获得我包下的全世界的空气，随便吸。

【学习笔记】随机游走优化 dp

感觉是比较冷门的技巧（） 点击这里获得更卡哇伊的阅读体验 引入 > 一个数轴，初始有一个点在 000 位置。现在这个点会移动 nnn 次，每一次有 12\frac1221 的概率点从 xxx 移动到 x+1x+1x+1，另外 12\frac1221 的概率点从 xxx 移动到 x−1x-1x−1。问移动完 nnn 次之后 ∣x∣|x|∣x∣ 的期望值是多少。 上述问题的答案不超过 O(n)O(\sqrt n)O(n ) 级别。下面给出一个简单的证明： 直接计算 E[∣x∣]E[|x|]E[∣x∣] 比较复杂。考虑先放缩一下，计算出 E[x2]E[x^2]E[x2] 的值，然后就可以直接得到 E[∣x∣]≤E[x2]E[|x|]\le \sqrt{E[x^2]}E[∣x∣]≤E[x2] 。 记第 iii 步 xxx 移动的决策是 pip_ipi （也就是 xxx 在第 iii 次操作中移动到了 x+pix+p_ix+pi 位置）。则显然有 x2=(p1+p2+…+pn)2x^2=(p_1+p_2+\ldots+p_n)^2x2=(p1 +p2 +…+pn )2，也就可以得到 E[x2]=∑i=1nE[pi2]+2∑i=1n∑j=i+1nE[pipj]=n+2∑i=1n∑j=i+1nE[pipj]E[x^2]=\sum\limits_{i=1}^nE[p_i^2]+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]=n+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]E[x2]=i=1∑n E[pi2 ]+2i=1∑n j=i+1∑n E[pi pj ]=n+2i=1∑n j=i+1∑n E[pi pj ]。又因为决策之间是两两独立的，所以直接分类 pi,pjp_i,p_jpi ,pj 的取值分别算期望，可以得到 E[pipj]=0E[p_ip_j]=0E[pi pj ]=0，也就得到了 E[x2]=n⇒E[x]≤O(n)E[x^2]=n\Rightarrow E[x]\le O(\sqrt n)E[x2]=n⇒E[x]≤O(n )。 现在在上面的问题上扩展，考虑另外一个与其相似的问题： > 一个数轴，初始有一个点在 000 位置。现在这个点会移动 nnn 次，每一次有 12\frac1221 的概率点从 xxx 移动到 x+1x+1x+1，另外 12\frac1221 的概率点从 xxx 移动到 x−1x-1x−1。问移动完 nnn 次后，xxx 移动到的全部 n+1n+1n+1 个位置中绝对值最大的点的期望值是多少。 解决完上一个问题之后容易猜测答案还是 O(n)O(\sqrt n)O(n ) 级别的。下面给出一个证明： 设随机游走位置为 S0=0,Sk=ξ1+ξ2+⋯+ξkS_0=0,S_k=\xi_1+\xi_2+\cdots+\xi_kS0 =0,Sk =ξ1 +ξ2 +⋯+ξk ，其中每个 ξi\xi_iξi 有 12\frac1221 的概率为 111，另外 12\frac1221 的概率为 −1-1−1。为了方便，记 Mi=max⁡j=0i∣Sj∣M_i=\max\limits_{j=0}^i|S_j|Mi =j=0maxi ∣Sj ∣ 即前 iii 次移动中距离原点最远的距离是多少。 因为 MnM_nMn 是非负整数，所以 E[Mn]=∑t≥1Pr⁡(Mn≥t)\mathbb E[M_n]=\sum_{t\ge1}\Pr(M_n\ge t)E[Mn ]=∑t≥1 Pr(Mn ≥t)。 所以只要我们能证明 Pr⁡(Mn≥t)≤Ce−ct2/n\Pr(M_n\ge t)\le C e^{-c t^2/n}Pr(Mn ≥t)≤Ce−ct2/n，把这个式子对 ttt 求和，就会得到 E[Mn]=O(n)\mathbb E[M_n]=O(\sqrt n)E[Mn ]=O(n )。 事件 Mn≥tM_n\ge tMn ≥t 的意思是：在前 nnn 步里，曾经到过 ttt 或者 −t-t−t。所以 Pr⁡(Mn≥t)≤Pr⁡(max⁡0≤k≤nSk≥t)+Pr⁡(min⁡0≤k≤nSk≤−t) \Pr(M_n\ge t) \le \Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr) + \Pr\Bigl(\min_{0\le k\le n}S_k\le -t\Bigr)Pr(Mn ≥t)≤Pr(max0≤k≤n Sk ≥t)+Pr(min0≤k≤n Sk ≤−t)。 由于对称性，这两项相等，因此有：Pr⁡(Mn≥t)≤2Pr⁡(max⁡0≤k≤nSk≥t)\Pr(M_n\ge t)\le 2\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)Pr(Mn ≥t)≤2Pr(max0≤k≤n Sk ≥t)。 现在用一维随机游走最经典的“反射法”结论：Pr⁡(max⁡0≤k≤nSk≥t)≤2Pr⁡(Sn≥t)\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)\le 2\Pr(S_n\ge t)Pr(max0≤k≤n Sk ≥t)≤2Pr(Sn ≥t)，结合一下就可以得到 Pr⁡(Mn≥t)≤4Pr⁡(Sn≥t)\Pr(M_n\ge t)\le 4\Pr(S_n\ge t)Pr(Mn ≥t)≤4Pr(Sn ≥t)。 此时又因为 Sn=ξ1+⋯+ξnS_n=\xi_1+\cdots+\xi_nSn =ξ1 +⋯+ξn 是 nnn 个独立 ±1\pm1±1 的和，所以它的方差是 nnn，标准差是 n\sqrt nn 。更进一步，SnS_nSn 有高斯型尾估计：Pr⁡(Sn≥t)≤e−t2/(2n)\Pr(S_n\ge t)\le e^{-t^2/(2n)}Pr(Sn ≥t)≤e−t2/(2n)，因此 Pr⁡(Mn≥t)≤4e−t2/(2n)\Pr(M_n\ge t)\le 4e^{-t^2/(2n)}Pr(Mn ≥t)≤4e−t2/(2n)。 结合一开始得到的式子，有： E[Mn]=∑t≥1Pr⁡(Mn≥t)≤∑t≥14e−t2/(2n)\mathbb E[M_n]= \sum_{t\ge1}\Pr(M_n\ge t)\le\sum_{t\ge1}4e^{-t^2/(2n)}E[Mn ]=t≥1∑ Pr(Mn ≥t)≤t≥1∑ 4e−t2/(2n) 而这个和的量级就是 n\sqrt nn 。最简单的看法是把它和积分比较： ∑t≥1e−t2/(2n)≤∫0∞e−x2/(2n)dx=n∫0∞e−u2/2du=Cn\sum_{t\ge1}e^{-t^2/(2n)} \le \int_0^\infty e^{-x^2/(2n)}{dx}= \sqrt n\int_0^\infty e^{-u^2/2}du= C\sqrt n t≥1∑ e−t2/(2n)≤∫0∞ e−x2/(2n)dx=n ∫0∞ e−u2/2du=Cn 所以有 E[Mn]≤4Cn\mathbb E[M_n]\le 4C\sqrt nE[Mn ]≤4Cn 。于是得到最终结论： E[Mn]=O(n)\boxed{\mathbb E[M_n]=O(\sqrt n)} E[Mn ]=O(n ) 事实上，可以继续收紧上下界得到 E[Mn]∼πn2\mathbb E[M_n]\sim\sqrt{\frac{\pi n}2}E[Mn ]∼2πn ，但是我不会证，而且在实际题目中并不需要这么紧的上界，因此这里直接给出一个由 ChatGPT 5.4 Thinking 给出的证明过程： :::info[证明过程] 设随机游走的过程为： S0=0,Sk=∑i=1kξi,Pr⁡(ξi=1)=Pr⁡(ξi=−1)=12,S_0=0,\qquad S_k=\sum_{i=1}^k \xi_i,\qquad \Pr(\xi_i=1)=\Pr(\xi_i=-1)=\frac12, S0 =0,Sk =i=1∑k ξi ,Pr(ξi =1)=Pr(ξi =−1)=21 , 题目要求的是 Mn:=max⁡0≤k≤n∣Sk∣M_n:=\max_{0\le k\le n}|S_k|Mn :=max0≤k≤n ∣Sk ∣ 的期望 E[Mn]\mathbb E[M_n]E[Mn ]。 1. 先写成尾和公式 因为 MnM_nMn 是非负整数值随机变量，所以： E[Mn]=∑m≥1Pr⁡(Mn≥m).\mathbb E[M_n]=\sum_{m\ge1}\Pr(M_n\ge m). E[Mn ]=m≥1∑ Pr(Mn ≥m). 而 nnn 步最多走到距离 nnn，所以实际上： E[Mn]=∑m=1nPr⁡(Mn≥m)\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Pr(M_n\ge m)} E[Mn ]=m=1∑n Pr(Mn ≥m) 也就是： E[Mn]=∑m=1n(1−Pr⁡(Mn<m))\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Bigl(1-\Pr(M_n<m)\Bigr)} E[Mn ]=m=1∑n (1−Pr(Mn <m)) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 精确公式 事件 Mn<mM_n<mMn <m 就是“前 nnn 步始终没有碰到 ±m\pm m±m”，也就是随机游走在区间 −m+1,−m+2,…,m−1{-m+1,-m+2,\dots,m-1}−m+1,−m+2,…,m−1 内存活到第 nnn 步。 这是经典吸收随机游走，谱分解可得： Pr⁡(Mn<m)=1m∑j=0m−1(−1)jcot⁡(2j+1)π4m,(cos⁡(2j+1)π2m)n.\Pr(M_n<m) = \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n. Pr(Mn <m)=m1 j=0∑m−1 (−1)jcot4m(2j+1)π ,(cos2m(2j+1)π )n. 因此： E[Mn]=∑m=1n[1−1m∑j=0m−1(−1)jcot⁡(2j+1)π4m,(cos⁡(2j+1)π2m)n].\boxed{ \mathbb E[M_n] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. } E[Mn ]=m=1∑n [1−m1 j=0∑m−1 (−1)jcot4m(2j+1)π ,(cos2m(2j+1)π )n]. 这就是这个期望的一个标准精确表达式。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 渐近结果 当 n→∞n\to\inftyn→∞ 时，有经典极限定理： Mnn ⟹ sup⁡0≤t≤1∣Bt∣\frac{M_n}{\sqrt n}\ \Longrightarrow\ \sup_{0\le t\le 1}|B_t| n Mn  ⟹ 0≤t≤1sup ∣Bt ∣ 其中 BtB_tBt 是标准布朗运动。并且该极限随机变量的期望是： E[sup⁡0≤t≤1∣Bt∣]=π2\mathbb E\Bigl[\sup_{0\le t\le 1}|B_t|\Bigr] = \sqrt{\frac{\pi}{2}} E[0≤t≤1sup ∣Bt ∣]=2π 所以： E[Mn]∼πn2\boxed{\mathbb E[M_n]\sim \sqrt{\frac{\pi n}{2}}} E[Mn ]∼2πn 也就是主项约为： E[Mn]≈1.253314n.\mathbb E[M_n]\approx 1.253314\sqrt n. E[Mn ]≈1.253314n . ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 对比一下末位置 注意这不是最后位置 ∣Sn∣|S_n|∣Sn ∣ 的期望。后者是 E∣Sn∣∼2nπ,\mathbb E|S_n|\sim \sqrt{\frac{2n}{\pi}},E∣Sn ∣∼π2n ,，而这里取的是全过程的最大绝对值，所以更大，主常数变成了 π2\sqrt{\frac{\pi}{2}}2π 。 5. 最终结论 精确值： E![max⁡0≤k≤n∣Sk∣]=∑m=1n[1−1m∑j=0m−1(−1)jcot⁡!(2j+1)π4m,(cos⁡!(2j+1)π2m)n].\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot!\frac{(2j+1)\pi}{4m}, \Bigl(\cos!\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. } E![0≤k≤nmax ∣Sk ∣]=m=1∑n [1−m1 j=0∑m−1 (−1)jcot!4m(2j+1)π ,(cos!2m(2j+1)π )n]. 渐近值： E![max⁡0≤k≤n∣Sk∣]∼πn2\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] \sim \sqrt{\frac{\pi n}{2}}} E![0≤k≤nmax ∣Sk ∣]∼2πn ::: 解决问题 考虑用上面给出的 trick 解决一道经典题目！ 题目给出的六边形网格不太好处理，因此容易想到把这个东西压扁，将六个方向修改为上，下，左，右，右上，左下。此时容易想到直接 dp。设 fi,x,y,j,kf_{i,x,y,j,k}fi,x,y,j,k 表示当前处理了前 iii 个 idea，L=j,G=kL=j,G=kL=j,G=k，当前网格的横坐标是 xxx，纵坐标是 yyy，是否是可行的状态。 考虑优化这个 dp。可行性 dp 通常有下面两种优化方法： * 把一维状态写到答案里。 * 用 bitset 优化。 这个问题看着很不能把状态写到答案里，因此考虑用 bitset 优化。发现 yyy 这个 dp 维度其实就是在做一次循环移位操作，用 bitset 优化可以让时间复杂度除一个 www，但是仍然难以通过。 考虑利用上面的 trick。注意到最后需要让所在的位置 (x,y)(x,y)(x,y) 回到 (0,0)(0,0)(0,0)，而上面的 trick 在更高维度上也同样满足距离 (0,0)(0,0)(0,0) 的曼哈顿距离期望为 O(n)O(\sqrt n)O(n ) 级别。因此考虑直接随机打乱输入的 idea 顺序，此时对于距离原点超过 O(n)O(\sqrt n)O(n ) 的位置，其很大概率是可以被不超过 O(n)O(\sqrt n)O(n ) 的位置所替代的，因此只需要处理 x,y∈[−O(n),O(n)]\boldsymbol{x,y\in[-O(\sqrt n),O(\sqrt n)]}x,y∈[−O(n ),O(n )] 的部分，范围以外的 dp 值直接截断处理即可。此时算法的时间复杂度被优化到 O(n2p2w)O(\frac{n^2p^2}w)O(wn2p2 )，卡常后可以通过该题。 :::success[代码] 因为作者不太会卡常所以目前只有用 C++98 提交才能通过/kel ::: 练习 > 给定一个 nnn 个结点的树，每条边都有边权（边权可能为负）。你需要选择若干条有 444 条边组成的简单路径（可以不选），使得没有一条边被超过一条路径覆盖。问所有被路径覆盖的边的边权的和最大是多少。 > > 数据范围：2≤n≤2×1052\le n\le 2\times 10^52≤n≤2×105。 考虑一个暴力的 dp 做法。设 fi,0/1/2/3f_{i,0/1/2/3}fi,0/1/2/3 表示当前只处理 iii 结点为根的子树，iii 结点没有挂长度不为 444 的链 / 在子树里挂了一条长度为 1/2/31/2/31/2/3 的链，边权之和最大是多少。转移过程需要合并儿子结点的 dp 信息，考虑再记一个 dp 数组辅助转移：设 gi,0/1g_{i,0/1}gi,0/1 表示当前合并了若干个儿子结点的信息，其中儿子结点里长度为 000 的链比长度为 222 的链多 iii 条，长度为 111 的链数量  mod  2=0,1\bmod\ 2=0,1mod 2=0,1，边权和最大是多少（只记录这些信息是因为子树内合并链只能是长度为 0,20,20,2 的链对应匹配，长度为 111 的链单独匹配）。此时合并信息是简单的。 直接做转移时间复杂度为 O(n2)O(n^2)O(n2)。注意到辅助转移的 ggg 数组中 iii 维度维护的是两类儿子结点的链的差值，而一个儿子结点只能有最多一条连向父亲结点的链，最后可以转移到 fff 数组里的 ggg 也只有 g−1,∗,g0,∗,g1,∗g_{-1,*},g_{0,*},g_{1,*}g−1,∗ ,g0,∗ ,g1,∗ 三类。因此考虑把长度为 000 的链看作 111，长度为 222 的链看作 −1-1−1，则可以看作是在数轴上做随机游走，打乱儿子结点顺序后 gig_igi 这个维度只需要维护 O(n)O(\sqrt n)O(n ) 个 iii 的信息即可。此时算法的时间复杂度优化到 O(nn)O(n\sqrt n)O(nn )，可以通过该题。 :::success[代码] :::

旅游攻略（浙江嘉兴平湖）

1.东湖/明湖必去！！！夏天还有西瓜灯节（明湖）！🍉🍉🍉 2.李叔同纪念馆门口有鸽子！可以喂！ 3.美食推荐：新仓小鲁苏，粽子（嘉兴），踏（ta）饼，西瓜😋😋 4.平湖博物馆：很漂亮，还有不定时活动！！ 5.西瓜乐园：适合小朋友去！ 6吾悦广场：平湖最好逛的商城！有海底捞，电影院，肯德基，蜜雪冰城…… （欢迎投稿！！！）