我们班梗王zyx（2）#4

互动｜分享你用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我一道都不会）

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

用一句话证明你是信奥人 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 📮 参与方式 直接在本帖评论区留言，坐等点赞收割！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💚 来吧，让我看看谁的“信奥含量”超标！ 往期互动

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

可能更好的阅读体验 发现有些洛谷折叠框不能在 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 ::::

#创作计划#浅谈 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 的最大数 和插入差不多，因为二叉搜索树保证了 左子树<根节点<右子树

有没有浙江的朋友，进来看看吧

你们春假什么时候到啊，想去哪啊，我实在没脑子，找不到去哪啊，有没有人给点建议啊

消失的下雨天 我好想再淋一遍

同步在洛谷更新 题目难度应该不会很大 括号内的是 CF 难度，如果不是 CF 的题的话可能会根据体感难度来估算一个 CF 难度（ 2026.03.11 天空仍灿烂 / 它爱着大海（周杰伦 花海） 001. CF1656F PARAMETRIC MST (*2600\RED{2600}2600) 未看题解完成，用时 1hr 29min 18s。 注意到 aiaj+t(ai+aj)=(ai+t)(aj+t)−t2a_ia_j+t(a_i+a_j)=(a_i+t)(a_j+t)-t^2ai aj +t(ai +aj )=(ai +t)(aj +t)−t2（恭喜你你做完了这个题最难的一步）。最后的 t2t^2t2 是容易省去的，于是问题可以转化为： > 对于给定的 ttt 值，你可以构造一棵 nnn 个点的完全图，其中两点 (i,j)(i,j)(i,j) 的边权是 (ai+t)(aj+t)(a_i+t)(a_j+t)(ai +t)(aj +t)，记 f(t)f(t)f(t) 为按照上述步骤构造的图的 MST 边权之和，问 f(t)f(t)f(t) 是否是有上界的。 先考虑对于给定的 ttt 值怎么快速求出构造出完全图的 MST 大小。把所有点的点权 aia_iai 按照从小到大的顺序排序，那么显然此时有 a1+t≤a2+t≤…≤an+ta_1+t\le a_2+t\le\ldots\le a_n+ta1 +t≤a2 +t≤…≤an +t。容易想到记 ppp 是满足 ap+t≥0a_p+t\ge 0ap +t≥0 的 ppp 里最小的值，那么直接贪心的把 ap,ap+1,…,ana_p,a_{p+1},\ldots,a_nap ,ap+1 ,…,an 都和 a1a_1a1 连边，a2,a3,…,ap−1a_2,a_3,\ldots,a_{p-1}a2 ,a3 ,…,ap−1 都和 ana_nan 连边，容易证明该贪心策略一定可以得到最优解。 把这个式子写出来，即： ∑i=pna1ai+t∑i=pn(a1+ai)+∑i=2p−1anai+t∑i=2p−1(an+ai)\sum\limits_{i=p}^na_1a_i+t\sum\limits_{i=p}^n(a_1+a_i)+\sum\limits_{i=2}^{p-1}a_na_i+t\sum\limits_{i=2}^{p-1}(a_n+a_i) i=p∑n a1 ai +ti=p∑n (a1 +ai )+i=2∑p−1 an ai +ti=2∑p−1 (an +ai ) 化简式子： a1∑i=1nai+t(n−p+1)a1+t∑i=pnai+an∑i=2p−1ai+t(p−2)an+t∑i=2p−1aia_1\sum\limits_{i=1}^na_i+t(n-p+1)a_1+t\sum\limits_{i=p}^na_i+a_n\sum\limits_{i=2}^{p-1}a_i+t(p-2)a_n+t\sum\limits_{i=2}^{p-1}a_i a1 i=1∑n ai +t(n−p+1)a1 +ti=p∑n ai +an i=2∑p−1 ai +t(p−2)an +ti=2∑p−1 ai 容易发现这个东西如果对 ttt 已知 ppp 那么可以预处理 aaa 序列前缀和然后做到 O(1)O(1)O(1) 计算答案。 但是问题是 ttt 的取值范围是 t∈Rt\in\mathbb Rt∈R，显然无法枚举所有的实数 ttt 来计算答案。考虑缩小最优解的 ttt 的取值集合。这里注意到对 t∈[ai,ai+1]t\in[a_i,a_{i+1}]t∈[ai ,ai+1 ]，ppp 的取值都不会变化，而显然对同一个 ppp 上面的式子是单峰的答案一定取在两个端点上，因此需要判定的 ttt 的集合只有 −a1,−a2,…,−an-a_1,-a_2,\ldots,-a_n−a1 ,−a2 ,…,−an ，而此时显然 ppp 的值也是十分容易求出的。因此该算法时间复杂度优化到 O(n)O(n)O(n) 可以通过该题。 最后剩下答案为 INF 的情况，直接带入 t=∞t=\infint=∞ 和 t=−∞t=-\infint=−∞ 即可简单判定（只需要看此时 ∞\infin∞ 的项的系数是不是 >0>0>0 的即可）。 该算法对于单组数据时间复杂度为 O(n)O(n)O(n)，可以轻松通过该题。 002. CF521D SHOP (*2800\RED{2800}2800) 未看题解完成，用时 34min 7s。 对一个位置而言赋值操作肯定最多进行一次，因此考虑直接贪心。注意到一定存在一个最优策略满足对每个位置，其执行的操作的顺序都是（赋值）-（加法）-（乘法），括号代表一个操作可有可无。证明可以简单 Exchange-Argument Trick 处理。 考虑先把所有的赋值操作对每个位置只保留赋值最大的操作，然后将其全部转化成加法操作，然后再把加法操作排序之后全部转化成乘法操作。乘法操作直接贪心选最大的 mmm 个数执行操作即可。 总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) 可以轻松通过该题。 2026.03.12 一路不断失去 / 一生将不断见证 / 看过再多风景眼眸如初清澄（周深 亲爱的旅人啊） 003. CF852A DIGITS（*2500\COLOR{PINK}{2500}2500） 未看题解完成，用时 26min 18s。 有一个简单的贪心策略是直接把每个位置都拆开得到 ∣s∣|s|∣s∣ 个长度为 111 的数字然后直接加起来，但是这个贪心显然是错的。 考虑直接错上加错，以一定概率把两个长度为 111 的数字合并起来（实测概率取 115\frac1{15}151 可以通过）然后再加起来合并，就可以通过这题。 成功率不太会算，但是这一看就很不能卡 :) 004. 暂时不能公开 2026.03.13 好想再问一遍 / 你会等待还是离开（周杰伦 晴天） 005. P15653 [省选联考 2026] 星图 / STARMAP（*33003{\RED{300}}3300） 直接在原图上维护操作是困难的，套路的考虑在图的反图上执行操作，这样问题转化为要求执行操作使得最终图上边的数量最少。 光轨数量的最大值 为了方便计算，该部分的讨论都将在原图的补图上进行。 考虑从奇偶性的方向入手。注意到若一次恰好可以选择 kkk 个点并对其执行操作，则 k=2k=2k=2 需要单独讨论。当 k>2k>2k>2 时： * k≡0(mod4)k\equiv 0\pmod 4k≡0(mod4)，此时点的度数的奇偶性不会发生变化，但边的数量的奇偶性会发生变化，因此此时最少剩下的边的数量即为 [2∤m][2\nmid m][2∤m]。 * k≡1(mod4)k\equiv 1\pmod 4k≡1(mod4)，此时点的度数的奇偶性会发生变化，且边的数量的奇偶性也会发生变化。此时需要进一步分类讨论： * 若 [2∣m]=[2∣∑i=1n[2∤deg⁡i]2][2\mid m]=[2\mid\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2][2∣m]=[2∣2i=1∑n [2∤degi ] ]，则此时显然可以在不改变奇偶性的前提下把边数删到答案下界 ∑i=1n[2∤deg⁡i]2\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}22i=1∑n [2∤degi ] 。 * 否则： * 若图上所有点的度数都为偶数，则此时最小可以达到的答案是 333。 * 若图上存在点的度数是奇数，则此时最小可以达到的答案为 ∑i=1n[2∤deg⁡i]2+1\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2+12i=1∑n [2∤degi ] +1。 * k≡2(mod4)k\equiv 2\pmod 4k≡2(mod4)，此时点的度数的奇偶性不会发生变化，且边的数量的奇偶性也不会发生变化，因此此时最少剩下的边的数量即为 000。 * k≡3(mod4)k\equiv 3\pmod 4k≡3(mod4)，此时点的度数的奇偶性会发生变化，但边的数量的奇偶性不会发生变化。最后剩下的边一定是若干个奇数度数的点两两匹配，答案即为 ∑i=1n[2∤deg⁡i]2\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}22i=1∑n [2∤degi ] 。 而 k=2k=2k=2 显然是简单的，必然可以在补图上删空所有的边。 最后用总数 n(n−1)2\frac{n(n-1)}22n(n−1) 减去上面得到的答案就可以得到最终结果。 构造流程 考虑先从特殊情况入手： 0X01 K=2K=2K=2 显然每次操作一条被连起来的边就可以删除该边。 0X02 K=3K=3K=3 此时操作形如每次反转一个三元环。容易想到先简单消去图上所有的环，得到一个森林。 然后对于森林上每一个非单独结点组成的树结构，均可以通过下面的操作让该树最终剩下恰好一条边： * 选择三个点 u,v,wu,v,wu,v,w 满足当前树上存在一条 u↔v↔wu\leftrightarrow v\leftrightarrow wu↔v↔w 的链。 * 对 u,v,wu,v,wu,v,w 三个点做一次操作，此时 vvv 点脱离树结构成为单独点，u,wu,wu,w 两点之间连了一条边。 容易发现这样恰好可以取到前面分析 k=2k=2k=2 部分的答案下界，因此该构造方案可以证明为最优解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 剩下 k>3k>3k>3 的情况。此时考虑先讨论如何构造出简单结构的操作： 0X11 长度为 444 的环 考虑类比 P9841 的套路，通过调用若干次操作得到一个比较简单的操作形式。 考虑执行下面的 444 次操作： * Step 111：x1,x2,…,xk−2,i,jx_1,x_2,\ldots,x_{k-2},i,jx1 ,x2 ,…,xk−2 ,i,j * Step 222：x1,x2,…,xk−2,j,kx_1,x_2,\ldots,x_{k-2},j,kx1 ,x2 ,…,xk−2 ,j,k * Step 333：x1,x2,…,xk−2,k,px_1,x_2,\ldots,x_{k-2},k,px1 ,x2 ,…,xk−2 ,k,p * Step 444：x1,x2,…,xk−2,p,ix_1,x_2,\ldots,x_{k-2},p,ix1 ,x2 ,…,xk−2 ,p,i 执行上面的 444 次操作后，x1,x2,…,xk−2x_1,x_2,\ldots,x_{k-2}x1 ,x2 ,…,xk−2 每个点都和 xxx 内其余点边的关系发生了 444 次反转（即没有发生变化），和 i,j,k,pi,j,k,pi,j,k,p 四个点的边的关系发生了 222 次反转（即没有发生变化）。而 i↔j,j↔k,k↔p,p↔ii\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow p,p\leftrightarrow ii↔j,j↔k,k↔p,p↔i 四条边则恰好被反转了一次（即发生了变化）。 0X12 长度为 NNN 个点的环（2∣N2\MID N2∣N） 这里为了简化操作，定义一个长度为 nnn 的点的环形如： * 对于任意整数 iii 满足 1≤i<n1\le i<n1≤i<n，i,i+1i,i+1i,i+1 两点之间都有一条边。 * 1,n1,n1,n 两点间有一条边。 考虑分类讨论，考虑下面的策略： * 选择 1,2,3,41,2,3,41,2,3,4 四个点执行 K4K_4K4 的操作，这样 2,32,32,3 两个点可以单独脱离环，然后 1,41,41,4 两个点会多出一条连边，得到形如 1−4−5−6−…−n−11-4-5-6-\ldots-n-11−4−5−6−…−n−1 的环。这个操作可以每次从环上单独分离出两个点。 * 重复执行上述操作直到环上点数量 ≤4\le 4≤4 为止。 此时因为 2∣n2\mid n2∣n 所以最终会获得一个长度为 444 的环，直接执行一次上面给出的操作就可以把所有点全部分离，最终剩余 000 条边。 0X13 U↔V↔WU\LEFTRIGHTARROW V\LEFTRIGHTARROW WU↔V↔W 的链（2∣K2\MID K2∣K） 目标是在图中反转 u↔v,v↔wu\leftrightarrow v,v\leftrightarrow wu↔v,v↔w 两条边。考虑先执行下面的操作： * Step 111：x1,x2,…,xk−2,u,vx_1,x_2,\ldots,x_{k-2},u,vx1 ,x2 ,…,xk−2 ,u,v * Step 222：x1,x2,…,xk−2,v,wx_1,x_2,\ldots,x_{k-2},v,wx1 ,x2 ,…,xk−2 ,v,w 此时 u↔v,v↔wu\leftrightarrow v,v\leftrightarrow wu↔v,v↔w 两条边都被反转了，但是此时还额外反转了 u↔xi,v↔xiu\leftrightarrow x_i,v\leftrightarrow x_iu↔xi ,v↔xi （1≤i≤k−21\le i\le k-21≤i≤k−2）这两类边。问题转为再反转一次 u↔xi,v↔xiu\leftrightarrow x_i,v\leftrightarrow x_iu↔xi ,v↔xi 的边。 此时通过 2∣k2\mid k2∣k 可以推导出 2∣k−22\mid k-22∣k−2。因此考虑把 k−2k-2k−2 个点分成 k2−1\frac k2-12k −1 组，第 iii 组点是 (x2i−1,x2i)(x_{2i-1},x_{2i})(x2i−1 ,x2i )。然后考虑使用一开始的“长度为 444 的环”操作，第 iii 次操作反转 (u,x2i−1,v,x2i)(u,x_{2i}-1,v,x_{2i})(u,x2i −1,v,x2i ) 四个点组成的四元环，这样每条多余的边都恰好被反转了一次。最终被反转的边就是 u↔vu\leftrightarrow vu↔v 和 v↔wv\leftrightarrow wv↔w。 0X14 (U,V),(U,W),(V,W),(I,J),(I,K),(J,K)(U,V),(U,W),(V,W),(I,J),(I,K),(J,K)(U,V),(U,W),(V,W),(I,J),(I,K),(J,K) 六条边（两个 K3K_3K3 ） 考虑执行下面的操作： * Step 111：x1,x2,…,xk−2,u,vx_1,x_2,\ldots,x_{k-2},u,vx1 ,x2 ,…,xk−2 ,u,v * Step 222：x1,x2,…,xk−2,u,wx_1,x_2,\ldots,x_{k-2},u,wx1 ,x2 ,…,xk−2 ,u,w * Step 333：x1,x2,…,xk−2,v,wx_1,x_2,\ldots,x_{k-2},v,wx1 ,x2 ,…,xk−2 ,v,w 此时 u↔v,v↔w,u↔wu\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow wu↔v,v↔w,u↔w 三条边均被反转。但是同时 xi↔xjx_i\leftrightarrow x_jxi ↔xj （1≤i<j≤n1\le i<j\le n1≤i<j≤n）这条边也被反转了。但是注意到现在想要构造的操作其实可以看作是两个 K3K_3K3 拼凑起来，现在 u↔v,v↔w,u↔wu\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow wu↔v,v↔w,u↔w 这三条边已经得到了一个 K3K_3K3 ，而反转具有自反性，因此可以考虑再将上面的操作执行一次得到第二个 K3K_3K3 并消去所有额外的边： * Step 444：x1,x2,…,xk−2,i,jx_1,x_2,\ldots,x_{k-2},i,jx1 ,x2 ,…,xk−2 ,i,j * Step 555：x1,x2,…,xk−2,i,kx_1,x_2,\ldots,x_{k-2},i,kx1 ,x2 ,…,xk−2 ,i,k * Step 666：x1,x2,…,xk−2,j,kx_1,x_2,\ldots,x_{k-2},j,kx1 ,x2 ,…,xk−2 ,j,k 此时所有 xi↔xjx_i\leftrightarrow x_jxi ↔xj （1≤i<j≤n1\le i<j\le n1≤i<j≤n）都又一次被反转了，因此两个反转操作被抵消掉。而此时 i↔j,i↔k,j↔ki\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow ki↔j,i↔k,j↔k 三条边则同样被反转一次。因此最后 u↔v,v↔w,u↔w,i↔j,i↔k,j↔ku\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow ku↔v,v↔w,u↔w,i↔j,i↔k,j↔k 这六条边恰好分别被反转一次，其余边均未被反转，也就是反转了两个 K3K_3K3 形态的子图。 注意到此时有 k−2k-2k−2 个辅助点，加上 666 个需要反转操作的点一共需要使用 k−2+4=k+4k-2+4=k+4k−2+4=k+4 个点，因此只有 k+4≤nk+4\le nk+4≤n 即 k≤n−4k\le n-4k≤n−4 时才可以使用该操作。 0X15 (U,V),(U,W),(V,W),(W,I),(W,J),(I,J)(U,V),(U,W),(V,W),(W,I),(W,J),(I,J)(U,V),(U,W),(V,W),(W,I),(W,J),(I,J) 六条边 和 0x14 部分本质相同，此时只需要 k≤n−3k\le n-3k≤n−3 就可以执行该操作。 其实这个地方是可以和 kkk 的取值无关的！其实利用 0x11 中给出的反转四元环操作就可以生成出该操作： * Step 111：用 0x11 给出的操作反转 u,v,i,ju,v,i,ju,v,i,j 四个点组成的四元环。 * Step 222：用 0x11 给出的操作反转 u,w,v,iu,w,v,iu,w,v,i 四个点组成的四元环。 容易发现此时恰好反转了 u↔v,v↔w,u↔w,w↔i,w↔j,i↔ju\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,w\leftrightarrow i,w\leftrightarrow j,i\leftrightarrow ju↔v,v↔w,u↔w,w↔i,w↔j,i↔j 六条边。 该结构的最大优势是处理 2∤k2\nmid k2∤k 的情况。 解决原问题 0X21 把原图化为特殊形态 前面已经特判掉了 k≤3k\le 3k≤3 的情况，因此本部分只需要解决 k>3k>3k>3 即可。 此时考虑先从图中找出三个关键点 i,j,ki,j,ki,j,k，并对图进行一些操作，使得图上所有二元组 (x,y)(x,y)(x,y) 若满足不存在 x↔yx\leftrightarrow yx↔y 的边，则这样的二元组 (x,y)(x,y)(x,y) 必然还满足下面两条之一： * x=i,y=jx=i,y=jx=i,y=j 或 x=j,y=ix=j,y=ix=j,y=i * x=kx=kx=k 或 y=ky=ky=k 下面考虑如何执行操作可以得到这种图。考虑执行下面的操作： * 对于每两个点 x,yx,yx,y 满足 x≠i,x≠j,y≠i,y≠j,x≠yx\neq i,x\neq j,y\neq i,y\neq j,x\neq yx=i,x=j,y=i,y=j,x=y，若图上当前没有连接 x,yx,yx,y 两个点的边，则考虑继续分类讨论（111）： * 若图上存在点 zzz 满足 z≠a,z≠b,z≠x,z≠yz\neq a,z\neq b,z\neq x,z\neq yz=a,z=b,z=x,z=y 且 xxx 和 zzz 之间不存在边相连，则反转 z,x,y,iz,x,y,iz,x,y,i 四个点组成的四元环。 * 否则，若图上存在点 zzz 满足 z≠a,z≠b,z≠x,z≠yz\neq a,z\neq b,z\neq x,z\neq yz=a,z=b,z=x,z=y 且 yyy 和 zzz 不存在边相连，则反转 x,y,z,ix,y,z,ix,y,z,i 四个点组成的四元环。 * 否则，直接反转 x,y,i,jx,y,i,jx,y,i,j 四个点组成的四元环。 * 对于每个点 xxx 满足 x≠i,x≠j,x≠kx\neq i,x\neq j,x\neq kx=i,x=j,x=k，考虑分类讨论 xxx 和 i,ji,ji,j 两点的连边关系（222）： * 若 xxx 和 i,ji,ji,j 两点都连了边，则不进行任何处理。 * 否则，若 xxx 和 i,ji,ji,j 两点都没有连边，则对 i,x,j,ki,x,j,ki,x,j,k 四个点执行一次 0x11 给出的操作即可。 * 否则，若 xxx 和 iii 没有连边，则对 i,x,k,ji,x,k,ji,x,k,j 四个点执行一次 0x11 给出的操作即可。 * 否则（即只有 xxx 和 jjj 没有连边），则对 j,x,k,ij,x,k,ij,x,k,i 四个点执行一次 0x11 给出的操作即可。 现在理性的分析一下上面给出的流程都干了什么事。这里为了方便描述，将上述流程分为 1,21,21,2 两个部分分别处理。 对于流程 111 而言：每一次都把端点不为 x,yx,yx,y 的不存在的边连接，并删除了对应的以 x,yx,yx,y 为端点的边。在该流程结束后对于所有不存在连边的 x,yx,yx,y 都有 i=xi=xi=x 或 i=yi=yi=y 或 j=xj=xj=x 或 j=yj=yj=y。 对于流程 222 而言：对于原来可能存在的不存在的边 (x,i),(x,j)(x,i),(x,j)(x,i),(x,j) 进行一次包含其的四元环操作后，(x,i),(x,j)(x,i),(x,j)(x,i),(x,j) 之间的边会被连上，而被删除的边一定形如 (x,k),(i,j),(i,k),(j,k)(x,k),(i,j),(i,k),(j,k)(x,k),(i,j),(i,k),(j,k) 中的一类。 此时显然可以达成该部分想要达成的目标。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 考虑回到问题的开始。在这片题解的最初通过对 k mod 4k\bmod 4kmod4 的值分类讨论得到了答案的上界，下面考虑继续对 k mod 4k\bmod 4kmod4 的值分类讨论并给出最终的构造方案（顺便也证明可以取到答案上界）。 0X22 K≡2(MOD4)K\EQUIV 2\PMOD 4K≡2(MOD4) 从最简单的情况入手讨论。 此时既没有边数量奇偶性的约束条件，也没有点度数的奇偶性约束条件。 这里先考虑没有被连的边的数量是偶数的情况。 考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 此时所有二元组 (x,y)(x,y)(x,y) 满足 x,yx,yx,y 之间没有边相连当且仅当 x=kx=kx=k 或 y=ky=ky=k。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。 而如果没有被连的边的数量是奇数，则在 0x21 修改图的形态之前，直接随便选 kkk 个点执行一次操作即可（容易发现 0x21 部分不会修改边的数量的奇偶性）。 0X23 K≡0(MOD4)K\EQUIV 0\PMOD 4K≡0(MOD4) 其实和 0x22 没有本质区别？ 把 0x22 里第一步调整没有被连的边的奇偶性那一步删掉，后面的部分完全是一样的。 0X24 K≡3(MOD4)K\EQUIV 3\PMOD 4K≡3(MOD4) 这里先考虑没有被连的边的数量是偶数的情况。 考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 此时所有二元组 (x,y)(x,y)(x,y) 满足 x,yx,yx,y 之间没有边相连当且仅当 x=kx=kx=k 或 y=ky=ky=k。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。 但是此时仍然没有达到答案的下界，需要进一步进行操作： * 若存在四个点 x,y,z,wx,y,z,wx,y,z,w 满足 x↔k,y↔k,z↔k,w↔kx\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow k,w\leftrightarrow kx↔k,y↔k,z↔k,w↔k 四条边都不在图中存在，那么用前面 0x15 的操作反转 k↔x,k↔y,k↔z,k↔w,x↔y,z↔wk\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,k\leftrightarrow w,x\leftrightarrow y,z\leftrightarrow wk↔x,k↔y,k↔z,k↔w,x↔y,z↔w 这六条边。 * 此时，若 x,yx,yx,y 两点还满足 x↔k,y↔kx\leftrightarrow k,y\leftrightarrow kx↔k,y↔k 两条边都不存在，且 i,j,ki,j,ki,j,k 三个点得到的三条边只有不超过一条边存在，那么用前面 0x15 的操作反转 k↔i,k↔j,k↔x,k↔y,i↔j,x↔yk\leftrightarrow i,k\leftrightarrow j,k\leftrightarrow x,k\leftrightarrow y,i\leftrightarrow j,x\leftrightarrow yk↔i,k↔j,k↔x,k↔y,i↔j,x↔y 这六条边即可。 这一步操作可以尽可能的减少图上任意一点 xxx 和选出的关键点 kkk 之间不存在边的 xxx 的数目。但是此时出现了两端点都不是 kkk 的边不存在的情况，因此还需要再打一次补丁。考虑观察此时图的性质，容易发现此时图上边的数量一定为偶数条，且用上述方法两端点都不为 kkk 的不存在的边的数量一定是偶数。因此考虑再执行下面的操作： * 若对于图上的结点 xxx，i↔j,i↔k,j↔k,x↔ki\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow ki↔j,i↔k,j↔k,x↔k 四条边都没有连，那么考虑找出 x,i,j,kx,i,j,kx,i,j,k 之外的任意一点 yyy。 * 此时考虑用操作 0x15 来反转 i↔j,i↔k,j↔k,k↔x,k↔y,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow yi↔j,i↔k,j↔k,k↔x,k↔y,x↔y 六条边（即补齐 i,j,ki,j,ki,j,k 三角形上的边以及一条 kkk 连向外部的边）。 * 若此时 i↔j,i↔k,j↔k,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow yi↔j,i↔k,j↔k,x↔y 四条边都没有连，则用操作 0x15 来反转 i↔j,i↔k,j↔k,k↔x,k↔y,x↔yi\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow yi↔j,i↔k,j↔k,k↔x,k↔y,x↔y 六条边（即补齐 i,j,ki,j,ki,j,k 三角形上的边以及一条在 i,j,ki,j,ki,j,k 以外的边）。 * 此时再找出点 www 满足 w≠i,w≠j,w≠k,w≠x,w≠yw\neq i,w\neq j,w\neq k,w\neq x,w\neq yw=i,w=j,w=k,w=x,w=y，则若此时 i↔k,x↔k,y↔k,z↔ki\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow ki↔k,x↔k,y↔k,z↔k 四条边都没有连，则用操作 0x15 来反转 i↔k,i↔x,k↔x,k↔y,k↔z,y↔zi\leftrightarrow k,i\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow zi↔k,i↔x,k↔x,k↔y,k↔z,y↔z 六条边（即补齐 i,ki,ki,k 两点之间的边以及 kkk 外面挂着的三条缺失的边）。 * 若此时 j↔k,x↔k,y↔k,z↔kj\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow kj↔k,x↔k,y↔k,z↔k 四条边都没有连，则用操作 0x15 来反转 j↔k,j↔x,k↔x,k↔y,k↔z,y↔zj\leftrightarrow k,j\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow zj↔k,j↔x,k↔x,k↔y,k↔z,y↔z 六条边（即补齐 j,kj,kj,k 两点之间的边以及 kkk 外面挂着的三条缺失的边）。 此时图上只有 i↔ji\leftrightarrow ji↔j 的边，以及 kkk 点连向除了 i,j,ki,j,ki,j,k 以外的若干点 xxx 的边不存在。因此考虑再打第三层补丁： * 如果 i↔j,j↔k,k↔vi\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow vi↔j,j↔k,k↔v 都缺边，那么直接反转 i,j,k,vi,j,k,vi,j,k,v 组成的四元环即可。 * 如果 i↔j,i↔k,k↔vi\leftrightarrow j,i\leftrightarrow k,k\leftrightarrow vi↔j,i↔k,k↔v 都缺边，那么直接反转 j,i,k,vj,i,k,vj,i,k,v 组成的四元环即可。 可以证明此时图的边数一定达到了上界。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 而对于奇数的情况，同样的，考虑在 0x21 部分中找出三个关键点 i,j,ki,j,ki,j,k 后，先将 i,ji,ji,j 两个点连起来（直接用 0x13 操作反转 i↔j,j↔ki\leftrightarrow j,j\leftrightarrow ki↔j,j↔k 两条边即可）。 0X25 K≡1(MOD4)K\EQUIV 1\PMOD 4K≡1(MOD4) 其实和 k≡3(mod4)k\equiv 3\pmod 4k≡3(mod4) 的情况也差不多，同样也是少了一个选前 kkk 个点反转的操作。这里就不展开讨论了。 2026.03.14 你为寻找或是告别耗尽一生 / 也足够让人心动（周深 亲爱的旅人啊） 006. CF1734F ZEROS AND ONES（*2500\COLOR{PINK}{2500}2500） 首先有一个经典结论是 Thue-Morse 序列的第 iii 项的值就是 parity⁡(i)\operatorname{parity}(i)parity(i)。因此题目中给出的询问操作其实就是问 ∑i=0m−1parity⁡(i⊕(i+n))\sum\limits_{i=0}^{m-1}\operatorname{parity}(i\oplus(i+n))i=0∑m−1 parity(i⊕(i+n))。 记 S(m,n)=∑i=0m−1parity(i⊕(i+n))S(m,n)=\sum\limits_{i=0}^{m-1}\text{parity}(i\oplus(i+n))S(m,n)=i=0∑m−1 parity(i⊕(i+n))。考虑到有 parity(2x)=1−parity(2x+1)=parity(x)\text{parity}(2x)=1-\text{parity}(2x+1)=\text{parity}(x)parity(2x)=1−parity(2x+1)=parity(x)。因此考虑按照 n,mn,mn,m 的奇偶性分别讨论计算答案： * 2∣n2\mid n2∣n：记 n=2k,m=2q+rn=2k,m=2q+rn=2k,m=2q+r（r∈{0,1}r\in\lbrace0,1\rbracer∈{0,1}），则有 S(m,2k)=2S(q,k)+rparity(q⊕(q+k))S(m,2k)=2S(q,k)+r\text{parity}(q\oplus(q+k))S(m,2k)=2S(q,k)+rparity(q⊕(q+k))。 * 2∤n2\nmid n2∤n：记 n=2k+1,m=2q+rn=2k+1,m=2q+rn=2k+1,m=2q+r（r∈{0,1}r\in\lbrace 0,1\rbracer∈{0,1}），则有 S(m,2k+1)=2q−S(q,k)−S(q,k+1)+r(1−parity(q⊕(q+k)))S(m,2k+1)=2q-S(q,k)-S(q,k+1)+r(1-\text{parity}(q\oplus(q+k)))S(m,2k+1)=2q−S(q,k)−S(q,k+1)+r(1−parity(q⊕(q+k)))。 边界条件是 S(0,n)=S(m,0)=0S(0,n)=S(m,0)=0S(0,n)=S(m,0)=0，记忆化搜索就可以做到 O(log⁡2n)O(\log^2n)O(log2n) 处理单组数据。 007. CF1626F A RANDOM CODE PROBLEM（*2800\COLOR{RED}{2800}2800） 注意到位置和位置之间是相互独立的，因此考虑对每个位置分别计算其期望值。设 fi,jf_{i,j}fi,j 表示当前处理的数值为 iii，进行了 jjj 次操作的不同方案数。转移形如： * fi,j+1←(n−1)fi,jf_{i,j+1}\leftarrow (n-1)f_{i,j}fi,j+1 ←(n−1)fi,j * fi−i mod (j+1),j+1←fi,jf_{i-i\bmod(j+1),j+1}\leftarrow f_{i,j}fi−imod(j+1),j+1 ←fi,j 直接转移时间复杂度为 O(kV)O(kV)O(kV)，考虑进一步优化。注意到用题目中给出的操作，若对 xxx 进行操作，则 xlcm(1,2,…,k−1)\frac x{\text{lcm}(1,2,\ldots,k-1)}lcm(1,2,…,k−1)x 的值在整个操作过程中一定不会发生变化。因此考虑初始把所有 aia_iai 都对 lcm(1,2,…,k−1)\text{lcm}(1,2,\ldots,k-1)lcm(1,2,…,k−1) 取模，此时值域 VVV 变为 lcm(1,2,…,k−1)\text{lcm}(1,2,\ldots,k-1)lcm(1,2,…,k−1)，O(kV)O(kV)O(kV) 的时间复杂度（简单卡常后）就可以通过该题。 至于这里为什么是 k−1k-1k−1 而不是 kkk，你会发现最后一次操作（即 i=ki=ki=k 时）aaa 数组的变化未被统计到 ans 内，所以不需要考虑。 008. CF1679F FORMALISM FOR FORMALISM（*2600\COLOR{RED}{2600}2600） 题意可以转化为：有多少个数不能通过题目中给出的操作使得自己的值变得比最开始更小。 然后考虑如果前一位填了 xxx，而且前面部分全都是合法的，那么后一位可以填哪些数字。假设这里填写了数字 yyy，则： * 如果 x,yx,yx,y 之间不能互相交换，那么很显然可以填写 yyy。 * 如果 x,yx,yx,y 之间可以互相交换，且 x>yx>yx>y，那么很显然不能填写 yyy。 * 否则考虑交换 x,yx,yx,y 两个位置后，yyy 可能可以和 xxx 之前的数继续发生交换，因此 yyy 能填写当且仅当在 xxx 的位置填写 yyy 合法。 然后就可以 dp 了。设 fi,jf_{i,j}fi,j 表示当前考虑了 iii 集合，上一次可以填写的数的集合是 jjj，有多少个合法的前缀数。转移直接枚举下一个位置填的是什么数字即可。最终时间复杂度为 O(nω2ω)O(n\omega2^\omega)O(nω2ω)，其中 ω=10\omega=10ω=10。 009. CF1623E MIDDLE DUPLICATION（*2500\COLOR{PINK}25002500） 因为字典序比较遵循贪心原则，所以考虑直接按中序遍历来贪心处理，即一个点被复制后优先处理其左子树。 此时容易想到下面的贪心流程： * 对于当前访问到的结点 uuu： * 递归访问其左子树 lul_ulu 。 * 若 lul_ulu 需要被复制，则 uuu 也同样需要被复制。 * 否则，若 uuu 复制后可以让答案更优，则 uuu 同样需要被复制。 * 若 uuu 被复制，则递归访访问其右子树 rur_uru 。 容易证明该算法的正确性。直接模拟上述流程可做到时间复杂度 O(n)O(n)O(n) 解决问题。 2026.03.15 因为我刚好遇见你 / 留下足迹才美丽 / 风吹花落泪如雨 / 因为不想分离 / 因为刚好遇见你 / 留下十年的期许 / 如果再相遇 / 我想我会记得你（李玉刚 刚好遇见你） 010. CF1598F RBS（*2400\COLOR{PINK}{2400}2400） 好困难/ll 套路的把左括号看作是 111，右括号看作是 −1-1−1。则显然 iii 位置的前缀是 RBS 的充要条件是： * 不存在 1≤j≤i1\le j\le i1≤j≤i 满足 jjj 位置的前缀和 <0<0<0。 * iii 位置的前缀和为 000。 考虑直接状压 dp，设 fi,jf_{i,j}fi,j 表示当前处理了 iii 集合内的字符串，当前的前缀最小值是 jjj，最多有多少个 RBS 前缀。转移随便处理点东西就可以做到 O(n2n)O(n2^n)O(n2n) 转移。 011. [AGC050A] ATCODER JUMPER（*2300\COLOR{YELLOW}{2300}2300） 十分 adhoc 的题目。考虑直接让 iii 点连 2i2i2i 和 2i+12i+12i+1（以 nnn 为单位循环标号），此时 iii 点走 101010 条边之后可以走到 [1024i,1024i+1024)[1024i,1024i+1024)[1024i,1024i+1024) 范围内的点，显然覆盖了 1∼n1\sim n1∼n 内的所有点。 直接模拟上述流程可以做到时间复杂度 O(n)O(n)O(n) 处理问题。 012. CF1614D1 DIVAN AND KOSTOMUKSHA (HARD VERSION) / CF1614D2 DIVAN AND KOSTOMUKSHA (HARD VERSION)（*2100\COLOR{ORANGE}{2100}2100 / *2400\COLOR{PINK}{2400}2400） 先考虑 D1 怎么做。容易想到记 bucibuc_ibuci 表示 aaa 序列中有多少个数是 iii 的倍数（可以写一个埃筛 O(nlog⁡n)O(n\log n)O(nlogn) 求出），然后记 fif_ifi 表示当前序列的 gcd⁡\gcdgcd 为 iii，所有前缀的 gcd⁡\gcdgcd 的和最大是多少。看上去没有记录当前选择了多少个数不好处理，但是注意到处理 fif_ifi 的时候把所有 iii 的倍数加到序列里的贡献都是 iii 且不会对序列的 gcd⁡\gcdgcd 产生影响，而再往后加的话序列的 gcd⁡\gcdgcd 值一定会变小，加入 iii 对答案的贡献也同样会减小，因此计算 fif_ifi 的时候一定需要把所有 iii 的倍数全都加入到序列里。 因此可以想到初始条件为 fi=i×bucif_i=i\times buc_ifi =i×buci ，转移方程为 fi←fij+i(buci−bucij)f_i\leftarrow f_{ij}+i(buc_i-buc_{ij})fi ←fij +i(buci −bucij )（buci−bucijbuc_i-buc_{ij}buci −bucij 即为当前为 iii 的倍数且没有被加入到序列中的元素的数量）。转移的时候枚举 iii 的倍数可以做到 O(Vlog⁡V)O(V\log V)O(VlogV)，能够通过 D1。 此时注意到转移时一个决策 i←iji\leftarrow iji←ij 可能成为不可被替代的最优解当且仅当 jjj 是质数，因此考虑先筛出 1∼V1\sim V1∼V 内所有的质数然后转移的时候只转移质数 jjj 的 dp 值。而处理 bucbucbuc 数组时可以套用 Dirichlet 前缀和的技巧做到 O(Vlog⁡log⁡V)O(V\log\log V)O(VloglogV) 计算。因此总时间复杂度为 O(Vlog⁡log⁡V)O(V\log\log V)O(VloglogV)，简单卡常即可通过 D2。 2026.03.16 泛红的双眼 / 对你的爱怎么遮掩 再靠近多些 / 望着你的背影默念 敏感又热烈 / 只想霸占你的世界 我可以付出一切代价 （王澳楠 请和这样的我恋爱吧） 013. CF1582G KUZYA AND HOMEWORK（*2600\COLOR{RED}{2600}2600） 考虑把每个数都分解质因数来统计。枚举右端点 rrr，然后维护一个栈 stkstkstk 表示当前有哪些左端点是合法的，SiS_iSi 表示若只考虑质因数为 iii 的部分有哪些左端点是合法的。则此时若 iii 位置对应的字符是 *，直接把 iii 加入 SjS_jSj 和 stkstkstk 中即可，否则在 SjS_jSj 和 stkstkstk 中把 iii 对应的质因数抵消掉。统计结束后栈 stkstkstk 内的元素数量即为右端点为 rrr 的合法区间数量。 线性筛出 spfi\text{spf}_ispfi 表示 iii 的最小质因数可以做到 O(nlog⁡V)O(n\log V)O(nlogV) 时间复杂度解决问题。 014. P3644 [APIO2015] 巴邻旁之桥（*2400\COLOR{PINK}{2400}2400） 注意到 k∈{1,2}k\in\lbrace 1,2\rbracek∈{1,2}（现在你已经做完了这个题最难的地方），因此猜测是直接分两类讨论。 K=1K=1K=1 可以把问题转化为：找到最小的 xxx 使得 ∑i=1n∣ai−x∣+∑i=1n∣bi−x∣\sum\limits_{i=1}^n|a_i-x|+\sum\limits_{i=1}^n|b_i-x|i=1∑n ∣ai −x∣+i=1∑n ∣bi −x∣ 的值最小。这是经典的贪心模型，直接把 ai,bia_i,b_iai ,bi 合并到一个数组 ccc 中然后升序排序，取 x=cnx=c_nx=cn 即为最优解。证明直接调整法即可。 K=2K=2K=2 类比 k=1k=1k=1 的做法，必然是建两座桥然后左半部分的走坐标的桥，右半部分的走右边的桥，因此容易想到枚举中间的分界点 ppp 然后对两侧分别做 k=1k=1k=1 的处理，可以简单维护有序数组做到 O(n2)O(n^2)O(n2) 求解问题。 考虑优化时间复杂度。考虑记 F(p)F(p)F(p) 为分界点为 ppp 时的答案，但是 F(p)F(p)F(p) 看上去没有单调单峰等性质。一个想法是直接对 F(p)F(p)F(p) 跑模拟退火（我不知道这个能不能过）。注意到其实不需要真的维护两个有序数组，只需要得知两个数组的中位数值即可，因此考虑从左到右扫描所有本质不同的位置 ppp 然后对两个集合做单点插入 / 单点删除操作，并分别维护两个集合的中位数以及 ∑i=1n∣ai−x∣\sum\limits_{i=1}^n|a_i-x|i=1∑n ∣ai −x∣ 的值（已知元素数量和数组中位数值后这个是容易维护的）。用对顶堆来维护即可做到 O(nlog⁡n)O(n\log n)O(nlogn) 通过该题。 015. CF1097G VLADISLAV AND A GREAT LEGEND（*30003\COLOR{RED}{000}3000） f(S)kf(S)^kf(S)k 看上去不太好维护，考虑经典套路斯特林反演： nk=∑i=0kS2(k,i)(ni)i!n^k=\sum\limits_{i=0}^k S_2(k,i)\binom nii! nk=i=0∑k S2 (k,i)(in )i! 于是题目给出的式子可以化为： ∑i=0ki!S2(k,i)∑S⊆{1,2,3,…,n}(f(S)i)\sum\limits_{i=0}^ki!S_2(k,i)\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}i i=0∑k i!S2 (k,i)S⊆{1,2,3,…,n}∑ (if(S) ) 问题在于对每个 iii 快速计算 ∑S⊆{1,2,3,…,n}(f(S)i)\displaystyle\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}iS⊆{1,2,3,…,n}∑ (if(S) ) 的值。 考虑这个东西的组合意义，容易发现对每个 iii，其答案可以看作是在 SSS 集合内点组成的虚树的点集上选 iii 条边的方案数。 设 fi,jf_{i,j}fi,j 表示当前处理了 iii 为根的子树内有 jjj 条虚树的边的方案数，转移类似于树上背包合并，时间复杂度为 O(nk)O(nk)O(nk)。统计答案的时候套路的在深度最低的结点上统计即可。实现起来细节比较多。 016. CF1592F2 ALICE AND RECOLORING 2（*2800\COLOR{RED}{2800}2800） 一眼看上去这题十分神秘不可做，因此考虑逐步挖掘其性质。 性质：有用的操作其实只有 1,41,41,4 两种。 证明： 对于 222 操作：则可以先用一次 111 操作操作掉整个左侧，然后再把不包含于她的左上角操作。这样花费的代价为 222，优于 111 次 222 操作的 333 代价。444 操作同理，用 111 操作操作掉整个上侧然后容斥把不包含于她的左上角操作，花费的代价为 222，优于 111 次 333 操作花费的 444 代价。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 然后发现一次操作操作的是一个矩阵，看上去很麻烦，要将其变为对单点做操作。因此考虑对矩阵做二阶差分。这里重定义颜色之间的按位异或： * 相同颜色异或，得到的颜色为 W\texttt{W}W。 * 不同颜色异或，得到的颜色为 B\texttt{B}B。 考虑将其转化为实际的数字意义，即 W\texttt{W}W 代表 000，B\texttt{B}B 代表 111。此时令这个差分的二维数组为 aaa，则考虑一次操作会对新的二维数组 aaa 做怎样的修改。 * 对于一次 111 操作 (x,y)(x,y)(x,y)，则只有 (x,y)(x,y)(x,y) 一个点会取反。 * 对于一次 444 操作 (x,y)(x,y)(x,y)，那么 (x−1,y−1)(x-1,y-1)(x−1,y−1)，(x−1,m)(x-1,m)(x−1,m)，(n,y−1)(n,y-1)(n,y−1)，(n,m)(n,m)(n,m) 四个点都会被取反。 看上去一次 444 操作修改的位置更多，性质或许也会更强一些？于是对其做分析。考虑同时对在同一行上的两个坐标 (x,y1)(x,y_1)(x,y1 ) 和 (x,y2)(x,y_2)(x,y2 ) 做一次 444 操作，则此时 (x,y1),(n,y1),(x,y2),(n,y2)(x,y_1),(n,y_1),(x,y_2),(n,y_2)(x,y1 ),(n,y1 ),(x,y2 ),(n,y2 ) 四个格子被取反了一次，而 (x,m),(n,m)(x,m),(n,m)(x,m),(n,m) 被取反了两次（等于没变）。一共取反了 444 个格子，和做 444 次 111 操作效果等价，花费均为 444。因此其实这种情况可以规避开较为复杂的 444 操作去使用较为简单的 111 操作替代。同一列上的两个坐标 (x1,y)(x_1,y)(x1 ,y) 和 (x2,y)(x_2,y)(x2 ,y) 的情况也同理。换句话说：444 操作操作的任意两个位置横纵坐标必须都不相同。 可以通过类似的手段分析，得到另一个性质更为强大的结论：使用 444 操作对 (x,y)(x,y)(x,y) 做操作比用 111 操作严格好，当且仅当 (x,y),(x,m),(n,y)(x,y),(x,m),(n,y)(x,y),(x,m),(n,y) 三个格子的值都为 111。证明类似于上面一个步骤，如果这三个格子中存在一个格子不为 111 则需要容斥一次翻转操作，即执行两次翻转，花费的代价为 444。而若用 111 操作则只需要不超过 333 的代价就可以达成目标。 分析了这么一大通，那么这个题有应该如何解决呢？考虑到（忘了哪个题）的套路，建一张二分图，把横坐标建在图的左侧，纵坐标建在图的右侧。那么做一次可能合法 444 操作 (x,y)(x,y)(x,y) 就是把左侧点 xxx 向右侧点 yyy 连一条边。用匈牙利算法对该图跑最大匹配，或者建立源汇用 Dinic 算法求解其网络最大流均可。时间复杂度为 O(n3)O(n^3)O(n3) 或 O(n2.5)O(n^{2.5})O(n2.5)（n,mn,mn,m 同阶），而且远远跑不满，所以可以通过。 017. [ARC127E] PRIORITY QUEUE（*2600\COLOR{RED}{2600}2600） 注意到操作的是一个集合，也就是加入元素的顺序不会影响答案。因此直接钦定的加入元素时不会被删除的数和会被删除的树都是从小到大加入的，因此删除操作一定是删除最近一个加入的未被删除的的元素。 因为需要保证每次删除的数都比前面的数要大，而因为前面钦定了删除一个数，这个数必须是上一次操作刚加入的。而又因为两组序列都必须是单调递增的，因此若当前是第 iii 个要被删除的数，前面已经有 jjj 个数一定不会被删除，则第 iii 个被删除的数的值必须严格大于 jjj。 因此考虑 dp。设 fi,jf_{i,j}fi,j 表示第 iii 次删除操作，删除的序列最大值为 jjj，不同集合的数量。则显然有初始条件 f0,0=1f_{0,0}=1f0,0 =1。转移枚举上一个被删除的数 jjj 可以做到 O(n3)O(n^3)O(n3)。注意到限制条件保证了 dp 的合法状态是连续的一段，因此使用前缀和优化可以做到 O(n2)O(n^2)O(n2) 解决问题。 2026.03.17 日记本线条随回忆见笑 / 付出我的一切却装成笑话编造 / 咽下的时光怨当初年少 / 爱没有尾声恨没有前兆 （因你而在的梦 椰蓉面包） 018. CF2204G GRID PATH（*2700\COLOR{RED}{2700}2700） 容易想到设 fk,i,jf_{k,i,j}fk,i,j 表示当前处理了前 kkk 行的染**况，第 kkk 行恰好染色了 [i,j][i,j][i,j] 区间内的所有格子，方案数是多少。然后注意到这个东西的转移可以用矩阵乘法优化，做到 O(m6log⁡n)O(m^6\log n)O(m6logn) 时间复杂度求解。 考虑继续优化。注意到关键性质：对于具有可减性的信息，[l,r][l,r][l,r] 区间的信息可以被表示为 [0,r]+[l,m−1]−[0,m−1][0,r]+[l,m-1]-[0,m-1][0,r]+[l,m−1]−[0,m−1]。此时所有区间都形如 [0,m−1][0,m-1][0,m−1] 整体的前后缀，可以用 2m2m2m 个区间来表示所有区间。转移直接枚举前后缀区间然后再枚举要转移的区间 [l,r][l,r][l,r] 将 [l,r][l,r][l,r] 拆分成三个前后缀区间后分别按系数转移即可，同样可以用矩阵乘法优化。此时算法的时间复杂度被优化到 O(m3log⁡n)O(m^3\log n)O(m3logn)，简单卡常后可以通过该题。 019. CF1622F QUADRATIC SET（*2900\COLOR{RED}{2900}2900） 考虑先随便构造出一个比较大的二次集。 众所周知阶乘可以被拆成若干个数的乘法的形式，因此考虑对每个数拆贡献，得到 ∏i=1ni!=∏i=1nin−i+1\prod\limits_{i=1}^ni!=\prod\limits_{i=1}^ni^{n-i+1}i=1∏n i!=i=1∏n in−i+1。此时考虑对每个 iii 把平方项都拆掉。注意到 nnn 的奇偶性会影响剩下的 iii 的取值，因此考虑对 nnn 的奇偶性分类讨论： 若 2∣n2\mid n2∣n：此时 ∏i=1nin−i+1=2n2n2![∏i=1n2(2i−1)!]2\prod\limits_{i=1}^ni^{n-i+1}=2^{\frac n2}\frac n2![\prod\limits_{i=1}^{\frac n2}(2i-1)!]^2i=1∏n in−i+1=22n 2n ![i=1∏2n (2i−1)!]2。此时若 4∣n4\mid n4∣n 则在集合中删去 n2\frac n22n 元素即可，否则（即 n≡2(mod4)n\equiv 2\pmod 4n≡2(mod4)）则在集合中删去 2,n22,\frac n22,2n 两个元素即可。 2∤n2\nmid n2∤n 时阶乘的前缀积没有这么好的性质，但是注意到此时并不需要要求删除的元素数量尽量少只需要随便找一个比较紧的下界，因此考虑直接把 nnn 从集合中删去，此时转化为 2∣n2\mid n2∣n 的情况。 于是可以得到关键结论：最优的删除策略一定不会删除超过 333 个元素。 因此考虑枚举删除的元素的数量。容易发现删除 0,10,10,1 个元素是容易判断的，因此此时只需要处理删除两个元素是否可行。 注意到平方这个操作看上去十分像异或，即两个质因数可以相互抵消。因此容易想到经典 trick XOR Hash，给每个质因子赋一个权值，然后预处理出 hih_ihi 表示 iii 的所有质因子的权值的 XOR 值。此时一个集合 SSS 是合法的当且仅当 ⨁i∈Sh(i)=0\bigoplus\limits_{i\in S}h(i)=0i∈S⨁ h(i)=0，因此直接把所有的 h(i)h(i)h(i) 扔到 map 里然后随便维护就可以 O(nlog⁡n)O(n\log n)O(nlogn) 判断是否存在合法解。 020. CF1620F BIPARTITE ARRAY（*2800\COLOR{RED}{2800}2800） 注意到若存在三元组 (i,j,k)(i,j,k)(i,j,k) 满足 i<j<ki<j<ki<j<k 且 ai>aj>aka_i>a_j>a_kai >aj >ak ，则此时 i,j,ki,j,ki,j,k 三个点在无向图上构成一个三元环，此时无向图一定不是二分图。若不存在任何一组这样的 (i,j,k)(i,j,k)(i,j,k) 则此时图上不存在环，一定是二分图。 因此数组 aaa 是二分的 的充要条件 即为序列的最长下降子序列长度不超过 222。此时直接 dp 可以做到 O(n3)O(n^3)O(n3) 时间复杂度解决问题。 考虑使用 Dilworth 定理，若一个序列的最长下降子序列长度为 ddd，则其最少可以被划分为 ddd 个不下降子序列（若数组元素互不相同则可以被划分为 ddd 个上升子序列）。因此序列的最长下降子序列长度不超过 222 一条件可以被转化为 aaa 可以被划分为两个上升子序列。 此时可以设 fk,i,j,0/1,0/1f_{k,i,j,0/1,0/1}fk,i,j,0/1,0/1 表示当前处理了前 kkk 个元素，其中第一个上升子序列最后一个元素位置是 iii，第二个上升子序列最后一个元素位置是 jjj，aia_iai 没有取反 / 取反，aja_jaj 没有取反 / 取反是否存在这样的序列。看上去时间复杂度仍然为 O(n3)O(n^3)O(n3)。此时考虑用染色的 trick，有 max⁡(i,j)=k\max(i,j)=kmax(i,j)=k，因此此时只处理 i,ji,ji,j 两个维度可以做到 O(n2)O(n^2)O(n2)。然后套路的判定性问题把一维信息压到答案里变成最优化问题可以做到 O(n)O(n)O(n) 解决。 2026.03.18 我吹过你吹过的晚风 那我们算不算 相拥 可如梦初醒般的两手空空 心也空 我吹过你吹过的晚风 是否看过同样 风景 像扰乱时差留在错位时空 终是空 是空 （艾辰 错位时空） 021. CF1613F TREE COLORING（*2600\COLOR{RED}{2600}2600） 考虑直接容斥计算。记有至少 iii 个点不满足条件的答案为 fif_ifi ，则容斥可得最后的答案即为 ∑i=0n(−1)ifi\sum\limits_{i=0}^n(-1)^if_ii=0∑n (−1)ifi 。而因为点和点的权值互不相同，因此一个点最多只有一个儿子可以不合法。此时套路的把每个点写成一个多项式的形式那么就可以得到 fi=[xi](∣soni∣x+1)(n−i)!f_i=[x^i](|\text{son}_i|x+1)(n-i)!fi =[xi](∣soni ∣x+1)(n−i)!（可以看作是，先钦定 iii 个点一定不合法，剩下的 n−in-in−i 个点的值随便填），分治 NTT 把多项式乘起来即可做到 O(nlog⁡2n)O(n\log^2n)O(nlog2n) 求解答案。 022. CF1612G MAX SUM ARRAY（*2500\COLOR{PINK}{2500}2500） 容易发现原式的值即为：∑i=1m∑j=1ci(2j−ci−1)xi,j\sum\limits_{i=1}^m\sum\limits_{j=1}^{c_i}(2j-c_i-1)x_{i,j}i=1∑m j=1∑ci (2j−ci −1)xi,j ，其中 xi,jx_{i,j}xi,j 表示值为 iii 的第 jjj 个数的位置，要求所有 xi,jx_{i,j}xi,j 恰好不重不漏的取完 1∼∑i=1mci1\sim\sum\limits_{i=1}^mc_i1∼i=1∑m ci 内的所有整数。此时容易想到直接贪心，把所有位置按照对应的系数 2j−ci−12j-c_i-12j−ci −1 从大到小排序然后依次对应从大到小 ∑i=1mci∼1\sum\limits_{i=1}^mc_i\sim 1i=1∑m ci ∼1 内的所有数，容易证明这个贪心策略最优。 第二问也是容易的，发现为了保证上式的值最大，肯定不会交换两个系数不同的数的 xi,jx_{i,j}xi,j 的值，因此直接求出每个数都出现了几次然后把出现次数的阶乘乘起来即可。 但是直接模拟上述流程时间复杂度为 O(∑ci)O(\sum c_i)O(∑ci )（排序可以写桶排优化到 O(n+V)O(n+V)O(n+V)），无法通过。注意到值域很小，所以直接差分加前缀和求出每个系数的出现次数，然后在值域上双指针扫描即可将时间复杂度优化到 O(n)O(n)O(n)。 2026.03.19 夏天的风我永远记得 清清楚楚地说你爱我 我看见你酷酷的笑容 也有腼腆的时候 夏天的风正暖暖吹过 穿过头发穿过耳朵 你和我的夏天风轻轻说着 （温岚 夏天的风） 023. CF1379E INVERSE GENEALOGY（*2800\COLOR{RED}{2800}2800） 容易发现 nnn 为偶数的时候一定无解。而 nnn 为奇数时，特判 n=1n=1n=1，最多可以构造 n−32\frac{n-3}22n−3 个不平衡点，构造方案就直接构造一条链然后给每个点再插一个儿子得到一个毛毛虫树即可。即：i,i+1i,i+1i,i+1 点的子女结点为 i−2i-2i−2 结点。 因此考虑在 kkk 取在上界以内的时候先构造一个 2k+32k+32k+3 个点有 kkk 个不平衡点的树，然后把最底下的一个有 333 个结点的子树扩建成一个完全二叉树。此时最多会新增一个不平衡点。这个时候把编号为 1,31,31,3 两个点的部分扔掉（此时减少了一个不平衡点）然后把这两个点放在一个不会改变不平衡点数量的地方即可。 corner case 是 n=9,k=2n=9,k=2n=9,k=2。此时不存在合法解，k<2k<2k<2 的特殊情况需要单独处理。 024. CF1830D MEX TREE（*2800\COLOR{RED}{2800}2800） 因为 010101 序列的 mex\text{mex}mex 值只有 0,1,20,1,20,1,2 三种不同取值，所以考虑然后 dp：设 fi,j,0/1f_{i,j,0/1}fi,j,0/1 表示当前处理了 iii 点为根的子树内的信息，iii 所对应的同色连通块的大小为 jjj，iii 点写的数字是 0/10/10/1，答案最少减少了多少。那么显然有下面的转移： * fu,i,0←min⁡(fv,j,1+fu,i,0,fv,i−j,0+fu,j,0+ij−i2)f_{u,i,0}\leftarrow \min(f_{v,j,1}+f_{u,i,0},f_{v,i-j,0}+f_{u,j,0}+ij-i^2)fu,i,0 ←min(fv,j,1 +fu,i,0 ,fv,i−j,0 +fu,j,0 +ij−i2) * fu,i,1←min⁡(fv,j,0+fu,i,1,fv,i−j,1+fu,j,1+2(ij−i2))f_{u,i,1}\leftarrow \min(f_{v,j,0}+f_{u,i,1},f_{v,i-j,1}+f_{u,j,1}+2(ij-i^2))fu,i,1 ←min(fv,j,0 +fu,i,1 ,fv,i−j,1 +fu,j,1 +2(ij−i2)) 直接转移看上去时间复杂度为 O(n3)O(n^3)O(n3)，但可以考虑这样的一个策略：直接对树做黑白染色，容易证明该贪心策略答案减少的数量即为 n+∑i=1n[coli=1]≤2nn+\sum\limits_{i=1}^n[col_i=1]\le 2nn+i=1∑n [coli =1]≤2n 也就是 O(n)O(n)O(n) 级别的，而 dp 转移过程中枚举的同色连通块大小 jjj 对答案的减小是 O(j2)O(j^2)O(j2) 级别的，因此枚举的连通块大小只需要到 O(n)O(\sqrt n)O(n ) 级别即可。 剩下部分的转移其实可以看作是一个树上背包的形式，枚举连通块大小只枚举到子树大小即可保证时间复杂度为 O(nn)O(n\sqrt n)O(nn )，可以通过该题。 2026.03.20 如果在噩梦中睁眼 直面着残忍的世界 风拨动了谁的心弦 留恋却来不及告别 如果结局仅剩惨烈 无惧在逆风中破茧 就算那羽翼被撕裂 重回到十九层深渊 （张韶涵 破茧） 025. CF1545C AQUAMOON AND PERMUTATIONS（*2800\COLOR{RED}{2800}2800） 很神秘的题，首先可以证明必然存在合法解。考虑到若某一列上一个数字只出现了一次，那么为了保证最后得到的矩阵是一个拉丁方，这个位置对应的一行排列必须被选择。此时其余和当前被选中排列有至少一位相同的排列都必须被删除。 因为前 nnn 行的矩阵恰好构成了一个拉丁方，因此通过上面的方式删除一个位置必然一次至少删除两行的排列。此时每一列上的数字都至少出现了两次，根据鸽巢原理可知每一列的数字都必须恰好出现两次才能满足条件。此时对于剩下的排列（只保留未删除的数字），不论是你选出来的矩阵还是剩下未被选的矩阵都是一个拉丁方。 此时考虑套路的对关系建图，考虑对每一列上出现的两个相同值的行编号连双向边，可以证明得到的图一定是二分图。因为一条边连接的两行不能同时被选择，因此对二分图的每个连通块，选择行的方案数都是 222。因此设二分图有 kkk 个连通块，答案即为 2k2^k2k。 直接按照上述过程模拟时间复杂度为 O(n3)O(n^3)O(n3)，感觉应该可以用 ds 优化到 O(n2log⁡n)O(n^2\log n)O(n2logn) 但是没啥必要（ 注意到本题只需要计数二分图内连通块的数量即可求出答案，因此实际写的时候可以不显式建出二分图，直接每次删掉一个排列然后再删掉所有和当前排列有关联的排列即可。 026. CF1404D GAME OF PAIRS（*2800\COLOR{RED}{2800}2800） 考虑先写个暴力 dfs 程序打表，可以发现下面的关键结论： * 若 nnn 是偶数，则先手必胜。 * 若 nnn 是奇数，则后手必胜。 下面考虑证明结论： 2∣N2\MID N2∣N 打表可以发现先手把 i,i+ni,i+ni,i+n 两个元素分为一组，此时后手无论在第 iii 组里选择 iii 还是 i+ni+ni+n，其在对 nnn 取模意义下都相当于是增加了 iii。而 ∑i=0n−1i=n(n−1)2=n2−n2≢0(modn)\sum\limits_{i=0}^{n-1}i=\frac{n(n-1)}2=\frac{n^2-n}2\not\equiv 0\pmod ni=0∑n−1 i=2n(n−1) =2n2−n ≡0(modn)，因此模 2n2n2n 显然也无法整除，也就是无论后手怎么操作，先手都是必胜。 2∤N2\NMID N2∤N 可能是一个不太一样的角度？考虑到 2n2n2n 个数中  mod  n\bmod\ nmod n 值为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的数都恰好有 222 个，因此一旦后手存在一种方案恰好选取了  mod  n\bmod\ nmod n 值为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的数各一个，则这些数的和  mod  n\bmod\ nmod n 一定为 000。又因为此时所有数的和  mod  2n\bmod\ 2nmod 2n 的值一定为 nnn，因此若这样的方案  mod  2n\bmod\ 2nmod 2n 的值为 nnn，则选剩下所有没被选的数即可使得和  mod  2n\bmod\ 2nmod 2n 的值为 000。 然后考虑证明无论先手怎么给元素分组，后手都可以给出一个这样的策略： 设当前组两个元素的值为 (i,j)(i,j)(i,j)，则： * 若 i≡j(modn)i\equiv j\pmod ni≡j(modn)，则选哪一个元素都不会影响  mod  n\bmod\ nmod n 的值，直接忽略。 * 否则，给每一组的元素  mod  n\bmod\ nmod n 的值之间连一条边，则图一定由若干个不相交的简单环组成。考虑找到连接 i mod ni\bmod nimodn 和 j mod nj\bmod njmodn 两个元素的值，则顺着这个环绕一圈每一次选择相同方向的端点一定能恰好取遍环上所有  mod  n\bmod\ nmod n 的值。 因此可以证明此时后手一定存在一组恰好取完值  mod  n\bmod\ nmod n 后为 0,1,2,…,n−10,1,2,\ldots,n-10,1,2,…,n−1 的方案，此时后手一定可以胜利。 027. CF850D TOURNAMENT CONSTRUCTION（*2800\COLOR{RED}28002800） 感觉知道 Landau 定理之后就很简单（） 前置知识 Landau 定理：一个长度为 nnn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 是竞赛图每点出度从小到大排列的序列，当且仅当下面两个条件同时满足： * ∑i=1nai=n(n−1)2\sum\limits_{i=1}^n a_i=\frac{n(n-1)}2i=1∑n ai =2n(n−1) * ∑i=1jai≥j(j−1)2\sum\limits_{i=1}^j a_i\ge\frac{j(j-1)}2i=1∑j ai ≥2j(j−1) （1≤j≤n1\le j\le n1≤j≤n） 题解 对 nnn 个点的竞赛图，记 deg⁡i\deg_idegi 表示 iii 点的出度大小，则图上边的数量即为 ∑i=1ndeg⁡i=n(n−1)2\sum\limits_{i=1}^n\deg_i=\frac{n(n-1)}2i=1∑n degi =2n(n−1) 。因为题目的数据范围中保证了图上边的总数量不超过 30n30n30n，解不等式可得 n≤61n\le 61n≤61 一定可以满足条件。 因此考虑直接 dp：设 fi,j,kf_{i,j,k}fi,j,k 表示当前处理到了 iii 号点，当前点的数量为 jjj，边的数量为 kkk，是否合法。转移直接枚举 iii 号点增加的边的数量即可，构造方案在 dp 过程中记录转移路径然后利用 Landau 定理随便构造即可。 总时间复杂度为 O(n5)O(n^5)O(n5)，但是跑不满所以可以通过。 028. P15555 [CCPC 2025 哈尔滨站] 比赛（*34003\COLOR{RED}{400}3400） 难度评的比较高主要是因为 KTT 这个 ds 太冷门了（）oi wiki 上甚至都没有介绍（） 很牛的题。这个 kkk 的限制看上去就很不舒服，考虑先处理 k=1k=1k=1 的情况。 此时 O(nq)O(nq)O(nq) 的暴力是容易的。考虑对每次询问直接暴力 dp 处理，dp 限制内部考虑贪心，显然对于位置 iii 而言，在保证合法的情况下 xix_ixi 的值越小越好。因此设 fif_ifi 表示当前处理了 Li∼iL_i\sim iLi ∼i 的人，xix_ixi 的值最小是多少。显然有初始条件 fLi=lLif_{L_i} = l_{L_i}fLi =lLi ，转移方程 fi=max⁡(fi−1+d,li)f_i=\max(f_{i-1}+d,l_i)fi =max(fi−1 +d,li )。此时合法的充要条件即为 ∀i∈[Li,Ri]∩N,fi≤ri\forall i\in[L_i,R_i]\cap\mathbb N,f_i\le r_i∀i∈[Li ,Ri ]∩N,fi ≤ri 。 因为每次询问会单独给出一个 ddd 所以上面的 dp 无法直接上 ddp 维护。因此考虑套路的展开 dp 方程式，得到：fi=max⁡j=Limax⁡(lj+d(i−j))f_i=\max\limits_{j=L}^i\max(l_j+d(i-j))fi =j=Lmaxi max(lj +d(i−j))，因此可行性条件可以看作是对每个 i∈[L,R]i\in[L,R]i∈[L,R] 都有 ∀j∈[L,i),lj+d(i−j)≤rj\forall j\in[L,i),l_j+d(i-j)\le r_j∀j∈[L,i),lj +d(i−j)≤rj ，移项可得有 max⁡j=Li−1(lj+d(i−j)−rj)≤0\max\limits_{j=L}^{i-1}(l_j+d(i-j)-r_j)\le 0j=Lmaxi−1 (lj +d(i−j)−rj )≤0，套路的分离参数把 i,ji,ji,j 的项分开考虑得到 max⁡j=Li−1[(lj−jd)−(ri−id)]≤0\max\limits_{j=L}^{i-1}[(l_j-jd)-(r_i-id)]\le 0j=Lmaxi−1 [(lj −jd)−(ri −id)]≤0。为了让里面这个东西的值最大，容易想到在左侧取一个 jjj 满足 lj−jdl_j-jdlj −jd 的值最大，右侧取一个 iii 满足 ri−idr_i-idri −id 的值最小（显然需要满足 L≤j<i≤RL\le j<i\le RL≤j<i≤R）。 考虑用一个黑盒 ds 来维护上面的信息，在该黑盒的每个结点上维护信息 mxmxmx 表示在该区间上的所有 iii 中 li−idl_i-idli −id 的最大值，mimimi 表示在该区间上的所有 iii 中 ri−idr_i-idri −id 的最小值，dfdfdf 表示在该区间上所有 iii 的 (lj−jd)−(ri−id)(l_j-jd)-(r_i-id)(lj −jd)−(ri −id) 的最大值。先不管这个 ddd 怎么处理考虑先合并信息，那么假设此时要合并的结点左右儿子分别为 L,RL,RL,R 两个结点，mx,mimx,mimx,mi 是容易的直接取对应的 max⁡\maxmax / min⁡\minmin 值即可，而 dfdfdf 则可以直接从左右儿子继承，或在 LLL 中取 max⁡\maxmax，在 RRR 中取 min⁡\minmin，即：df=max⁡(L.df,R.df,L.mx−R.mi)df=\max(L.df,R.df,L.mx-R.mi)df=max(L.df,R.df,L.mx−R.mi)。 此时考虑 ddd 的信息怎么处理，这个东西可以看作是每次操作会先对区间的 iii 位置值对应增加 ididid，操作结束时刻对区间的 iii 位置值对应减少 ididid，也就是每次区间加 / 减一个一次函数。注意到一次操作内只有给定的询问区间 [L,R][L,R][L,R] 内的数才会被考虑到其余的数都不会被考虑到，因此直接把区间加减一次函数看作是对整体做操作。然后考虑到问题没有强制在线因此考虑 P5073 的套路把所有的 ddd 离线下来从小到大排序，此时相邻两次 ddd 的询问可以看作是整体加斜率为两个 ddd 的差（这个值一定 ≥0\ge 0≥0）截距为 000 的一次函数，因此直接上 KTT 大力维护即可（注：为了保持 KTT 的结构这里需要把最小值取反，维护最小值相反数的最大值）。 然后容易发现 kkk 这个信息是好处理的，很显然把 Li,Li+1,…,RiL_i,L_i+1,\ldots,R_iLi ,Li +1,…,Ri 这些人按顺序依次分配到 1,2,3,…,k,1,2,3,…,k,1,…1,2,3,\ldots,k,1,2,3,\ldots,k,1,\ldots1,2,3,…,k,1,2,3,…,k,1,… 队内就一定是最优的，证明简单调整法即可。 总时间复杂度为 O(nklog⁡3n)O(nk\log^3n)O(nklog3n) 瓶颈在于维护 KTT。但是众所周知 KTT 十分跑不满，实际运行下来也就 O(nklog⁡2n)O(nk\log^2n)O(nklog2n) 级别，因此可以通过该题。 2026.03.21 前路漫漫 总有绕不过的弯 人生太短 悲欢自渡皆是伤 这熙攘的人潮 谁不迷惘 谁不是 在崩溃的边缘 苦求着希望 想要用魔法 解开生活的惆怅 谁不是奔跑在黑暗中 追寻微弱的光 也曾轻言过失败 也曾被冷眼相待 在最平庸的日子里 频繁受伤害 （王小帅 天真的橡皮） 029. P15502 [ICPC 2025 APC] BOOK SORTING（*2900\COLOR{RED}{2900}2900） 容易证明一定存在一个最优形态，满足存在两个位置 1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n，使得执行的操作形如： * 把 l−1,l−2,…,1l-1,l-2,\ldots,1l−1,l−2,…,1 这些书按顺序移动到最左侧。 * 把 r+1,r+2,…,nr+1,r+2,\ldots,nr+1,r+2,…,n 这些书按顺序移动到最右侧。 * l∼rl\sim rl∼r 范围内的书全部相邻项交换排序。 因此贡献即为：n−1−(r−l)+inv(al,al+1,…,ar)n-1-(r-l)+\text{inv}(a_l,a_{l+1},\ldots,a_r)n−1−(r−l)+inv(al ,al+1 ,…,ar ) 也就是最大化 (r−l)−inv(al,al+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar ) 的值，其中 inv(seq)\text{inv}(seq)inv(seq) 表示 seqseqseq 序列的逆序对的数量。 （注：这里的 aaa 是 ppp 的逆排列，即 api=ia_{p_i}=iapi =i）。 考虑固定右端点 rrr，记 SrS_rSr 集合内存储了所有左端点 lll 满足 1≤l≤r1\le l\le r1≤l≤r 且对于所有位置 j∈(l,r]j\in(l,r]j∈(l,r]，都有 (r−l)−inv(al,al+1,…,ar)>(r−j)−inv(aj,aj+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)>(r-j)-\text{inv}(a_j,a_{j+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar )>(r−j)−inv(aj ,aj+1 ,…,ar )。 此时把 SrS_rSr 按照左端点 lll 的位置从大到小排序（下标从 111 开始），则有一个关键结论：(r−Sr,j)−inv(aSr,j,aSr,j+1,…,ar)=j−1(r-S_{r,j})-\text{inv}(a_{S_{r,j}},a_{S_{r,j}+1},\ldots,a_r)=j-1(r−Sr,j )−inv(aSr,j ,aSr,j +1 ,…,ar )=j−1。为了方便，后面记 (r−l)−inv(al,al+1,…,ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)(r−l)−inv(al ,al+1 ,…,ar ) 的值为 f(l,r)f(l,r)f(l,r)。下面给出该结论的证明： :::success[证明] 要证明的结论为：f(Sr,j,r)=j−1f(S_{r,j},r)=j-1f(Sr,j ,r)=j−1。 套路的考虑对临项做差，得到 f(i,r)−f(i+1,r)=1−gif(i,r)-f(i+1,r)=1-g_if(i,r)−f(i+1,r)=1−gi ，其中 gig_igi 的值为 [i+1,r][i+1,r][i+1,r] 中比 aia_iai 小的元素的数量。因为 gi≥0g_i\ge 0gi ≥0 所以显然有 f(i,r)≤f(i+1,r)+1f(i,r)\le f(i+1,r)+1f(i,r)≤f(i+1,r)+1。 因为 Sr,∗S_{r,*}Sr,∗ 集合内只有对应 fff 值严格变大的位置，因此一定有 f(Sr,j,r)=f(Sr,j−1,r)+1f(S_{r,j},r)=f(S_{r,j-1},r)+1f(Sr,j ,r)=f(Sr,j−1 ,r)+1。而又因为有 f(Sr,1=r,r)=0f(S_{r,1}=r,r)=0f(Sr,1 =r,r)=0，因此 f(Sr,j,r)=j−1f(S_{r,j},r)=j-1f(Sr,j ,r)=j−1，命题得证。 ::: 因此最大化 (r−l)−inv(al,al+1,…ar)(r-l)-\text{inv}(a_l,a_{l+1},\ldots a_r)(r−l)−inv(al ,al+1 ,…ar ) 即 f(l,r)f(l,r)f(l,r) 的最大值其实就是 max⁡1≤r≤n(∣Sr∣−1)\max\limits_{1\le r\le n}(|S_r|-1)1≤r≤nmax (∣Sr ∣−1)，因此只需要对每个右端点 rrr 求出 ∣Sr∣|S_r|∣Sr ∣ 的值即可。 直接求 SrS_rSr 是困难的，因此可以想到通过 SrS_rSr 递推出 Sr+1S_{r+1}Sr+1 。显然此时有 f(r+1,r+1)=0f(r+1,r+1)=0f(r+1,r+1)=0。若不考虑逆序对的影响则有 f(l,r+1)=f(l,r)+1f(l,r+1)=f(l,r)+1f(l,r+1)=f(l,r)+1，但是若有 al>ar+1a_l>a_{r+1}al >ar+1 则 f(1,r+1),f(2,r+1),…,f(l,r+1)f(1,r+1),f(2,r+1),\ldots,f(l,r+1)f(1,r+1),f(2,r+1),…,f(l,r+1) 都会受到这组逆序对的影响，导致这些 fff 值全部减去 111。 考虑维护该事件对 Sr+1S_{r+1}Sr+1 的影响。因为在考虑逆序对影响之前有 f(Sr,j)=j−1f(S_{r,j})=j-1f(Sr,j )=j−1，现在对左端点 p∈[1,l]p\in[1,l]p∈[1,l] 的 ppp 对应的 fff 值减少 111，找出最大的位置 qqq 满足 qqq 是集合中最大的满足 Sr,q≤lS_{r,q}\le lSr,q ≤l 的位置，则此时 Sr,1,Sr,2,…,Sr,q−1S_{r,1},S_{r,2},\ldots,S_{r,q-1}Sr,1 ,Sr,2 ,…,Sr,q−1 对应的 fff 值不会变化，Sr,q,Sr,q+1,…S_{r,q},S_{r,q+1},\ldotsSr,q ,Sr,q+1 ,… 对应的 fff 值都会减少 111。因此此时只有 Sr,qS_{r,q}Sr,q 一个位置对应的 fff 值不再是前缀 max⁡\maxmax 位置，在集合中二分出这个位置并将其删除即可。 容易想到用 set 来维护这个结构，每次从 SrS_rSr 扩展到 Sr+1S_{r+1}Sr+1 只需要先在集合加入 f(r+1,r+1)f(r+1,r+1)f(r+1,r+1) 的影响，然后再二分出 qqq 的位置并将 Sr,qS_{r,q}Sr,q 从集合中删除。显然该算法流程的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)，可以通过该题。 030. [ABC450G] RANDOM SUBTRACTION（*2400\COLOR{PINK}{2400}2400） 可以证明，n>2n>2n>2 时答案一定只和 ∑i=1nai,∑i=1nai2\sum\limits_{i=1}^na_i,\sum\limits_{i=1}^na_i^2i=1∑n ai ,i=1∑n ai2 有关。下面给出上述结论的证明： ::::success[证明]{open} :::success[结论]{open} E[x2]E[x^2]E[x2] 一定是关于 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的二次式。 ::: :::success[证明] 操作形如选择两个数 a,ba,ba,b，把这两个数删除然后再加入 a−ba-ba−b 这个元素。因为这是一个线性操作，因此 xxx 一定是 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的一个线性组合。 因此 x2x^2x2 是关于 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 的二次式，根据期望的线性性可知 E[x2]E[x^2]E[x2] 同样也是二次式。 ::: 因此考虑把 E[x2]E[x^2]E[x2] 用二次式的形式表示出来，即 ∑i=1nαiAi2+∑i=1n∑j=1n[i≠j]βi,jAiAj\sum\limits_{i=1}^n\alpha_iA_i^2+\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]\beta_{i,j}A_iA_ji=1∑n αi Ai2 +i=1∑n j=1∑n [i=j]βi,j Ai Aj 。 但是注意到 E[x2]E[x^2]E[x2] 的值不能因为交换 AAA 数组中的两个位置就导致其值发生变化，因此必须有：α1=α2=…=αn,β1,2=β1,3=β1,4=…=βn,n−1\alpha_1=\alpha_2=\ldots=\alpha_n,\beta_{1,2}=\beta_{1,3}=\beta_{1,4}=\ldots=\beta_{n,n-1}α1 =α2 =…=αn ,β1,2 =β1,3 =β1,4 =…=βn,n−1 。也即 E[x2]E[x^2]E[x2] 可以表示为 α∑i=1nAi2+β∑i=1n∑j=1n[i≠j]AiAj\alpha\sum\limits_{i=1}^nA_i^2+\beta\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]A_iA_jαi=1∑n Ai2 +βi=1∑n j=1∑n [i=j]Ai Aj 。 此时记 s1=∑i=1nAi,s2=∑i=1nAi2s_1=\sum\limits_{i=1}^nA_i,s_2=\sum\limits_{i=1}^nA_i^2s1 =i=1∑n Ai ,s2 =i=1∑n Ai2 ，把上式所有含 AAA 的项都用 s1,s2s_1,s_2s1 ,s2 表示，得到：E[x2]=αs2+β(s12−s2)E[x^2]=\alpha s_2+\beta(s_1^2-s_2)E[x2]=αs2 +β(s12 −s2 )。 :::: 此时可以直接写个暴力然后把 α,β\alpha,\betaα,β 的值打表求出来，下面给出一个正常推导的做法。 先给数组 AAA 代入特值，令 A1=A2=…=An−1=0,An=tA_1=A_2=\ldots=A_{n-1}=0,A_n=tA1 =A2 =…=An−1 =0,An =t，则显然有 E[x2]=t2,s1=t,s2=t2E[x^2]=t^2,s_1=t,s_2=t^2E[x2]=t2,s1 =t,s2 =t2，代入前面给出的式子得到 E[x2]=t2=αt2E[x^2]=t^2=\alpha t^2E[x2]=t2=αt2，因此必然有 α=1\alpha=1α=1。 考虑记 bib_ibi 表示 n=in=in=i 时上式 β\betaβ 的值，则 E[x2]=s2+bn(s12−s2)E[x^2]=s_2+b_n(s_1^2-s_2)E[x2]=s2 +bn (s12 −s2 )。此时考虑若在某次操作中选择了 i,ji,ji,j 两个位置，s2s_2s2 的值会减少 2AiAj2A_iA_j2Ai Aj 。因为 E[AiAj]=s12−s2n(n−1)E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}E[Ai Aj ]=n(n−1)s12 −s2 ，所以有 E[s2]=s2−2(s12−s2)n(n−1)E[s_2]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}E[s2 ]=s2 −n(n−1)2(s12 −s2 ) 。 s12−s2s_1^2-s_2s12 −s2 的值会增加 2AiAj+4Aj2−4Ajs12A_iA_j+4A_j^2-4A_js_12Ai Aj +4Aj2 −4Aj s1 ，对其每项分别计算期望，得到：E[Aj]=s1n,E[Aj2]=s2n,E[AiAj]=s12−s2n(n−1)E[A_j]=\frac{s_1}n,E[A_j^2]=\frac{s_2}n,E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}E[Aj ]=ns1 ,E[Aj2 ]=ns2 ,E[Ai Aj ]=n(n−1)s12 −s2 ，因此有 E[s12−s2]=s12−s2−4s1×s1n+4×s2n+2(s12−s2)n(n−1)E[s_1^2-s_2]=s_1^2-s_2-4s_1\times\frac{s_1}n+4\times\frac{s_2}n+\frac{2(s_1^2-s_2)}{n(n-1)}E[s12 −s2 ]=s12 −s2 −4s1 ×ns1 +4×ns2 +n(n−1)2(s12 −s2 ) ，化简可得 E[s12−s2]=(n−2)(n−3)(s12−s2)n(n−1)E[s_1^2-s_2]=\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}E[s12 −s2 ]=n(n−1)(n−2)(n−3)(s12 −s2 ) 。 记 fn(A)f_n(A)fn (A) 为长度为 nnn 的 AAA 序列最后得到 x2x^2x2 的期望值，则有 f1(A)=A12,f2(A)=(A1−A2)2,fn(A)=E[fn−1(A′)]f_1(A)=A_1^2,f_2(A)=(A_1-A_2)^2,f_n(A)=E[f_{n-1}(A')]f1 (A)=A12 ,f2 (A)=(A1 −A2 )2,fn (A)=E[fn−1 (A′)]，其中 A′A'A′ 是 AAA 序列进行一次操作后得到的序列，把 E[x2]E[x^2]E[x2] 代入上式可得 fn(A)=E[s2+bn−1(s12−s2)]=s2−2(s12−s2)n(n−1)+bn−1(n−2)(n−3)(s12−s2)n(n−1)f_n(A)=E[s_2+b_{n-1}(s_1^2-s_2)]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}+b_{n-1}\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}fn (A)=E[s2 +bn−1 (s12 −s2 )]=s2 −n(n−1)2(s12 −s2 ) +bn−1 n(n−1)(n−2)(n−3)(s12 −s2 ) 。又因为 fn(A)=s2+bn(s12−s2)f_n(A)=s_2+b_n(s_1^2-s_2)fn (A)=s2 +bn (s12 −s2 )，联立两个 fn(A)f_n(A)fn (A) 的关系式可得 bn=−2n(n−1)+(n−2)(n−3)bn−1n(n−1)b_n=-\frac2{n(n-1)}+\frac{(n-2)(n-3)b_{n-1}}{n(n-1)}bn =−n(n−1)2 +n(n−1)(n−2)(n−3)bn−1 。线性求出前缀的逆元然后模拟上述过程可以做到 O(n)O(n)O(n) 求解答案。 :::success[能不能 O(1)O(1)O(1) 求出 bnb_nbn 的值？] 先观察样例可以发现答案形如 23\frac2332 加上一个数，然后再结合暴力打表，可以猜想 n≥3n\ge 3n≥3 时有 bn=−23(n−1)b_n=-\frac2{3(n-1)}bn =−3(n−1)2 ，然后简单数学归纳证明即可。 ::: :::warning[注意] 特判 n≤2n\le 2n≤2 的时候一定要记得给答案平方！！！ ::: 2026.03.22 那时候手心余温刚好 晚风很温柔有你陪就足够 时间是个小偷 无情盗走你我之间的所有 未留温暖又平凡的以后 你说分开也能相守 不过一个人把回忆保留 却还记得你的笑容 （yihuik苡慧 银河与星斗） 031. CF1579G MINIMAL COVERAGE（*2100\COLOR{ORANGE}{2100}2100） 有两个端点比较难受，所以考虑转化问题，找到最小的 mmm 使得存在一个起点 t∈[0,m]t\in [0,m]t∈[0,m] 使得每一步 +ai+a_i+ai 或 p−aip-a_ip−ai 后值都在 [0,m][0,m][0,m] 范围内。 显然 mmm 是有单调性的，所以考虑二分 mmm 的值，判定是否合法容易简单想到 O(nm)O(nm)O(nm) 暴力背包 dp。此时总时间复杂度为 O(nVlog⁡V)O(nV\log V)O(nVlogV)，其中 V=∑i=1nai=O(n2)V=\sum\limits_{i=1}^n a_i=O(n^2)V=i=1∑n ai =O(n2)，即总时间复杂度为 O(n3log⁡n)O(n^3\log n)O(n3logn)。 考虑优化。容易发现 dp 转移的形式就是对一个 010101 序列整体左移整体右移然后再按位与把序列框在 [0,m][0,m][0,m] 范围内。因此容易想到用 bitset 简单优化做到 O(n3log⁡nω)O(\frac{n^3\log n}\omega)O(ωn3logn ) 求解。 但是这个时候还是过不去。考虑进一步优化，注意到答案的上界不会超过 2max⁡ai2\max a_i2maxai 。证明的话考虑若一个数大于 max⁡ai\max a_imaxai 那么下一个直接减 aia_iai 一定不会使得上界超过 2max⁡ai2\max a_i2maxai 。把二分的上界改设为 2max⁡ai2\max a_i2maxai 可以做到总时间复杂度 O(n2log⁡nω)O(\frac{n^2\log n}\omega)O(ωn2logn ) 可以通过该题。 032. CF1768E PARTIAL SORTING（*2300\COLOR{YELLOW}{2300}2300） 感觉比较像 sale（？但是要简单一些 可以证明对于任意一个排列都最多只需要三次操作使得排列变得满足条件。因此考虑分别计数需要 0,1,2,30,1,2,30,1,2,3 次操作可以排序的排列数量： * 需要 000 次操作的排列数量：显然答案就是 111。 * 需要 111 次操作的排列数量：显然这次操作只能把前 2n2n2n 个数排序或把后 2n2n2n 个数排序，因此需要不超过 111 次操作的排列数量可以被表示为前 nnn 个数正好是 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 或后 nnn 个数正好是 2n+1,2n+2,…,3n2n+1,2n+2,\ldots,3n2n+1,2n+2,…,3n 的排列数量，简单容斥可得答案为 2(2n)!−n!2(2n)!-n!2(2n)!−n!。 * 需要 222 次操作的排列数量：显然此时排列要么 1∼n1\sim n1∼n 元素在前 2n2n2n 个位置，要么 2n∗∗∗∗im3n2n****im 3n2n∗∗∗∗im3n 元素在后 2n2n2n 个位置。对于需要不超过 222 次操作的排列数量，若假设两个条件互斥，则显然答案可以被计数为 2(2n)!n!(2nn)2(2n)!n!\binom{2n}n2(2n)!n!(n2n )。然后考虑容斥，计数同时满足前面给出的两个条件的排列数目。容易想到枚举出现在中间区间里数的情况。这里枚举 iii 表示恰好有 iii 个数值在 [n+1,2n][n+1,2n][n+1,2n] 范围内出现在序列的前 nnn 个位置。那么可以这样计数： * 前 nnn 个位置里有 iii 个数字在 [1,n][1,n][1,n] 范围内，方案数是 n!(ni)n!\binom nin!(in )。 * 中 nnn 个位置里有 n−in-in−i 个数在 [1,n][1,n][1,n] 范围内，方案数是 n!(ni)n!\binom nin!(in )。 * 后 nnn 个位置里有 iii 个数在 [n+1,3n][n+1,3n][n+1,3n] 范围内，方案数是 n!(2n−in)n!\binom{2n-i}nn!(n2n−i )。 * 直接乘法原理乘起来计数即可。 * 需要 333 次操作的排列数量：直接用排列数量 (3n)!(3n)!(3n)! 减去需要 0,1,20,1,20,1,2 次操作的排列数量即可。 该算法总时间复杂度为 O(n)O(n)O(n)，可以通过该题。 2026.03.23 世界赠予我虫鸣 也赠予我雷霆 赠我弯弯一枚月 也赠予我晚星 赠我一场病 又慢慢痊愈摇风铃 赠我一场空 又渐渐填满真感情 （王菲 世界赠予我的） 033. AT_ARC122_D [ARC122D] XOR GAME（*2400\COLOR{PINK}{2400}2400） 感觉是比较套路的题？注意到问题可以转化为把 2n2n2n 个数分成 nnn 个二元组，使得每个二元组内两个数的异或的最大值最小。套路的从二进制的高位开始向低位考虑： * 若当前位上有偶数个数二进制表示为 111，则显然可以贪心的两两分组使得 111 和 111 分组 000 和 000 分组，因此直接按二进制 0,10,10,1 分为两组然后分别递归处理即可。 * 若当前位上有奇数个数二进制表示为 111，则必然需要找恰好一组数使得其中一个数二进制表示为 111，另一个数二进制表示为 000。直接贪心的找出一组异或最小的数，可以证明这个贪心策略正确。用 01-Trie 维护信息，时间复杂度为 O(nlog⁡V)O(n\log V)O(nlogV) 可以通过该题。 034. P6009 [USACO20JAN] NON-DECREASING SUBSEQUENCES P（*2600\COLOR{RED}{2600}2600） 【模板】猫树分治。对于当前的分治区间 [l,r][l,r][l,r] 而言： * 若 l=rl=rl=r，则直接处理即可。 * 否则，记区间的中点为 MMM，则先分别递归处理 [l,M][l,M][l,M] 和 [M+1,r][M+1,r][M+1,r] 两个区间内的答案，然后套路的记 fi,jf_{i,j}fi,j 表示 [i,M][i,M][i,M] 区间内最后一个元素是 jjj 的不下降子序列的数量，gi,pg_{i,p}gi,p 表示 [M+1,i][M+1,i][M+1,i] 区间内第一个元素是 ppp 的不下降子序列的数量，转移直接枚举 j,pj,pj,p 然后合并 f,gf,gf,g 两个数组的 dp 信息即可。 总时间复杂度为 O(nk2log⁡n)O(nk^2\log n)O(nk2logn)，可以通过该题。 2026.03.24 Ho baby 情话多说一点 想我就多看一眼 表现多一点点 让我能真的看见 Oh bye 少说一点 想陪你不只一天 多一点 让我心甘情愿 爱你[比心] （王心凌 爱你） 035. WIKIPEDIA（*2600\COLOR{RED}{2600}2600） 考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 qqq 是合法的当且仅当删除 qqq 序列的 nnn 后得到的序列 ttt 从后往前操作可以把升序排列变为 ppp。因此答案就是 nnn 乘以能够得到排列 ppp 的序列 ttt 的数量。 更确切的说：记 sis_isi 表示当前操作交换 ai,ai+1a_i,a_{i+1}ai ,ai+1 两个数，则对于长度为 n−1n-1n−1 的排列 ttt，操作过程可以看作是：从排列 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 开始按顺序执行操作 st1,st2,…,stn−1s_{t_1},s_{t_2},\ldots,s_{t_n-1}st1 ,st2 ,…,stn −1 并最终得到 ppp 排列。最后答案额外乘以 nnn。 注意到若 ∣i−j∣>1|i-j|>1∣i−j∣>1，则 sis_isi 和 sjs_jsj 两个操作调换顺序不会影响最后得到的排列。考虑记 did_idi ：若 di=1d_i=1di =1 则表示 iii 在 ttt 中出现在 i+1i+1i+1 的前面，否则（di=0d_i=0di =0）表示 iii 在 ttt 中出现在 i+1i+1i+1 的后面。此时考虑把 1,2,3,…,n−11,2,3,\ldots,n-11,2,3,…,n−1 看作是图上的若干结点，则若 di=1d_i=1di =1 则连一条 i→i+1i\to i+1i→i+1 的边，否则连一条 i+1→ii+1\to ii+1→i 的边。则此时 ttt 正好是这张有向图的一个拓扑序。 记 S1,S2S_1,S_2S1 ,S2 两个集合为：S1={i+1∣di=1},S2={i+1∣di=0}S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbraceS1 ={i+1∣di =1},S2 ={i+1∣di =0}。则最终得到的置换 ppp 一定存在一个循环分解形如 1,S1,n,S21,S_1,n,S_21,S1 ,n,S2 的形式，且 S1S_1S1 一定是升序排列的，S2S_2S2 一定是降序排列的。 此时套路的记 π\piπ 为 ttt 的逆排列，则 ddd 的限制条件形如： * di=1d_i=1di =1：πi<πi+1\pi_i<\pi_{i+1}πi <πi+1 * di=0d_i=0di =0：πi>πi+1\pi_i>\pi_{i+1}πi >πi+1 问题变为计数有多少个长度为 n−1n-1n−1 的排列满足上述 ddd 对 π\piπ 的限制。因此考虑套路的 dp：设 fi,jf_{i,j}fi,j 表示当前处理了排列的前 iii 个元素，满足 ddd 的前 i−1i-1i−1 个限制，且最后一个数是这 iii 个数里第 jjj 小的元素。则转移枚举下一个数的排名可以做到 O(n3)O(n^3)O(n3)。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 O(n2)O(n^2)O(n2) 可以通过该题。 036. AT_AGC071_C [AGC071C] ORIENTABLE AS DESIRED（*32003\COLOR{RED}{200}3200） :::info[结论 111] 若无向图 GGG 是一棵树，则一定不存在这样的一个数组 XXX 满足题目中给出的条件。 ::: :::warning[提示 111] 试着给树定根，然后自底向上递归处理度数信息？ ::: ::::success[证明结论 111] 考虑先给树随便定一个根。此时很显然叶子结点可以满足条件。 :::info[结论 1.11.11.1] 翻转一个结点 uuu 子树内所有边以及 uuu 和其父结点的边的方向不会影响 uuu 子树内除 uuu 结点以外的所有点的合法性。 ::: :::warning[提示 1.11.11.1] 考虑 uuu 子树内的结点入度和出度会怎么变化？ ::: :::success[证明 1.11.11.1] 翻转一个结点 uuu 子树内所有的边后，对于 uuu 子树内一点 vvv，若满足 v≠uv\neq uv=u 则 vvv 点操作前后一定是恰好交换了入度和出度的值。 ::: 而对于非叶子结点的限制，考虑先递归处理其所有子结点 vvv 的子树条件，使得对于所有 vvv 都是满足条件的。 考虑先给每个子结点 vvv 的子树以及 u←vu\leftarrow vu←v 的边随便定向使得 vvv 子树内所有结点的信息都是合法的。此时若 uuu 结点不合法，根据结论 1.11.11.1 可知此时翻转 vvv 子树内所有的边以及 u←vu\leftarrow vu←v 的边不会导致 vvv 子树内任意一个点不再满足度数条件，而这样会导致 uuu 的入度和出度发生 ±1\pm 1±1 或 ∓1\mp 1∓1 的变化。容易发现必然存在一个调整方案使得 uuu 满足其度数条件。 :::: :::info[结论 222] 若图 GGG 不是二分图，则必然存在一个数组 XXX 满足题目给出的条件。 ::: :::warning[提示 222] 试着构造一个特殊的 XXX 数组？ ::: :::success[证明结论 222] 构造 X1=X2=…=Xn=0X_1=X_2=\ldots=X_n=0X1 =X2 =…=Xn =0。则此时要求一个点的入度或出度中至少有一个为 000。 也就是对于一个结点 uuu，要么和其相邻的边全都是从 uuu 出发的，要么和其相邻的边全都是到达 uuu 的。 考虑按照这个条件把所有点 uuu 分为两类点：若 uuu 点相邻的所有边均从 uuu 出发，则称其为 111 类点，否则称其为 222 类点。 则根据两类点的定义可知，一条边定向后只可以是从 111 类点连向 222 类点的边，即在原图上只能存在连接111 类点和 222 类点的边，不能存在一条边连接的两个点类别相同。因此若要存在一个定向方案满足条件，则图必须是一张二分图。 因此对非二分图，构造 X1=0,X2=0,…,Xn=0X_1=0,X_2=0,\ldots,X_n=0X1 =0,X2 =0,…,Xn =0 就一定不满足题目中给出的度数条件。 ::: :::warning[提示 333] 是否只需要研究一类特殊的 XXX 数组就可以正确求解问题？ ::: :::info[结论 333] 只需要研究形如 Xi=k,Xj=0(∀j,j≠i)X_i=k,X_j=0(\forall j,j\neq i)Xi =k,Xj =0(∀j,j=i) 的数组 XXX 即可。 ::: :::::success[证明结论 333] 先考虑若一个序列 XXX 中只有一个位置 XiX_iXi 的值可以不为 000，定向后得到的有向图会形如什么样。容易想到这张图除了 iii 结点以外，每个结点要么和其相邻的所有边都从她出发，要么和其相邻的所有点都连向她。 ::::warning[提示 3.13.13.1] 如果翻转树上两个点 u,vu,vu,v 的简单路径上所有边的方向，那么点度数的信息会发生怎样的变化？ :::: ::::success[提示 3.13.13.1 的答案] 容易发现若 uuu 到 vvv 路径上的点按照顺序可以写作为 u,x1,x2,…,xp,vu,x_1,x_2,\ldots,x_p,vu,x1 ,x2 ,…,xp ,v，则 x1,x2,…,xpx_1,x_2,\ldots,x_px1 ,x2 ,…,xp 点的入度和出度都不会发生变化。而 u,vu,vu,v 两点的入度要么增加 111 要么减少 111，出度则刚好相反。 :::: 考虑对于一个不合法的序列 XXX，记位置 v1,v2,…,vkv_1,v_2,\ldots,v_kv1 ,v2 ,…,vk 满足 Xvi≠0X_{v_i}\neq 0Xvi =0，则考虑每次选择两个非零点 vi,vjv_i,v_jvi ,vj 然后通过提示 3.13.13.1 中给出的操作把 viv_ivi 上度数不为 000 的部分转移到 vjv_jvj 上即可。且因为这个转移操作只需要把 i→ji\to ji→j 路径上所有边的方向翻转，因此设得到的新序列 YYY，则 XXX 不合法的充要条件即为 YYY 不合法，反之同理。 ::::: （这里只讨论 GGG 是二分图且不是树的情况）此时特判掉 XXX 序列全 000 的特殊情况，则对于给定的图 GGG，考虑固定 ppp 点，满足 Xp≠0X_p\neq 0Xp =0。此时考虑在图 GGG 中删除 ppp 点以及所有一端为 ppp 点的边，则此时： :::info[结论 444] 二分图删除一个结点和该结点相邻的边后，得到的新图仍然是一张二分图。 ::: :::info[结论 555] 若一张二分图中所有结点对应的 XXX 值都为 000，则确定一个点的入度为 000 / 出度为 000 后，一定可以确定整个连通块内每个点入度为 000 / 出度为 000。 ::: :::success[证明结论 555] 确定二分图连通块内一个点入度为 000 / 出度为 000 后，一定可以通过二分图染色的方式，使得同色的点一定同时满足入度为 000 / 出度为 000。而二分图染色确定一个点的颜色后一定可以唯一确定该点所在连通块内其余点的颜色。因此此时染色方案一定唯一，可以唯一确定。 ::: :::info[结论 666] ppp 点向同一个连通块内连的边的方向一定全部相同，即：要么全都是从 ppp 出发，要么全都是连向 ppp 点。 ::: :::success[证明结论 666] 考虑到二分图删掉若干点后仍然会得到一个二分图，而且二分图一定不存在任何奇环，而除了 ppp 点以外的所有点都要么全是从 ppp 出发的边，要么边全都连向 ppp 点。考虑到前面提到过二分图染色后颜色相同的点必须全都是从 ppp 点出发的边或者全都是连向 ppp 点的边，因此 ppp 点向同一个连通块内连的边的方向必然全都相同。 ::: 此时考虑记 ppp 点删除后各个连通块内和 ppp 点有边相连的点的数量分别为 a1,a2,…,ama_1,a_2,\ldots,a_ma1 ,a2 ,…,am ，则问题可以被转化为可重集合 {a1,a2,…,am}\lbrace a_1,a_2,\ldots,a_m\rbrace{a1 ,a2 ,…,am } 中是否对于任意一个整数 v∈[0,∑ai]v\in[0,\sum a_i]v∈[0,∑ai ] 都存在一个子集 T⊆ST\subseteq ST⊆S 满足 ∑i∈Ti=v\sum\limits_{i\in T}i=vi∈T∑ i=v。此时考虑 P15253 Raining Mex 的经典结论： :::info[结论 777] 可重集合 {a1,a2,…,am}\lbrace a_1,a_2,\ldots,a_m\rbrace{a1 ,a2 ,…,am } 中对任意一个整数 v∈[0,∑ai]v\in[0,\sum a_i]v∈[0,∑ai ] 都存在一个子集 T⊆ST\subseteq ST⊆S 满足 ∑i∈Ti=v\sum\limits_{i\in T}i=vi∈T∑ i=v，当且仅当把 aaa 数组内元素升序排序后，对任意 iii 都有 ∑j=1i−1aj≥ai−1\sum\limits_{j=1}^{i-1}a_j\ge a_i-1j=1∑i−1 aj ≥ai −1。 ::: ::::success[证明结论 777] 首先把 aaa 数组内元素升序排序。此时考虑套路的数学归纳，若当前处理的一段前缀内元素恰好可以凑出 0∼x0\sim x0∼x 的值，当前要加入的元素值为 yyy，则：若 x≥y−1x\ge y-1x≥y−1，则很显然此时可以凑出的元素的值为 0∼x+y0\sim x+y0∼x+y，否则此时无法凑出值在 x∗∗∗∗imy−1x****im y-1x∗∗∗∗imy−1 的元素。但是为什么在某个时刻出现无法凑出的值，后面就再也无法凑出这些值了呢？ :::info[结论 7.17.17.1] 对于一个升序排列长度为 nnn 的数组 aaa，若在某个时刻能够凑出的值不是一段连续的区间，则在之后无论怎么插入元素都不会使得能凑出的值是一段连续的区间。 ::: :::success[证明结论 7.17.17.1] 考虑第一次出现不是一段连续区间前，能凑出值为 0∼x0\sim x0∼x 的元素，插入了元素 yyy，则必有 x<y−1x<y-1x<y−1。此时无法凑出值为 x+1x+1x+1 的元素。而在后面加入的所有元素其值都不会小于 yyy，更不会小于 x+1x+1x+1，自然也无法凑出值为 x+1x+1x+1 的元素。而显然能凑出元素的上界就是当前所有元素的和，而这个和显然是严格大于 x+1x+1x+1 的。 ::: 因此可以证明前面给出的条件就是充要条件。 :::: 于是得到了一个时间复杂度为 O(n2)O(n^2)O(n2) 的做法：特判掉二分图和树的情况，然后考虑枚举点 ppp 作为序列 XXX 中唯一的非零点，求出删除点 ppp 后每个连通块和点 ppp 有边相连的点的数量 aia_iai ，排序（这里排序可以使用桶排）后通过结论 777 判断点 ppp 是否合法即可。显然输出 No 当且仅当对于每个 p∈[1,n]p\in [1,n]p∈[1,n]，aia_iai 都可以凑出值在 0∼∑ai0\sim \sum a_i0∼∑ai 内的元素。 考虑进一步优化该算法的时间复杂度。考虑若一个点 ppp 不是原图的割点，则原图删掉点 ppp 和与其相邻的所有边后仍然得到一张二分图，且图仍然是连通的。此时 ppp 点相邻的所有点，每个点相邻的边的方向都必须是相同的，且做二分图染色后这些和 ppp 相邻的点的颜色必然是相同的，因此这些点和 ppp 点之间的边方向必须全部指向 ppp 或者全部从 ppp 出发，也就是此时因为 ap≠0a_p\neq 0ap =0 所以只能有 ap=deg⁡(p)a_p=\deg(p)ap =deg(p)，这个情况是平凡的，无需通过上面的方法讨论。因此直接在图上求出所有的割点然后把这些点依次设为 ppp 直接枚举和 ppp 点相邻的每条边即可。总时间复杂度为 O(n+mlog⁡m)O(n+m\log m)O(n+mlogm)，可以通过该题。

官方题解 | 巅峰赛#32

巅峰赛32题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 返程拼车 普及- T2 星港远航 普及/提高- T3 霓虹线路 普及/提高- T4 雾港灯串 普及- T5 星灯选址 普及- T6 分裂晶体 提高+/省选- T1 返程拼车 题目大意 给定 nnn 个同学在数轴上的位置 xix_ixi ，每辆车最多载 222 人，且两人之间距离满足 ∣xi−xj∣≤D|x_i-x_j|\le D∣xi −xj ∣≤D 才能拼车。求最少需要多少辆车使所有同学都能回家。 题解思路 要让车辆数最少，就要让“拼车的对数”尽量多，因为每拼成一对就比两人各自打车少用一辆车。 把所有位置 xix_ixi 排序为 p1≤p2≤⋯≤pnp_1\le p_2\le \dots \le p_np1 ≤p2 ≤⋯≤pn 。在有序序列上从左到右扫描： * 如果 pi+1−pi≤Dp_{i+1}-p_i\le Dpi+1 −pi ≤D，就把这两位同学配成一对，然后跳过这两人； * 否则 pip_ipi 无法与任何更右侧的人拼车（更右只会更远），只能单独一辆车。 这是最大化不相交配对数的典型贪心：能配就立刻配相邻元素。设配对数为 pairs，答案为 cars=n−pairs.\text{cars}=n-\text{pairs}. cars=n−pairs. 复杂度：排序 O(nlog⁡n)O(n\log n)O(nlogn)，扫描 O(n)O(n)O(n)。 参考代码 T2 星港远航 题目大意 从位置 000 出发，要到达位置 LLL。初始有能量 PPP，每走 111 单位距离消耗 111 能量。沿途有若干补给站，第 iii 个补给站在位置 xix_ixi ，可以提供 aia_iai 的能量，每个站最多使用一次。求最少需要使用多少个补给站才能到达终点，若无法到达输出 −1-1−1。 题解思路 这是一个典型的贪心问题。关键在于：当当前能量不足以继续前进时，应该从之前经过的所有补给站中选择补给量最大的那个来使用。 先将所有补给站按位置排序，并把终点看成一个位置为 LLL、补给量为 000 的虚拟站。设当前最远能到达的位置为 reachreachreach，初始为 PPP，同时用一个大根堆维护所有已经经过的补给站的补给量。 从左到右扫描每个站： 如果当前站的位置 xi≤reachx_i \le reachxi ≤reach，说明可以到达，就把该站的补给量加入堆中；如果 xi>reachx_i > reachxi >reach，说明当前无法到达这个站，此时必须从堆中取出最大补给量来补充能量，使 reachreachreach 增大，并统计一次补给操作。重复这个过程，直到可以到达当前站或者堆为空。 如果堆为空仍无法前进，说明无法到达终点，输出 −1-1−1。否则最终成功走到终点，补给次数就是答案。 这个贪心策略的核心在于：每次必须补给时，选择补给量最大的站，可以让当前可达距离尽可能远，从而减少后续补给次数，是最优选择。 参考代码 T3 霓虹线路 题目大意 给定一棵有 nnn 个点的树，需要给每条边染色，颜色编号为 1∼k1\sim k1∼k。要求对于任意一个点，与它相连的所有边颜色必须两两不同。判断是否存在合法方案，若存在输出任意一种。 题解思路 树的边染色要求“每个点相邻边颜色两两不同”，这就是树上的proper edge coloring。设树的最大度数为 Δ\DeltaΔ。必要条件是 k≥Δk\ge \Deltak≥Δ：因为度为 Δ\DeltaΔ 的点周围 Δ\DeltaΔ 条边必须用不同颜色。 对树而言这也是充分条件：当 k≥Δk\ge\Deltak≥Δ 时一定能染色。构造方法用一次 DFS 从根向下分配颜色即可。 把树以 1 为根。对每个点 uuu，设与父边的颜色为 parColor[u]（根为 0）。我们给 uuu 的所有子边依次分配颜色 1..k，但跳过 parColor[u]，并且同一节点内部不重复。因为 uuu 的子边数是 deg(u)-1（根是 deg(u)），而 deg(u)≤kdeg(u)\le kdeg(u)≤k，所以总能分配完且不会用到第 k+1k+1k+1 种颜色。 实现上先用栈/队列求出父子关系，再按父到子的顺序给边赋色，复杂度 O(n)O(n)O(n)。 若 k<Δk<\Deltak<Δ，直接输出 NO。 参考代码 T4 雾港灯串 题目大意 给定一个长度为 nnn 的 01 串，可以通过翻转某一位（0↔10 \leftrightarrow 10↔1）来修改它。要求最终得到的新串满足：任意连续长度为 444 的子串中，111 的个数不能恰好为 333。求最少需要翻转多少次。 题解思路 本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 bbb，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。 用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 iii 位时，尝试把 bib_ibi 取为 0 或 1： * 若 i≥4i\ge 4i≥4，则长度为 4 的窗口正好是“上一状态的 3 位 + 当前选择的 1 位”，对应一个 4 位数 w=(mask<<1)|b_i，若 popcount(w)==3 则该选择非法； * 否则（前 3 位）没有形成长度为 4 的窗口，不需要检查。 代价增加为 [s_i\ne b_i]，新状态为 ((mask<<1)&7)|b_i。每步转移常数只有 16 次，整体复杂度为 O(n)O(n)O(n)，空间为 O(1)O(1)O(1)。 最终答案是处理完全部位置后所有 dp[mask] 的最小值。 参考代码 T5 星灯选址 题目大意 给定一个长度为 nnn 的数组 aia_iai ，表示在第 iii 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。 题解思路 这是经典的线性 DP。设 dp[i] 表示只考虑前 i 个位置能得到的最大收益，则第 i 个位置要么不选，要么选： * 不选 i：收益 dp[i-1] * 选 i：则 i-1 不能选，收益 dp[i-2] + a_i 所以递推为 dp[i]=max⁡(dp[i−1],dp[i−2]+ai).dp[i]=\max(dp[i-1], dp[i-2]+a_i). dp[i]=max(dp[i−1],dp[i−2]+ai ). 边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。 参考代码 T6 分裂晶体 题目大意 给定一棵以 1 号节点为根的树，每个节点有一个整数能量值。要求通过任意重排每个节点的子树顺序，生成字典序最小的先序遍历序列。 题解思路 对任意节点 u，设它的“最稳定子序列” S(u) 是在允许重排 u 的孩子后，u 的子树先序序列中字典序最小的那条。显然整棵树的答案就是 S(1)。 如果 u 的孩子子树最稳定子序列分别是 S(v1),S(v2),…，那么 S(u) 一定形如： S(u) = [a_u] + S(按某顺序排列的孩子 1) + S(孩子 2) + … 为了让拼接后的整体字典序最小，只需把孩子按各自的 S(v) 的字典序从小到大排序后依次拼接即可：因为先序序列在进入第一个孩子子树前已经固定为 a_u，之后最先产生差异的位置一定落在“第一个不同孩子的子序列”里，所以把最小的子序列放在最前是最优的。 因此问题变成：需要能高效比较两个子树的 S(u) 与 S(v)。直接把 S(u) 展开成数组会导致总长度平方级。 做法是把每个 S(u) 当成一条“序列对象”，用一棵隐式 Treap 维护： * 长度 len； * 两个模数下的多项式哈希值； * 支持 O(log n) 取第 k 个元素、取前缀哈希。 比较两个序列时，用二分 + 前缀哈希求它们的最长公共前缀 LCP，再比较下一位元素即可完成字典序比较。对子树排序后，用 Treap 进行序列拼接（merge）即可得到父节点的序列对象。 整体流程：先把树以 1 为根，得到父子关系与后序顺序；按后序从叶到根处理，每个节点对孩子排序并合并生成自己的序列对象，同时把排序结果存下来。最后按存下来的孩子顺序做一次先序遍历输出能量值。 复杂度：设比较一次序列为 O(log^2 n)，则总复杂度约为 O((n + 总排序比较次数)·log^2 n)，在本题规模内可通过；空间 O(n)。 参考代码

ABC 451 全题解

ABC 450 差 1s AK，气急败坏的我顺手 AK ABC 451。 题号 个人难度 tag（个人做法） AC time A 红 字符串 2'19'' B 红 STL 4'24'' C 橙 STL 10'23'' D 黄 枚举、BFS 22'33'' E 绿 MST、BFS 34'07'' F 蓝 带权 DSU 50'54'' G 紫 01 Trie、线性基 85'19'' ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ A. ILLEGAL 使用 string 类的 size() 函数或者 length() 函数判断是否为 555 的倍数即可。 B. PERSONNEL CHANGE 用一个桶记录两个学期每个社团的人数，然后相减即可。 C. UNDERSTORY 看到操作容易想到 multiset，它不会自动去重，而且自动排序，因此每次删除操作时只需要使用 upper_bound() 找大于 hhh 的第一个数，erase() 区间删除即可。 D. CONCAT POWER OF 2 由于 log⁡109≈30\log 10^9 \approx 30log109≈30，所以可以从每个 222 的幂出发，使用 BFS 暴力生成所有拼接数，用 set 去重，最后将集合中的数排序即可。 E. TREE DISTANCE 由于是稠密图，所以我们使用 Prim。以 ai,ja_{i,j}ai,j 为边权构建最小生成树。在 MST 上跑所有点对的最短路，与输入矩阵比较即可。 F. MAKE BIPARTITE 3 用带权 DSU 维护每个连通分量内的颜色关系。每个分量根节点维护 cntrt,0cnt_{rt,0}cntrt,0 和 cntrt,1cnt_{rt,1}cntrt,1 分别表示与根同色和异色的顶点数。当加边时： * 若 u,vu,vu,v 已在同一分量，检查边是否异色，若为 000 则出现奇环，不可行。 * 否则合并两个分量，根据 u,vu,vu,v 的颜色关系计算需要翻转其中一个分量的颜色，更新合并后的计数和最小黑点数。 G. MINIMUM XOR WALK 油 奠 以 死 完成了 异或粽子 和 线性基 以后，你就会发现他其实就是这俩玩意的结合。没做过先别着急做，看我操作。 这种典题有一些经典步骤： * 固定一棵生成树，任意两点间的异或 walk 最小值为 base⁡x⊕base⁡y\operatorname{base}_x \oplus \operatorname{base}_ybasex ⊕basey 与所有环的线性基组合得到的最小值。 * 所有环的异或值构成一个线性基 B⁡\operatorname{B}B，则任意两点间的最小异或值等于 min⁡s∈span(B)⁡(base⁡x⊕base⁡y⊕s)\min_{s \in \operatorname{span(B)}} \bigl( \operatorname{base}_x \oplus \operatorname{base}_y \oplus s \bigr)mins∈span(B) (basex ⊕basey ⊕s)，即 base⁡x⊕base⁡y\operatorname{base}_x \oplus \operatorname{base}_ybasex ⊕basey 在子空间 span(B)⁡\operatorname{span(B)}span(B) 中的最小表示。 * 通过线性基可以将所有 base 向量化简为代表元，使得之间两两的异或值就是原图两点间的最小异或值。 容易将问题转化为：有多少对 i,j (i<j)i,j\ (i<j)i,j (i<j) 满足 ai⊕aj≤ka_i \oplus a_j \leq kai ⊕aj ≤k。那就经典了： * 建一棵 303030 位 01 Trie，插入时统计。 * 对每个代表元，在 Trie 中查询与它异或值 ≤k\leq k≤k 的数的个数（这一步貌似是经典数位 DP 查询）。 * 注意去重，可以在插入前先查询，再插入当前数。