c++。嗯对。可以。

互动｜分享你用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干过的“神级操作”，越实用越欢迎！ 往期互动

【学习笔记】随机游走优化 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[代码] :::

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

警告：五年级以上看不懂可能无法进 NOIP @YHZ@YHZ@WCQK@WCQK@STARS_SEEKER@STARS_SEEKER > 请不要发布无意义评论，否则会删评。若发布大量发布类似“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 的最大数 和插入差不多，因为二叉搜索树保证了 左子树<根节点<右子树。根据这条性质我们可以轻松实现查询前驱的功能。具体实现请参考代码注释。 查询后继 和前驱一样的，只不过反了一下，参考注释即可。不多赘述。 删除 棍木 查询第 K 小 也是递归实现，若在左子树则递归左子树，在当前节点则直接返回，当在右子树的时候记得减去左子树和当前节点的数量。 查排名 因为二叉搜索树的性质是左子树 <<< 根节点 <<< 右子树，所以当找到目标值，排名就是左子树的大小。若目标在右子树，则为右子树的查询结果加上左子树大小、当前节点值重复的数量。 完整代码就不放了。那么这样我们就得到了一个朴实无华的 BST 代码。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 平衡树的旋转与平衡调整 使我的节点旋转 旋转是平衡树维持平衡的一个重要方法。它可以在不违反二叉搜索树的性质下降低树高。这里我们来讲左旋（zag）和右旋（zig）。 右旋 先来讲右旋，其实你学完右旋就能直接推出左旋了。 下面给出两幅图，各位可以进行理解。分别是对于节点 A 的右旋前和右旋后的： 仔细观察，我们可以发现，对于节点 A 的右旋就像是把他的左孩子“提”起来，事实上我们只改变了三个节点的链接关系： 1. 将 A 的右孩子 C 的右孩子指针指向 A，将 A 的父指针指向 C； 2. 将 A 的左孩子的右孩子的父指针指向 A； 3. 将 A 的左孩子指针指向 A 的左孩子的右孩子。 那么这个时候我们的右旋操作就结束了。[1] 左旋 本质上和右旋是一样的，就是把右旋的操作反了一下。这里不多赘述。具体参考代码实现。 那么在学完左右旋之后我们来学习如何调整平衡树的平衡。这里介绍四种情况。 LL 型 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 鸣谢 用户 ID 帮助 ID：519007 帮助修改大量格式问题，/bx ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 为什么这里要说“A 的左孩子的右孩子”而不直接说“C 的右孩子”？因为在实际代码中，我们是通过当前节点，也就是我们现在所指的 A 节点来进行旋转操作，只是间接的经过左孩子节点也就是我们现在说的节点 C。这样子写代码会更好理解点。不过本质上没啥区别。 ↩︎

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

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

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

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

#Github#目前的状态

预告: 大家好，我是孤砂小白，这是目前我的网站链接别想了，目前我还在加工 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我的构思：

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

叠甲：没事干写一篇好玩，不喜勿喷，有问题欢迎指出，暂时已完结。 本文只讲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 重构树上两点之间的 LCA 的权值。 Code R 不讲了，R≈\approx≈Q，上题是最大生成树，这题是最小生成树，没了。 Code 大家觉得我有必要写S-Y吗（实际上除了S我一道都不会）

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

可能更好的阅读体验 发现有些洛谷折叠框不能在 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 :::: P6765 [APIO2020] 交换城市 * 难度：紫 * 耗时：4days，看完题解 r97v84gt 后，理解+实现也花了近一天 哇呀这和别的紫不一样啊（（（ 这咋这么难。 我真不知道该说啥了，我自己都是对着第一篇题解学的，自己去看 r97v84gt 吧。 以后有空肯定是得二刷的。 ::::success[100pts] Link :::: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ::::info[Other]{} > 碍于我平时还要跟进一些课上的题目或是校队周赛的一些杂题，一般自己做题的时间并不多，一周也就三题，感觉我好颓，决定把这些题也记录上去 P2734 [IOI 1996 / USACO3.3] 游戏 A GAME * 难度：黄 板板板。 :::success[100pts] Link ::: P3004 [USACO10DEC] TREASURE CHEST S * 难度：绿 双倍经验，随便做个滚动数组就行了。 :::success[100pts] Link ::: P1613 跑路 * 难度：绿 先跑一个 Floyd 判断每两个点是否可以直接通过 222 的整数次幂的时间到达，若可以则存一条边权为 111 的边权，再跑一个 Floyd 求最短路。 :::success[100pts] Link ::: P2966 [USACO09DEC] COW TOLL PATHS G * 难度：蓝 这个真的比较考验对 Floyd 具体理解程度。 注意到每次 Floyd 最外层循环的顺序是没有任何影响的，我们大可以直接做一个降序排序，使得当前点的 CCC 值必然比之前所有的 CCC 值大。 :::success[100pts] Link ::: P14306 【MX-J27-T3】旋律 * 难度：黄 很不错的贪心，反正我十分钟没想出来。 注意到每个区间的得分与顺序无关大可以直接排序。又想到当我们取了一个数后，把其它相同的数都取了必然更优，区间长度增加了，极差不变。 不妨开一个结构体，val⁡\operatorname{val}val 表示值，sum⁡\operatorname{sum}sum 表示出现次数。用 SSS 表示 sum⁡\operatorname{sum}sum 的前缀和加速区间求和操作，考虑一个区间 [l,r][l,r][l,r] 的贡献为 (Sr−Sl−1)×k−(val⁡r−val⁡l)=(−Sl−1×k)+(Sr×k−val⁡r)(S_r-S_{l-1})\times k-(\operatorname{val}_r-\operatorname{val}_l)=(-S_{l-1}\times k)+(S_r\times k-\operatorname{val}_r)(Sr −Sl−1 )×k−(valr −vall )=(−Sl−1 ×k)+(Sr ×k−valr )，考虑枚举 lll，即找到一个 rrr 使得后面的那一坨式子的值最多即可，做一个后缀最大值即可。 :::success[100pts] 这里我开始写了一个臭的 ST 表，实在是大材小用，后来发现写一个后缀最大值数组即可，也懒得改了。 Link ::: P1433 吃奶酪 * 难度：绿 其实是把之前 T 的代码优化了一下。 :::success[100pts] Link ::: ::::

关于“核武器”的小知识（还是太"刑"了）

--------------------------------------------------全是干货哟------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 暴力美学与末日工程的终极交响：B61热核炸弹深度解剖报告 各位军迷同仁，今天我们要聊的，不是那些在航展上光鲜亮丽的战斗机，也不是在深海里游弋的核潜艇，而是一件更为纯粹、更为本质的“战略艺术品”。你眼前的这张剖面图，是美军核武库中服役时间最长、型号最繁杂、战术灵活性最高的“多面手”——B61系列热核重力炸弹。它不像洲际导弹那样充满科幻感，也不像战略轰炸机那样气势磅礴，但它却是真正意义上能够被战术飞机携带、在战场上“随叫随到”的毁灭力量。从越战时期的阴影，到冷战对峙的前沿，再到如今F-35隐身战机的内置弹舱，B61就像一位深藏不露的武林宗师，在半个多世纪的风云变幻中，不断修炼内功，进化出了令人胆寒的全新形态。 让我们暂时抛开道德的审视，单纯从工程和武器的角度，来一场极致的“硬核拆解”。这张图展示的，不仅仅是一枚炸弹，更是一个集成了人类顶尖物理学、材料学、电子学和空气动力学智慧的精密系统。全弹由超过5500个零部件构成，每一个螺丝、每一根导线、每一层金属，都在为那个终极的瞬间——核爆，做着毫秒级的准备。 首先，我们要聚焦于它的“大脑”与“感官”——位于弹体前部的引信与电子组件。对于一枚重力炸弹而言，如何从万米高空准确命中目标，是一门复杂的学问。图中清晰可见的雷达高度计，是B61实现“空爆”威力的关键。它能在炸弹以超音速下坠的过程中，持续向地面发射雷达波，精确计算出离地高度。这意味着，B61不需要直接撞击目标，而是在目标上空的最佳高度引爆，利用冲击波横扫地面，将杀伤面积最大化。而在B61-11和B61-13这些“钻地”型号中，头锥部分则被替换为高强度合金钢，使其能够像一颗致命的钢钉，穿透数米厚的钢筋混凝土或数十米的土层，在地下深处引爆，彻底摧毁敌方的指挥中心或核武库。 剥开前端的电子舱，我们就进入了B61最核心、最神秘的领域——核弹头部分。这里采用的是经典的“泰勒-乌拉姆构型”，也就是我们常说的“两级热核武器”。这并非简单的“原子弹+氢弹”的堆砌，而是一场精心编排的能量接力赛。图中标注的“COUGAR”是初级裂变装置，它是整个核反应的“火柴”。其核心是钚-239制成的裂变弹，当外围的高能炸药被精确起爆，产生向心聚爆的压力，将钚核心压缩至超临界状态，瞬间引发链式裂变反应。这个过程在微秒级时间内，释放出数千万度的高温和巨量的X射线。 但这仅仅是开始。初级产生的能量，并不是直接去炸毁目标，而是被用来点燃真正的“燃料”。这就不得不提到图中那个被称为“辐射瓶”的精妙结构。初级释放的X射线，以光速在弹体内部的辐射通道中传播，均匀地包裹并压缩次级装置。次级装置，也就是图中的“MACE”，是B61威力的真正源泉。它包含了铀-235制成的“火花塞”和氘化锂-6聚变燃料。在初级X射线的辐射内爆作用下，次级被极度压缩，温度飙升，最终触发了轻原子核的聚变反应。聚变释放的能量是裂变的数倍，这才是氢弹能够产生百万吨级当量的根本原因。为了确保这场微观世界的“点火”万无一失，B61内部还配备了“中子枪”和“增强腔”。中子枪在裂变核心达到临界质量前注入中子流，确保链式反应准时启动；而增强腔则注入氘氚气体，在裂变过程中产生额外的中子，像涡轮增压一样，将初级裂变的效率压榨到极致。 B61最令人着迷的，莫过于它的“模块化”与“可变当量”设计。这枚炸弹就像一个可以随意调节火力的“核能水龙头”。通过弹体侧面的控制面板，地勤人员可以输入指令，调整初级和次级之间的能量耦合效率，从而让同一枚炸弹在0.3千吨到36万吨TNT当量之间自由切换。在战术层面，它可以以300吨的低当量，精确摧毁一个机场或装甲集群，将附带损伤降到最低；在战略层面，它又可以化身为36万吨的“城市毁灭者”，其威力是广岛原子弹的二十多倍。这种灵活性，使得B61模糊了战术武器与战略武器的界限，成为美国总统手中一张极具威慑力的“王牌”。 而最新的B61-12和B61-13型号，更是将这种威慑力推向了新的高度。它们加装了全新的“制导尾翼组件”，赋予了这枚“笨炸弹”以智慧。通过GPS和惯性导航系统的复合制导，B61-12的圆概率误差被压缩到了惊人的30米以内。这意味着，它不再需要依靠巨大的当量来弥补精度的不足，而是可以用更小的核弹头，实现“外科手术式”的精确打击。这种“低当量+高精度”的组合，极大地降低了核武器的使用门槛，使其从一种“末日武器”变成了一种在局部冲突中“可用”的选项，其战略意义不言而喻。 看着这张剖面图，我们看到的不仅是钢铁与核料的堆砌，更是一种令人窒息的工程美学。它将毁灭性的力量，封装在如此精密、如此可控的系统中，这本身就是人类智慧的一种悖论。B61，这位服役了半个多世纪的“老兵”，通过不断的升级换代，依然在21世纪的战场上散发着致命的魅力。它提醒着我们，在和平的表象之下，末日的引擎从未停止过轰鸣。 //谢谢观看，制作不易，望推举，谢谢！

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

同步在洛谷更新 题目难度应该不会很大 括号内的是 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)，可以通过该题。