互动｜最近遇到过的离谱小事

互动｜😓 你最近遇到过的离谱小事 嗨，AC狗友们，生活有时候比段子还离谱 比如： * 去机房做作业，电脑开机三次蓝屏三次，第四次它自己更新了半小时。 * 老师说这道题很简单，像呼吸一样自然。结果他自己讲了四十分钟还没讲完。 * 在数学课睡过1800秒 不管多小的事，只要你觉得离谱、好笑、无语、神奇，都欢迎来分享。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎯 怎么参与？ 在评论区写下你最近遇到的一件真实发生的离谱小事。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 奖励 活动截止后（符合评论要求的）： * 评论点赞前5名 → 每人 罐头 × 50 * 随机抽取5人 → 每人 罐头 × 20 ⏰ 时间 即日起 至 2026年5月5日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 快来评论区说说：你最近遇到了什么离谱小事？ （越真实越好笑，越离谱越有奖） 往期互动

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

互动｜分享你用AI干过的“神级操作” hi，AC狗友们 AI时代，连懒人都能开挂！写作业、做笔记、催队友、编曲……今天，它全包了！ 玩法超简单： 在评论区，分享一个你用AI干过的“神级操作” —— 越实用越欢迎，越“又懒又爽”越好！ 举个栗子： * 把老师60页PPT变成3句重点+10道押题：“我用了30秒，AI用了0.3秒。” * 把乱哼的旋律变成一首完整的Lo-fi beats：“现在它是我的学习背景音，比白噪音还上头。” 你可以写： * AI帮你“偷懒”的真实操作 * 一个离谱但实用的AI用法 * AI把你的某个日常变宝的故事 奖励 活动截止，评论区符合参与条件的留言 点赞TOP5 每人获得：罐头 × 50，@༺ཌༀ我要上浙大ༀད༻，@Michael，@拉巴巴小魔仙(布)，@全站的狗子我嘴最臭(慕温)，@Zorange(ZC) 幸运奖5名 每人获得：罐头 × 20，@（百小1."QYM".4育才）回，@（百小1."QYM".4育才）回，@‎樱桃指挥官(互关)（加团）‏，@???，@寻道·渊·天道主宰 ⏰ 时间 即日起至 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[代码] :::

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

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

#Github#目前的状态

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

#创作计划#浅谈 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。这样子写代码会更好理解点。不过本质上没啥区别。 ↩︎

地球online每日任务

（4月16日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.玩一局游戏(欢乐值+3)、2.完成今日作业(欢乐值−1，智商+3)\color{green}{1.玩一局游戏(欢乐值+3)、2.完成今日作业(欢乐值-1，智商+3)}1.玩一局游戏(欢乐值+3)、2.完成今日作业(欢乐值−1，智商+3) （4月17日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.好好的做作业(欢乐值−1，智商+3)、2.给你的家人唱一首歌（精神值+1，欢乐值+3）\color{green}{1.好好的做作业(欢乐值-1，智商+3)、2.给你的家人唱一首歌（精神值+1，欢乐值+3）}1.好好的做作业(欢乐值−1，智商+3)、2.给你的家人唱一首歌（精神值+1，欢乐值+3） （4月18日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.去下面玩(欢乐值+2)、2.去你喜欢的地方玩（精神值+1，欢乐值+5）\color{green}{1.去下面玩(欢乐值+2)、2.去你喜欢的地方玩（精神值+1，欢乐值+5）}1.去下面玩(欢乐值+2)、2.去你喜欢的地方玩（精神值+1，欢乐值+5） （4月19日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1）\color{green}{1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1）}1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1） （4月20日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1）\color{green}{1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1）}1.玩一局游戏(欢乐值+3)2.完成今日作业(欢乐值−1，智商+3)3.跟朋友一起吃饭（欢乐值+3，精神值+1） （4月21日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.在学校写完作业（欢乐值+1，智商+3）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3）\color{green}{1.在学校写完作业（欢乐值+1，智商+3）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3）}1.在学校写完作业（欢乐值+1，智商+3）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3） 3.出去练习跑步（体质+2，欢乐值+1）\color{green}{3.出去练习跑步（体质+2，欢乐值+1）}3.出去练习跑步（体质+2，欢乐值+1） （4月22日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.写完作业（欢乐值+1，智商+3，疲惫值+0.5）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3，疲惫值−1）\color{green}{1.写完作业（欢乐值+1，智商+3，疲惫值+0.5）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3，疲惫值-1）}1.写完作业（欢乐值+1，智商+3，疲惫值+0.5）2.在下面跟朋友快乐的玩（精神值+1，欢乐值+3，疲惫值−1） （4月23日）地球online今日任务已刷新：\color{red}{地球online今日任务已刷新：}地球online今日任务已刷新： 1.玩一局益智游戏（欢乐值+1，智商+3，疲惫值−0.5）2.练习跳绳（体质+2，疲惫值+2）\color{green}{1.玩一局益智游戏（欢乐值+1，智商+3，疲惫值-0.5）2.练习跳绳（体质+2，疲惫值+2）}1.玩一局益智游戏（欢乐值+1，智商+3，疲惫值−0.5）2.练习跳绳（体质+2，疲惫值+2） 当疲惫值达到50时有概率触发“生病”,抑郁值达到50，有概率触发“成绩下滑”正面属性−20\color{red}{当疲惫值达到50时有概率触发“生病”,抑郁值达到50，有概率触发“成绩下滑”正面属性-20}当疲惫值达到50时有概率触发“生病”,抑郁值达到50，有概率触发“成绩下滑”正面属性−20体质达到150有概率免疫一次“生病”,智商达到150，有概率免疫一次“成绩下滑”\color{green}{体质达到150有概率免疫一次“生病”,智商达到150，有概率免疫一次“成绩下滑”}体质达到150有概率免疫一次“生病”,智商达到150，有概率免疫一次“成绩下滑”精神值达到150时有概率“负面属性−20”欢乐值达到150时有概率“正面属性+20”\color{green}{精神值达到150时有概率“负面属性−20”欢乐值达到150时有概率“正面属性+20”}精神值达到150时有概率“负面属性−20”欢乐值达到150时有概率“正面属性+20” 放假（精神值+10，欢乐值+30）\color{green}{放假（精神值+10，欢乐值+30）}放假（精神值+10，欢乐值+30） 在评论区打出你现在的属性吧\color{blue}{在评论区打出你现在的属性吧}在评论区打出你现在的属性吧 每人初始有：疲惫值0，抑郁值0，其他100\color{blue}{每人初始有：疲惫值0，抑郁值0，其他100}每人初始有：疲惫值0，抑郁值0，其他100 关注一下吧

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

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

期中考试怎么样？!

主包今天刚刚考完期中考，很疑惑为什么要在兴奋激动期待的春假来临之前举行一次生死肉搏……嗯对老师这个批卷的速度也是很快好吧，成功获得 语文37(满分四十，只考阅读)，数学95，英语100科学28(满分三十只考实验)的好成绩了哈哈哈哈可以过个好假期啦。宝宝们都肿模样呢，欢迎打评论区哦

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

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