9.14-9.20 学习记录

发表于 2026-09-16 更新于 2026-09-23 分类于学习记录

好颓废的一周。

9.14

VP CF Educational 191

C

题意

给你一个长度为 $n$ 的括号序列 $s$，可以通过删除 $s$ 中的最多 $k$ 个字符，最小化 $s$ 中最大合法括号子序列的长度。

$k \le n \le 5000$。

赛时思路

看完样例之后猜测，是不是一定先删 ( 再删 ) 呢？
考虑如何找到最大合法括号子序列。可以搞一个 $O(n^3)$ 的划分 dp，有没有更优的？想不出来。dp 不行就想贪心，贪心的时间复杂度通常比 dp 更优，感觉还是缺少那种，最优化问题想贪心想 dp 的直觉。
考虑这个最大合法括号子序列的结构是什么。最左侧一定是第一个 (，最右侧一定是最后一个 )。如果出现 () 的结构，那么它一定处于最大合法括号子序列中。
没啥好用的性质啊，放弃了，用时 $21$ 分钟。
想到一个诡异的贪心，首先剔除子序列开头的 ) 和结尾的 (，然后双指针找下一个 ( 和下一个 )，每次删除那个会使得距离缩小的更多的那个项。
首先明白，删除一个项至多减少 $1$ 对括号序列。按照上面那个做法贪心，只要右边不是 )，就能减少 $1$ 对。啊啊感觉还是不行啊，算了不管这题了。

正确思路

考虑如何找到最大合法括号子序列。括号序列的经典贪心是，遇到 ( 就取。我们按照这个贪心策略，遇到 ) 且 $sum > 0$ 就匹配，可以得到一个 $O(n)$ 的做法。
在这个做法的基础上进行删数。我们想让这个做法匹配到的括号最少，当遇到 ) 时，分类讨论一下：
1. 若 $sum = 1$，则恰好有一个 ( 可以和它匹配，删除这个 ( 就可以减少一对括号。实际上这里需要用一个循环来删除，因为此时的 ( 都是一一对应的。
2. 若 $sum > 1$，则此时不知道该删哪个好，于是我们就 延迟决策，先不管它。
这样的话序列最后会剩一段 $sum > 1$，左括号比较多，此时删除右括号就找不到另一个替换它，所以删右括号。删到前面的 $sum=1$ 段也没关系，一直删就好了。

D

题意

给你一个长度为 $n$ 的数组 $a$，你可以交换其中任意两个下标 $i,j$ 最多一次，问交换之后能不能使得序列中，相同的项都处于同一个块内。

$n \le 2\times 10^5,a_i \le 10^9$

赛时思路

按照值考虑，分类讨论一下：
1. 如果有一个块，不用管。
2. 如果有两个块，要么这两个块之间只有一个空隙（此时决定了一个交换的下标），要么有一个块只有一项（也决定了交换的一个下标）。
3. 如果有三个块，要求其中两个块之间只有一个空隙，另一个块只有一项。此时两个交换下标都被确定了
4. 好像没啥用啊。
操作一定选两个不同的数，所以最多管到两种值。我好像只要一次深搜出不来就基本出不来了，可能是心态上的问题，以后专门搞一个“回溯”训练吧。
没思路了，用时 $22$ 分钟。

正确思考

从操作本身的角度考虑。交换的数一定是未成功块的左右端点。这样的数很少，最多有 $12$ 个（101010），否则就无解了。
然后就是枚举这个下标，再枚举另一个下标，用一个 cnt 维护块数量，当 $cnt=种类数$ 时成功。

9.15

VP CF 1102 Div.2

D

题意

给你一个长度为 $2^k+1$ 的序列 $a$，每一项都是长度为 $n$ 的二进制数，初始时 $a_1$ 和 $a_{2^k+1}$ 是确定的。

现在要往里面填数，进行 $k$ 轮。每一轮中，找到已填的相邻两个数，这两个数中间那个数的取值就是这两个数的取值的异或值。

令 $x_i$ 表示 $a_i$ 中，二进制 $0$ 的个数。

最后计算 $\sum\limits_{i=1} x_i \times (n-x_i)$。

$n \le 10^5$，$k \le 30$.

赛时思路

手玩样例发现，数的取值只可能是 $a_1,a_{2^k+1},a_i \oplus a_{2^k+1}$ 这三种。
统计这三种取值的 $x_i$ 和数量就好了，现在的难点在于数量上。
发现这个结构具有很大的相似性，令我们联想到递归。直接递归肯定炸，那就加上记忆化。可以拆成子问题，考虑 dp。
代码写了好久，下次想清楚再开始吧。
用时 $50$ 分钟。

更优秀的思路

这个数量其实可以递推，以层数为阶段递推就好了，不用这么复杂。
然后扩展了一个数学知识，对形如 $a_n=xa_{n-1}+y$ 形式的数列，可以通过如下变换找出通项公式：

$a_n+b = xa_{n-1}+y+b=x(a_{n-1}+\frac{y+b}{x})$
当 $b=\frac{y+b}{x}$ 时，$b=\frac{y}{x-1}$
即 $a_n+\frac{y}{x-1}=x(a_{n-1}+\frac{y}{x-1})$
令 $c_i=a_i+\frac{y}{x-1}$，有 $c_i=xc_{i-1}=x^ic_1$
$a_i=x^ic_1-\frac{y}{x-1}$

E

题意

给你一个长度为 $n$ 的数组 $a$，$a_i$ 的值定义为满足以下条件的子段数量：

对于一个排列 $p$，$\min p[l…r] = p_i$。

问有多少种排列可以生产出 $a$ 数组。

$n \le 5\times 10^5$，$a_i \le 10^{12}$.

赛时思路

先来考虑如何对一个排列 $p$ 求出 $a$。找到左右两边比 $p_i$ 小的数，记其下标为 $l,r$，则 $a_i=(i-l)\times(r-i)$。

正确思路

卡点：首先确定那个最好确定的数是什么，本题里显然是最小值。最小值的 $a_i=i(n-i+1)$，对于每一个 $a_i$，判断这一位是不是最小值即可。如果存在 $1$ 个以上的最小值，那么无解。
找到这个最小值后，会将原问题分成两半。因为此时左右两边的 $a$ 实际上是独立的，被 $i$ 分割开了，左边一定不会影响右边。这个东西可以乘法原理。
于是左右两边再找最小值，注意这里的最小值是区间内的相对大小，至于区间内具体取了什么数是不知道的，所以这里要组合数算一下。
如果暴力找最小值的话，极端情况下会劣化到 $O(n^2)$。考虑优化。
优化的时候想瓶颈在哪，这里的问题在于，如果最小值靠后，那就要扫很长一段距离。于是我们从左右开始扫，双指针。
实际上这个时间复杂度不好计算，考虑每个点最多被扫几次，把每一层的消耗记到小的那一边，算两次。一个点最多被记 $\log n$ 次，因为它被记过之后，所在的区间长度至少减半。所以时间复杂度 $O(n \log n)$。

VP CF 1101 Div.2

C

题意

$n$ 个人，$x$ 张桌子，每张桌子可以坐 $s$ 个人。

$n$ 个人按照排队的顺序入座，$I$ 人只会坐上空桌子，$E$ 人只会坐上非空桌子，$A$ 人都可以。

问最多容纳多少个人入座。

$n,x,s \le 2\times 10^5$

赛时思路

直觉告诉我要对 $A$ 人做延迟决策，和之前某个 C 题一样。这个延迟决策真的很常见欸，和反悔贪心有不解之缘啊。
遇到 $I$ 人就放到空桌子上，如果没有，那就不放。遇到 $E$ 人就放到非空桌子上，如果没有，那就不放。$A$ 人不放。
最后分类讨论：
1. 如果剩下 $I$ 人，说明没有空桌子。此时扫一遍，统计 $A$ 人个数，如果发现有 $E$ 人没放且桌子没满，那就用前面的 $A$ 人替换后面的 $I$ 人，就可以做到把 $E$ 人放进去。
感觉不行，太复杂了。换种思路。这里跳出分类讨论思维是对的。
没有新想法了。放弃了，用时 $24$ 分钟。
让我们来挑战 $n\le 3000$ 的 Eazy version。
我们充分发挥人类智慧，将这个问题转化为一个类括号序列问题。$I$ 人视作 $+s-1$，$E$ 人视作 $-1$，$A$ 人可以是 $+s-1$ 或 $-1$，那么问题的约束就转化为，任何时刻，$sum \ge 0$ 且至多选择 $x$ 个 $+s-1$。问最长括号子序列长度。然而不会做。
好像只要 A 后面有没有被 I 覆盖的 E，用它替换 I 就一定更优，没时间写代码了，就这样吧。

正确思路

延迟决策很对啊，首先考虑没有 $A$ 怎么做。遇到 $I$ 就开台，遇到 $E$ 就放进去。
考虑加入 $A$。$A$ 的作用是可以提前开台，如果开不了台，也可以不劣地替换 $E$。
如果 $A$ 能带来一个 $I$ 管不了的 $E$，那么令 $A$ 开台一定不劣。==这里我一开始其实想到了，但是被秒否了，下次对这种看起来很优很对的结论要多想一会儿啊。==因为这样做最坏的情况也只是没有新增其他点。
于是扫一遍，一开始把 $A$ 当 $E$，发现有 $E$ 放不下去了，就用一个 $A$ 从 $E$ 变 $I$。维护一个剩余空位数和台数。

D

题意

$n$ 层汉诺塔问题的变种，唯一区别是可移动的条件不同。移动 $i$ 层的条件是，上方有恰好 $a_i$ 层。

问能否通过 $2^n$ 以内次移动达成目的，不能则输出 No。

$n \le 20$。

赛时思路

考虑无解。首先如果 $a_i \ge i$ 则 $i$ 层不能移动，必然无解。
考虑到汉诺塔的第一步永远是把最底下那层移到第三根柱子上。我们做一个类似的递归。
需要把任意 $n-a_i-1$ 层移动到第二根柱子上，但是这样有可能无法移回去。

正确思路

这类问题，我们想想出一个显然解，再来优化。
定义 $f(n)$ 表示将从上到下的 $n$ 层移动到另一柱子上的步数，则有：$f(n)=2f(n-a_i-1)+1$，这一个一定是比汉诺塔公式的 $2^n-1$ 要小的。
所以无脑写就好了。

树论专题训练

CF685B

题意

给你一颗 $n$ 个节点的有根树，找出每个子树的重心。

$n \le 3 \times 10^5$。

正确解法

树的重心一定在从根开始的重链上。所以子树的重心一定在它的重儿子里，从重儿子的重心往上跳就好了。
每个点至多跳一次，因此时间复杂度 $O(n)$。

9.16

VP CF 1099 Div.2

C

题意

给你一个长度为 $n$ 的序列 $a$，可以将它的偶数除以 $2$，奇数 $+1$，问要使得数都相同的最小操作次数。

$n \le 10^5,a_i \le 10^9$

赛时思路

每个数至多进行 $\log V=30$ 次操作。实际上是 60 次，因为两次才能出来一个除以 2
每个数能达到的最大值就是 $x+1$，之后只会变小，所以最终序列的最大值是 $序列最小值+1$。
猜想：是不是一定是序列最小值或序列最小值 $+1$ 呢？并非吧。
好像不用那么复杂？对每个数操作 $\log V$ 次就好了，记录一下不同值需要的操作次数。
难绷之用 map 和 unordered_map 被卡了。
不会卡常啊，就这样吧。用时 $30$ 分钟。

订正

以后有想法之后，把它变成一个好写的形式，没想好就直接写肯定是不行的，不论什么水平的人都一样。
这题要剪枝还是很方便的，代码也可以写得很简单，下次多想一想怎么写代码。

D

题意

给你一个长度为 $n$ 的数组 $a$ 和 $c$，$c$ 是 $a$ 的前缀和数组 $b$ 的前缀最大值。

$a$ 是不完整的，只有 $s_i=1$ 的地方是正确的，其余部分未知。

现要根据 $c$ 数组还原 $a$，若不行则输出 NO.

$n \le 2\times 10^6$，$\vert a_i \vert \le 10^6$

赛时思路

唯一能着手的信息是 $c$ 数组：
1. 若 $c_i > c_{i-1}$，则说明 $b_i = c_i$ 且 $b_i$ 是前 $i$ 项里最大的那个。
2. 否则若 $c_i = c_{i-1}$，则说明 $b_i \le c_i$。
相当于现在得到了三种约束：
1. $a_i=x$
2. $a_1+a_2+…+a_i=x$
3. $a_1+a_2+…+a_i \le x$
然后约束 $3$ 其实可以直接简化成约束 $2$，这样好像就好做了。除了有约束的 $i$ 号位置以外全部填 $0$.
如果 $i$ 位置同时有约束 $1$ 和 $2$，那就可能发生冲突。

正确思路

$c$ 相当于给了某些位置的 $b$ 一些约束。注意到它实质上将整个序列分成了很多个块（块的结尾的前缀和是确定的，不同块之间不影响）。
我们按照块考虑。每一个块的位置分两类：
1. 中间：需要满足 $b_i \le c_i$
2. 块末：需要满足 $b_i=c_i$
然后考虑填数，因为这个区间的数受到上界约束，所以我们在块开头填一个极小值，就不用理会这个约束了。
现在的问题是块末的 $b_i$ 要等于 $c_i$，由于块末的 $a$ 有可能是确定的，所以不好弄；但如果不是确定的，那就很容易。主要到，如果块末 $a$ 是确定的，实际上 $b$ 也是确定，所以可以找到第一个不确定的位置。
总结一下，先从后往前扫一遍，如果 $b_i$ 确定，$a_i$ 确定，那么 $b_{i-1}$ 也确定。如果 $b_{i-1}$ 本身不确定，但现在确定了，判断一下是不是无解。注意 $b_0=0$。
然后构造 $b$，再差分得到 $a$。

VP CF Educational 190

C

题意

第 $i$ 种卡片有 $c_i$ 张，从中选出尽可能多的卡片围成一圈，要求不存在连续三张不同。

$n \le 2\times 10^5$

赛时思路

首先把所有数量 $> 2$ 的卡牌全部放上去，这样显然是合法的。再考虑如何放数量 $= 1$ 的卡牌。
数量等于 $1$ 的卡牌只能放在同色卡牌之间。如果只有一种同色卡牌，能多放 $\frac{n}{2}$ 个，否则每种同色卡牌多放 $\frac{n}{2}-1$ 个。
用时 $18$ 分钟。

D

题意

给你两个长度为 $n$ 的序列 $a$ 和 $b$，定义一个合法区间 $[l,r]$ 为，$1,2,3…x$ 在 $a[l…r]$ 和 $b[l…r]$ 出现的下标相同。

找出有多少个合法区间。

$n \le 5\times 10^5$

赛时思路

首先考虑如何判定合法区间，扫一遍就行。
钦定区间的左端点，发现右端点的合法性是单调的，考虑二分或者双指针。
发现很难判定。考虑转化一下判定的思路。
本质上需要找 $i$ 点后面第一个等于 $a_i+1$ 的数的下标，这个东西可以倍增处理。
倍增找到右端点就好了。时间复杂度 $O(n \log n)$。需要特殊处理右边第一个 $1$ 的位置。
赛后 $3$ 分钟过了。。。

更优秀的实现

发现问题可以拆成子问题。一段一段的，这样要考虑递推/DP。
这题用 DP 写很简单啦。

树论专题训练

知识积累

直径的求法

两次 dfs/bfs：适用于边权非负的情况
树形 dp：维护最长链和次长链

直径的性质（边权非负时才成立）

从任意点出发，能走到的最远距离必定是直径一端
多条直径至少交于一点，否则的话就可以连接两条直径的某两个端点，形成更长的链。
新增叶子，直径至多增加 $1$，并且新直径是原直径或者原直径某个端点与叶子形成的链。
两棵树用一条边连接，新直径的端点必然是原四个直径端点其二。
多条直径的中点重合**（边权为正的前提下）**。

消防

题意

给你一个 $n$ 个节点的树，边有边权，要求找一条边权和 $\le s$ 的路径，使得其他点到这条路径的权值和最大值最小。

$n \le 3\times 10^5$。

原始思路

考虑在选择路径确定的情况下，怎样找到最大值。
显然只有叶子节点会贡献最大值。对于路径上的每一个点，找到与之对应的叶子节点，算一下距离就可以了。判定时间复杂度 $O(n)$。
于是我们得到一个 $O(n^3)$ 的做法。

正确思路

如果把路径视作一个点，那么与之最远的那个点，一定是直径的端点。这启示我们，这题或许与直径有关系。
猜想：路径一定在直径上
1. 若路径与直径无交，调整到有交的状态一定不劣。因为直径端点一定会更新它的最大值（否则的话就会存在一条新的直径），所以路径一定与直径有交。
2. 若路径与直径有交但不是完全覆盖，调整到完全覆盖的状态一定不劣。因为此时能成为最大值的来源只有两个：
  1. 直径端点到路径的权值和。
  2. 外部的点走到路径与直径交的部分（如果是不交的部分更新了最大值，就能构造出新的直径）。
3. 将路径完全放在直径上，第一个来源的最大值显然减少，第二个来源的最大值也单调不增，因此路径在直径上。
然后把直径拉出来，对于上面的每一个点跑一个 dfs 求出以它为源点的最远距离（直径上的点除外），把这个最远距离打在点上。这样的时间复杂度是 $O(n)$ 的，因为每个点只会被遍历一次。
然后对于一个固定的左端点，右端点越大越好，所以双指针。如何计算一段路径的价值呢？首先，路径上的点取点权最大值，然后左右两边未覆盖部分要加入路径距离长度，这个可以预处理。具体的，令 $s_i$ 表示直径上 $1$ 号点到 $i$ 号点的路径长度，那么预处理数组 $pre_i=\max(pre_{i-1}+w_{i-1,i},v_{i})$，最终答案就是 $\max(v[i…j],pre_i,suf_j)$。

Civilization

题意

给出一个由 n 个点，m 条边组成的森林，有 q 组询问。

两种询问：

查询 $x$ 所在树的直径
合并 $x$，$y$ 两颗树，使得新树的直径最小

$n,q \le 3\times10^5$

原始思路

这个很像启发式合并啊。枚举小树的所有点，新树的直径就是 $\max(d1,d2,u$ 出发最远距离 $+v$ 出发最远距离 $+1)$。
要维护每个点能到达的最远距离。不是很好维护的样子。

正确思路

根据直径的性质，新树的直径必然是原四个直径端点其二。我们想让直径最短，所以加边的端点一定在直径的中点上。其实想到了，又被秒否了。
新直径的长度就是 $\max(d1,d2,\lceil\frac{d1}{2}\rceil+\lceil\frac{d2}{2}\rceil+1)$，不需要维护具体直径，维护长度就好了。
维护一个带权并查集就好了。

9.17

VP CF 1098 Div.2

C

题意

给你一个非负整数 $a$ 和一个长度为 $n$ 的严格递增数字序列 $d$。构造一个数 $b$，它的每一位来自 $d$，求 $\vert a-b\vert$。

$a \le 10^{17}$, $0 \le d_1<d_2<…<d_i \le 9$

赛时思路

$b$ 要么比 $a$ 多一位，要么位数相等，要么少一位。少一位的情况构造最大值，多一位的情况构造最小值，位数相等的情况是难点。
位数相等时要求尽可能接近，也就是每一位尽可能相同。遇到一位不可能做到相同时，两种情况：
1. 填较大的数：此时 $b$ 一定大于 $a$，所以后面的数尽可能小
2. 填较小的数：此时 $b$ 一定小于 $a$，所以后面的数尽可能大
具体细节是用两个函数，$f(n)$ 表示 $n$ 位的最大值，$g(n,0/1)$ 表示 $n$ 位的最小值，含不含前导 $0$。对 $4$ 个 $b$ 取最接近的就好了。
代码调了半年。发现每一位上都可以填较大/较小/相等。
麻了，不调了，用时 $60$ 分钟。

订正

细节问题，没讨论充分。。

D

题意

平面上有 $n$ 个点，用一条竖线和横线将平面分成 $4$ 块，每块至少一个点，问有多少种不同的分法（只要块内点不同就是不同分法）。

$1 \le x,y \le n \le 2\times10^6$

赛时思路

这种题是叫扫描线吧。给 $x$，$y$ 离散化，然后从左到右用一条竖线扫过去，把左右切成两半，找到 $[\min(\max l_y,\max r_y),\max(\min l_y,\min r_y)]$ 这个区间内有多少种 $y$，答案加上 $cnt-1$。
具体细节是，先离散化，然后按 $x$ 排序，找前后缀 $y$ 最大/最小值。然后二分找个数。时间复杂度 $O(n\log n)$，是二分和排序的 $\log$，常数很小应该能过。
用时 $55$ 分钟，被一个代码细节硬控了好久。。
不是，又被卡常了😡。

树论专题

Propagating tree

题意

给你一课 $n$ 个节点的有根树，点有点权。$q$ 次操作。每次操作要么询问 $u$ 点点权，要么给 $u$ 增加 $x$，给 $u$ 的子节点增加 $-x$，给孙子节点增加 $x$…

$n,q \le 2\times10^5$

思考

这种父节点对子树的影响，如果从父节点视角来考虑的话通常比较困难，从子树节点看影响会比较简单。
对于节点 $u$，维护根到 $u$ 的路径上的标记和，分奇偶存储就可以做了。
具体地，令 $f_i$ 表示，$i$ 到 $1$ 这条路径上层数为偶数的点的标记和是多少。每一个增加操作，判断它的深度是奇数还是偶数，令对应子树的 dfs 序增加就好了。区间加单点查，用树状数组维护差分即可。

Blood Cousins

题意

$n$ 个节点的有根树，如果存在一个人 z ，是两个人 a 和 b 共同的 p 级祖先，那么称 a 和 b 为 p 级表亲。

处理 $q$ 个询问，求编号为 $u$ 的人有多少个 $p$ 级表亲。

$n,m \le 10^5$

思考

令 $u$ 所处深度为 $d$，这个询问本质上是在问，$u$ 的 $p$ 级祖先的子树内，有多少个深度为 $d$ 的点。
所以我们就把节点按层数分类（本质剔除无用元素），并按照 dfs 序排序。找到 $u$ 的 $p$ 级祖先后，在 $d$ 层二分一下找到范围就可以了。
至于怎么找到 $p$ 级祖先，直接倍增跳就好了。

松鼠的新家

树上差分模板题。

运输计划

旧题重做。

题意

给你一个 $n$ 个节点的树，边有边权。$m$ 条路径，可以将某条边边权清 $0$，问路径边权和最大值最小是多少。

$n,m \le 3\times10^5$，$w \le 1000$

思考

数据范围和题目要求都提示二分答案，那我们就套一个二分答案上去。
找到所有超限的路径，分类讨论，如果它们没有交集，无解；否则找到最大的那条边，将它清 $0$，看超限最大的那条路径有没有达到要求。
预处理路径端点 LCA，二分答案边权和，总时间复杂度 $O(m \log n+(m+n)\log V)$

紧急集合 / 聚会

旧题重做。

题意

$n$ 个点的树，$q$ 个询问。每次询问给出 $a,b,c$，求一个 $p$ 点，使得 $dis(a,p)+dis(b,p)+dis(c,p)$ 最小。

$n,q \le 5\times10^5$

思考

如果是两个点的情况，令距离最小的 $p$ 显然是 $lca(a,b)$。
猜想：三个点的情况，距离最小的 $p$ 是不是两两点之间的 $lca$ 呢？
使用调整法证明（想当年我还不会证这个）：假设存在一个点 $p$，他不是 $lca(a,b),lca(b,c),lca(a,c)$，那么，将它往其中一个 $lca$ 方向移动，距离变化量一定可以等于 $-1$（往两个点的 $lca$ 移动，离这两个点更近了，离第三个点更远了）。
于是三个 $lca$ 都试一下，时间复杂度 $O(m \log n)$。

严格次小生成树

$n \le 10^5$，$m \le 3\times10^5$

思考

首先生成一课 MST，然后考虑用边替换。
考虑每一条未使用的边，将它加入 MST 中，会形成一个环。令这条边替换掉环上边权第一个 $<$ 它的那条边就好了。
实际上不用真的替换，只需要找到这课树上，两个节点之间路径的最大值和次大值就可以了。
用 kruskal 的话时间复杂度 $O(m \log m+m \log n)$。

9.18

VP CF 1121 Div.2

B

题意

从长度为 $n$ 的序列 $a$ 中选择一个长度为 $m$ 的子序列 $b$，$b$ 的价值定义为：$\sum \limits_{i=1}^m i\times(b_i-b_{i-1})$。

求最大价值。

$1 \le m \le n \le 2\times 10^5$

赛时思路

这种最优化+子序列选择问题，让人想到 dp。但这题 dp 的话复杂度爆炸，于是考虑贪心。
越靠后的 $b$ 的权重越大，把贡献拆开来得到：$\sum\limits_{i=1}^{m-1} (i\times b_i-(i+1)\times b_i)+b_m=m\times b_m-\sum\limits_{i=1}^{m-1} b_i$。
也就是要选 $m-1$ 个小的数和一个大的数，枚举每个数作为大数的情况就好了，问题是怎么维护前 $m-1$ 小的和？
不会做啊，用时 $28$ 分钟。

订正

这种东西可以用 multiset 维护一个集合，插入它之后删掉末尾最大元素。
这个维护集合的技巧挺常见的吧，积累一下吧。

C

题意

给你 $n$ 个点的点权 $a_i$，两两不同。要用这 $n$ 个点组成一颗有根树，要求满足堆结构。每一棵树的价值定义为：$\sum\limits {i=1}^n(a{p_i}-a_i)$，求所有合法树的价值总和。

$n \le 2\times 10^5$

赛时思路

$a$ 最大的那个点显然作为根节点，次大的点只能作为根节点的子节点，次次大的可以作为次大的子节点，或者最大的子节点。
给 $a$ 排个序，我们考虑每一个点的贡献是多少。记 $cnt_{u,v}$ 为 $v$ 以 $u$ 作为父节点能构成的合法的树的个数，则 $v$ 贡献：$\sum \limits_{u=1}^{v-1}cnt_{u,v}\times(a_u-a_v)$。然后发现不管 $v$ 挂在哪个节点下面，$cnt$ 都是不变的，所以 $cnt$ 只和 $v$ 有关，把它提出来就有：$cnt_v \times \sum \limits_{u=1}^{v-1}(a_u-a_v)=cnt_v \times ((\sum \limits_{u=1}^{v-1}a_u)-(v-1)\times a_v))$
发现这个 $cnt$ 其实挺好计算的，$cnt_v=v\times(v+1)\times…\times (n-1)$。于是这题就结束了。
排序。处理一下单个数的逆元，维护一个 sum 和 cnt 就可以做了。时间复杂度 $O(n \log n)$。
写的时候发现前面推错了，好在不是什么大问题，就是忘记乘上前面几个点能组成的方案数了。
用时 $40$ 分钟。

D

题意

要求构造一个长度为 $n$ 的 $01$ 串 $s$，并且 $s$ 中 $1$ 的个数不超过 $3$。定义 $f(t)$ 为，$t$ 有多少个子串能被 $3$ 整除（全 $0$ 也算）。

要求构造的 $s$ 是长度为 $n$ 的 $01$ 串中 $f(t)$ 最小的。

$n \le 2\times10^5$。

赛时思路

先来考虑对于一个 $01$ 串 $s$ 如何求 $f(s)$。
能被 $3$ 整除这个约束可以转化到十进制的数位和里，其实也可以转化到 $2$ 进制的数位和里。因为 $x \bmod 3 = (2^i+2^{i-1}…+1)\bmod 3=(2^i\bmod 3+2^{i-1}\bmod 3+…1 \bmod 3) \bmod 3 = (1+2…+1)\bmod 3$，想让这个式子等于 $0$，说明不存在孤立的 $1$，即一定是 $11001111000…$ 这样的形式的。想错了。
猜测令 $f(s)$ 最小的 $s$ 一定长成：$01010101…$ 这样的，因为这样都是孤立的 $1$。啊突然发现不对啊，令上式等于 $0$，说明贡献 $1$ 的个数加上贡献 $2$ 的个数乘 $2$ 是 $3$ 的倍数。这可怎么找到最小值。

订正

直觉先于机械。当你感觉机械的方法不能带来启示的时候果断转换啊，我就是掉这个坑里了。
这里求一个普遍的 $f(s)$ 不能带来启示，那就考虑对于题目的约束，$f(s)$ 最小取值。
直接用一个 $O(n^5)$ 的暴力打表，然后发现规律就好了。

树论专题

知识积累

换根 LCA

通过讨论 $rt$，$u$，$v$ 的不同分布情况，得到结论：$lca(rt,u,v)$ 是 $lca(rt,u),lca(rt,v),lca(u,v)$ 里深度最深的那个节点。

区间 LCA

lca 和 dfs 序其实有很大关系（这里的 dfs 序指的是每个点都会出现两次的那种）。

点 $u$，$v$ 一定是处于以 $lca(u,v)$ 为根的一棵子树上的。所以求两点 lca，实际上就是在 dfs 序上找一个最小的包裹两点的区间。求区间 lca 也是一样的，本质在 dfs 序上找到第一个完全包裹区间所有点的区间。

所以我们只需要找到这堆区间里 dfs 序最大最小的两个点，对它们两个求 lca 就好了。

货车运输

旧题重做。瓶颈路要联想最小生成树。

9.20

VP CF 1120 Div.2

B

题意

构造一个 $n\times n$ 的网格，用 $1$ 到 $n^2$ 的排列填充，要求每行每列最小值中不同的数有 $k$ 个。

$n\le 1000,k \le 2n$

赛时思路

构造题考虑上界。不同的最值最多有多少个呢？通过按照 $1,2,3…n^2$ 的顺序填，可以填出 $2n-1$ 个不同的最值。可以证明这是上界，因为 $1$ 本身要占据一行一列，最多又只有 $2n$ 个。
构造题考虑下界。不同的最值最少有多少个呢？通过将最小的 $n$ 个填入对角线，可以填出 $n$ 个不同最值，可以证明这是下界。因为每一行都至少贡献 $1$ 个，所以最少贡献 $n$ 个最值。
所以 $k$ 的合法取值范围是 $n \le k < 2n$。
尝试从下界出发调整至 $k$。好像没想到什么好的方案啊。。
尝试从上界出发调整至 $k$。这个好做啊。第一行的向下移动就能使个数 $-1$，交换 $a_{1,j}$ 和 $a_{j,j}$ 就可以了。
用时 $22$ 分钟。

C1

题意

定义函数 $f(S,x)$ 表示：集合 $S$ 中的每个元素除以 $x$ 向下取值构成的集合的 mex。

给你一个序列 $a$，$a_i$ 表示 $f(S,i)=a_i$。要求根据 $a$ 构造出一个集合 $S$，$S$ 是 $[0,n-1]$ 的子集。

$a_i\le n\le 10^5$

赛时思路

先来考虑对于一个确定的集合 $S$，如何生成 $a$。对于一个 $x$，将集合按照 $kx$ 分类，找 mex 转化为找第一个没有元素的类别 $k$。
有了这个理解好像就能做这题了。现在的 $a_i$ 可以理解为：将集合 $S$ 按照 $i$ 分类后，$[0,a_i-1]$ 这些类别至少有一个元素，并且 $a_i$ 这个类别不能有元素。还是不可做啊？？
等等，这样想的话，相当于每个 $a_i$ ban 掉了一些集合的取值。具体的，$[a_i\times i,a_i\times i+i-1]$ 这个区间的数不能取。由于题目保证有解，除了这些区间内的数我全部取上，那一定是可以的啊。
用时 $26$ 分钟。

C2

题意

与 C1 的不同在于，需要计数有多少个满足条件的集合。

赛时思路

C1 的时候，我们忽略了 $[0,a_i-1]$ 一定要有至少一个元素的约束，现在把它补上。
我们现在把问题转化为了：$[0, n-1]$ 中，有一些区间的数不能取，有一些区间的数至少要取一个。问取的方案数。这个可以 $O(n\log n)$ 预处理出来。
如果没有不能取的约束，能做吗？
1. 如果区间没有重叠，那是好做的。
2. 区间有重叠部分怎么办呢？这其实是在问区间选点覆盖的方案数啊。感觉做不了啊。
  1. 如果一个区间被另一个区间包含，那么大的区间是没用的，可以删掉。
  2. 所以我们就得到了一堆相交的区间，问方案数。两个区间相交是好做的，三个区间呢？做不了~
应该是少了点性质？不会了啊。。。用时 $30$ 分钟。

正确思路

把问题转化之后，尝试用组合数学直接做，但是发现做不了，那就试试 dp 嘛。组合数学不行就换 dp，还是没有机械解题的意识啊。
定义 $f_i$ 表示，第 $i$ 元素取了，且前面所有区间都被满足的方案数。如果 $i$ 不能取显然 $f_i=0$，否则的话可以从 $[l_{mx},i-1]$ 处转移，前缀和累加就好了。
最终的答案要求 $i$ 覆盖 $[l_{mx},n]$ 这一段，同样前缀和。

补题

ABC476 F

题意

给你一个 $N\times N$ 的网格，定义 $f_{p,q} = \sum\limits_{i=1}^n\sum\limits_{j=1}^n (a_i\times b_j \bmod m) \times \max(\lvert i-p \rvert,\lvert j-q \rvert)$，每个点贡献 $f_{i,j}+(i-1)N+(j-1)$，问这个东西的异或和。

$n \le 1500$

正确思路

这题本质在求每个点的 $f_{i,j}$，求这个东西本质是在求二维网格上的带权切比雪夫距离和。
切比雪夫距离在二维网格上的几何理解是“一层一层的正方形”，这个结构很难去递推，或者快速计算。
于是我们就考虑将切比雪夫距离转化为曼哈顿距离。对这个技巧不够熟练吧
转化之后的距离可以表达为：$\lvert i-p \rvert+\lvert j-q \rvert$，让 $x$，$y$ 单独计算。
按 $x$ 排序，考虑 $x$：
$x$ 前面的数贡献 $sum_{id-1} \times v_{id}-s_{id-1}$，其中 $s_{id}=s_{id-1}+v_{i,j}\times i$。后面同理，前缀和做差。
然后交换 $x$，$y$ 次序再做一遍。

一些思考

这个转化在代数上是将 $\max$ 与求和的相互转化，在几何上是将其旋转了 $45°$ (相似比 $1:\sqrt{2}$)。

ABC475 E

题意

给你 $n$ 个长度为 $k$ 的 $01$ 串，处理 $q$ 个询问，要求支持单点修改 $01$ 串，单点查询 $01$ 串的排名。

$n,m \le 3\times10^4$，$k \le 200$，$q \le 5\times10^4$

正确思考

理解了这个查询的过程后，可以联想到 $01$ trie 吧。
然后就是建 trie，插入的时候维护个数，查询的时候它是第几名，如果这一位是 $0$，$rk$ 就加上 $1$ 的个数。
然后需要注意一下相等和 $n=m$ 的特殊情况。

树论专题

Omsk Metro (hard version)

题意

初始给你一棵树的根节点，权值为 $1$。节点的权值只能是 $1$ 或 $-1$。加点的同时还有询问操作。

+ v x 表示将一个编号为当前点总数的节点接到 $v$ 下面，权值为 $x$。
? u v k 表示询问 $u$ 到 $v$ 的唯一路径上，是否有一个子段的和等于 $k$。

$n,k \le 2\times 10^5$

思路

感觉先离线会简单一点。先把不联通弄掉，然后离线处理那些有路径的，但是不确定 $k$ 是不是对的点。
因为点的权值都是 $1$ 或 $-1$，所以能表达的子段和一定是连续的。这就是说，只需要找到这条路径上，能表达的最小和最大的子段和就好了。暴力 dfs 是 $O(n^2)$ 的。
这咋维护啊。

正确思路

想法对完了。有一点没注意到，题目保证了有路径，所以不需要上并查集判断连通性。
然后就是怎么维护最大最小子段和的问题了。直接维护肯定不行，子段和又不是什么可以差分的东西，我们借鉴线段树的思路，一个东西不好维护，就维护其他的东西，给他拼成需要的那个东西。
我们在这里需要维护路径信息，所以考虑路径之间的合并。现在已知两条路径，怎么得出它的最大子段和呢？
1. 最大后缀+最大前缀
2. 各自的最大子段和
3. 为了维护最大前/后缀，还需要一个路径和
然后就是像线段树一样做了，不过是倍增。

一些思考

第一次见到还能合并路径信息的。不能差分的信息可以通过倍增来维护，感觉很巧妙。

Dominant Indices

题意

$n$ 点有根树，对于点 $u \in [1,n]$，找出以 $u$ 为根的子树的每一层中，第一个达到最大值的那一层。

$n \le 10^6$

思路

对每个节点维护一个 $d$ 数组，$d_i$ 表示向下第 $i$ 层的节点个数。暴力算的话是 $O(n^2)$ 的。
感觉有很多层数都是没有用的？没啥道理感觉。
那么这个层数随着合并会不会有单调性呢？并不存在吧。没招了。

正确思路

首先要意识到这题可以 dsu on tree。暴力算的话 $O(n^2)$，但是我们在递归子树的时候，有一些信息其实是可以保留的，不需要重复遍历。
所以我们就保留重儿子的信息，而通过遍历去找到轻儿子的信息。
考虑如何计算时间复杂度。每个点被遍历之后，所处的子树大小都会翻倍，所以至多被遍历 $\log n$ 次。总时间复杂度 $O(n \log n)$。

一些思考

关于 dsu on tree 的一些识别技巧：

只具备查询操作
只和子树有关

dsu on tree 本质上是在利用已处理的信息来优化求解。

Lomsat gelral

题意

$n$ 点有根树，点有颜色。对于每一个 $u \in [1,n]$，找到它的子树中，出现次数最多的颜色的编号之和（点权和）。

$c_i \le n \le 10^5$

思考

无修改，子树查询，联想 dsu on tree。
朴素的解法是，遍历子树的每一个节点，维护每种颜色的出现次数、最大次数、编号之和。但是子树的信息是可以给父节点用的。
于是我们保留重儿子的信息，单独遍历轻儿子。时间复杂度 $O(n \log n)$。

Tree and Queries

题意

$n$ 点有根树，点有颜色。处理 $m$ 个询问，每一个询问需要找出 $u$ 的子树中，有多少种颜色的出现次数 $\ge$ $k$。

$n,m \le 10^5$

思考

无修改，子树查询，考虑 dsu on tree。
暴力的解法是，遍历子树的每一个节点，用权值树状数组维护出现次数 $= x$ 的颜色数量。
保留重子树信息。其他与上一题一样。时间复杂度 $O(n \log^2 n)$.

后记

这不用上树状数组啊，因为每次只会产生 $+1$ $-1$ 的变化，所以正常数组就可以了。