2025 贵阳代码源集训 复盘

专题

Day2 数据结构(1)

CF1474C

发现 \(x\) 是不增的，所以第一次选择一定要选择一个最大值，枚举剩下的数，同理，也是不断选择当前最大值，判断方案是否可行。

Day3 数据结构(2)

CF1208D

我们从后往前遍历数组 $s_i $可以使用一个树状数组维护当前存在的数的前缀和，每次二分查找得出当前的数，然后再树状数组中删除即可，时间复杂度是 \(\mathcal{O(n\log\log n)}\) 的，直接在树状数组上二分可以做到单 \(\log\)。

CF1690G

$ set $ 维护所有的火车头。发现每次火车减速只会影响其后面的火车段数。如果他的速度这一段成为了新的前缀最小值，那么就将在他之后的直到第一个速度小于等于它的火车头之间的火车头全部删掉。用 \(\text{set}\) 维护这些值即可。

CF1913D

记 \(f_i\) 为删除当前位的方案数，\(g_i\) 为保留当前位的方案数。设 \(j\) 为 \(i\) 前面第一小于它的元素，\(i\) 可以被 \(j\) 删除，同时也可能被 \(j\) 前面小于 \(j\) 的元素删除，所以 \(f_i\) 可以从 \(f_{j}\) 和 \(g_j\) 转移过来。

如果要保留 \(i\)，那么 \([j+1，i]\) 的元素可以被 \(i\) 删除，\(g_i\) 可以被这一段区间转移而来，这样的情况下， \(j\) 一定要被删除，所以 $g_i \gets f_j + \sum_{k = j+1}^{i} g_k $

求和可以用前缀和快速处理，而求 \(j\) 元素可以用单调队列维护。

CF2000H

转化一下题意，就是要求出最小的 \(l\) 满足 \([l，l+k-1]\) 这些的数不在集合 \(S\) 中存在。要支持插入和删除操作

值域不大，可以开一颗权值线段树，有数的权值为 \(-1\)，没数的权值为 \(1\)，维护最大子段和，每次在树上二分找到答案。

LGP7706

肯定可以想到线段树维护区间信息。发现照片的排列在线段树上可能为四种情况

ooo|， oo|o， o|oo ， |ooo

用线段树维护：最大的 \(a_i\)，最小的 \(b_j\)，\(j\) 在 \(i\) 左边最大的 \(a_i - b_j\)，\(j\) 在 \(i\) 右边的最大的 \(a_i - b_j\)，区间最大答案 \(\psi(x,y)\) 。区间合并时分讨维护即可。

CF1638E

发现有一个区间颜色更改的操作，可以使用线段树区间推平，也可以使用 ODT 维护。使用 ODT 比较简单，同时给每种元素打上标记用树状数组维护区间和， assign 操作给区间需要修改的区间加上 \(tag_x\) 并减去 \(tag_y\) （\(x\) 为原来的颜色，\(y\) 为新的颜色)。最后查询时查询颜色段的 tag 和树状数组加上的标记就是答案。

Day5 数据结构(3)

CF459D

记 \(g_i\) 为 \(a_i\) 在 \([i,n]\) 出现的的个数。

开一颗线段树，点 \([l,l]\) 代表当前合法区间内 \(g_l\) 的个数，每次查询直接查询出现个数小于于 \(f_i\) 的个数，即 $ [1,f_{i}-1]$ 的区间和，为了保证 $ j > i $， 第 \(i\) 次查询之前需要将 \(g_i\) 的个数 \(-1\)。

Day6 字符串

CF176B

发现如果一个 \(S\) 可以变为 \(T\) 那么，肯定只需要一次就可以完成变换，考虑 \(dp\)

记录 \(cnt\) 为原串中有多少个位置在移动之后可以变为 \(T\)。记 \(f_{i,0/1}\) 为当前变化 \(i\) 次，是否变换为 \(T\) 的方案数。

在第 \(i\) 次后要变换为 \(T\)，若上一次为原串那么就有 \(cnt - 1\) 个位置可以变为目标串，否则只有 \(cnt\) 个位置可以变为目标串。

在第 \(i\) 次后不要变换为 \(T\)，若上一次为原串那么就有 \(n - cnt\) 个位置可以变为其他串，否则有 \(n - cnt - 1\) 个位置可以变为其他串。

所以转移为

\[f_{i,1} \gets \min(f_{i-1,0} \times (cnt)，f_{i-1,1}\times (cnt - 1)) \]

\[f_{i,0} \gets \min(f_{i-1,0} \times (n - cnt - 1)，f_{i-1,1}\times (n - cnt)) \]

答案是 \(f_{k,1}\) 。

LGP4824

字符串哈希简单题。

考虑用栈维护，将字符一个一个加入栈中中，计算末尾的一段哈希值 \(f(l,r)\)，与目标串的哈希值尝试匹配，匹配成功就弹出 \([l, r]\) 的字符。注意使用栈时不要越界。

CF1721E

直接暴力拼接加 KMP 直接爆炸。

发现前一段 \(s\) 的前缀函数时不会变的，只用考虑新加入 \(t\) 的前缀函数的计算，预处理 next 之后直接用普通方法求\([ |s| + 1, |s + t| ]\) 前缀函数，但这样还是会 TLE，因为 KMP 每次跳 next 的时间复杂度时 \(\mathcal{O(n)}\) 的。

所以，记 $ lst(i, j) $ 第\(i\) 个前缀的串最长的 border 的下一位为 \(j\) 的位置。若 \(s_{i} = j\) 那么 \(lst(i,j) = i\) 否则为 \(lst(nxt_i,j)\) 。预处理 \(lst\) 并在 KMP 中更新。

每次 KMP 跳 next 时可以直接 \(\mathcal O(1)\) 处理。

CF898F

字符串哈希，但为了保证 \(a + b = c\)，底数 base 应为 10，发现加法最多进一位，所以枚举的串长只在 \(n/3\) 到 \(n / 2\) 之间，取出区间 check，需要 check 是否有前导零，哈希值是否相等。

PS：很多人被哈希卡了，但我用 998244353 单模数过了，很神秘。

LGP8131

考虑贪心地删除从左到右的回文串，先用 $$\text{Manacher}$$ 算出回文半径，从左到右扫一遍维护一个左右端点 $(l, r) $，如果回文串的左端点 \(\leq\) \(l\) 就能删掉，右边同理，能删就删，再从右到左删一遍，就得到答案了。

CF873F

后缀自动机板子题。建出后缀连接数之后直接在树上 DP，求出每种字串的出现次数，如果一个位置合法就直接计算入答案即可。难点在于会 SAM。

好像用后缀数组也可以做。

Day7 DP(1)

CF1207D

考虑 DP，记 \(dp_{i,j}\) 为当前为第 \(i\) 位，使用操作 \(j\) 的最小代价，一个格子有两种方法涂上颜色，要么自己花钱涂上，要么从别人那里转移过来。这种情况就是 \(dp_{i, j} = \min(dp_{i, a_i}, dp_{i - 1, 0} + 1,dp_{i - 1, 1},dp_{i - 1, 2})\)。除此之外，还有一种情况是前面的一些数向后匀了一位，此时 \(dp_{i,a_i - 1}\) 可以从第 \(i\) 位前面最后一个大于 \(0\) 的位置转移过来，因为如果隔着一个 0，前一个连续段的贡献是无法传过来的，此时的转移为 \(dp_{i,a_i- 1} \leftarrow\min(dp_{pre_i,0},dp_{pre_i, 1}, dp_{pre_i, 2}+1)\) 可以预处理 \(pre_i\) 数组，剩下正常 dp 即可。

CF1077F2

考虑 dp，记 \(dp_{i,j}\) 表示当前选择第 \(i\) 位，已经选择了 \(j\) 个数的最大价值，发现这是从一段区间的 dp 最大值转移而来，可以想到单调队列优化 。\(dp_{i,j} \leftarrow dp_{q_{head},j - 1} + a_i\) ，答案就是 \(\max_{i = n - k + 1}^{n} f_{i,x}\)。注意特判没有选择方案的情况。

Day9 DP(2)

Day10 DP(3)

CF1096D

记 \(dp_{i, 0/1/2/3}\) 表示当前在第 \(i\) 位，破坏掉所有hard 子串的代价最小值。转移如下：

\(dp_{i,0} \gets dp_{i-1,0} + w_i\)

\(dp_{i,1} \gets \min (dp_{i-1,1} + w_i, dp_{i-1,0})\)

其他同理。

答案为 $ min （dp_{n,0}, dp_{n,1}, dp_{n,2}, dp_{n,3})$

Day11 组合数学(1)

CF1236C

为了使二分查找可以在第 \(pos\) 位找到 \(x\)，二分过程中访问到的点必须满足和 \(x\) 的大小关系是符合条件的，即 \(pos\) 左边被访问到的位置应该小于 \(x\)，右边被访问到的位置应大于 \(x\)。可以记下这些点的个数，计算答案即可。

LGP9306

发现如果一个元素满足 \(p_i = q_i = n\) 那么后面的元素都不会产生贡献。此时，方案数为剩下 \(n - 1\) 个数的全排列。 即 \((n-1)!\)

否则，将 \(p_i = n\) 或者 \(q_i = n\) 的元素放在第一位，为了使贡献最小，那么 \(q_k \leq q_i\) 的元素 \(k\) 才会被放在 \(p_i = n\) 的元素 \(i\) 和 \(q_j = n\) 的元素 \(j\) 之间的位置，剩下的位置可以任意排列。此种情况的方案数为 \(A_{n-1}^{q_i - 1} + A_{n-1}^{p_i - 1}\)。

CF1696E

记 \(f(i,j)\) 为一个格子的操作数，一个格子 \((i,j)\) 会操作 \(f(i-1,j) + f(i, j-1)\) 次。发现这是杨辉三角的形式，所以格子 \((i,j)\) 的操作数就可以表示为 $C_{i+j}^{j} $ 。所以：

\[ans= \sum_{i=0}^{n}\sum_{j=0}^{a_i-1} C_{i+j}^{j} \]

发现

\[\sum_{j=0}^{a_i-1} C_{i+j}^{j} = \sum_{j=0}^{a_i-1} C_{i+j}^{i} \]

又因为 \(C_{i}^{j} + C_{i}^{j+1} = C_{i+1}^{j+1}\)

所以

\[\sum_{j=0}^{a_i-1} C_{i+j}^{j} = C_{i+a_i}^{i+1} \]

所以 \(\text{ans}\) 就可以 \(\mathcal{O(n)}\) 时间内求出了。

CF571A

正着想如何将 \(l\) 分割成 3 段时不简单的，然而正难则反，考虑有多少种方案是不合法的。

如果一个方案不合法那么 \(a,b,c\) 中一定存在一个满足两个之和小于第三个。枚举一个最长边，再枚举一个 \(x (x\leq l)\) 表示为最长边选择加上多少长度。此时不满足题意的方案就为将剩下的长度分配给其余两个木棒的方案数。总共的不合法方案求和即可。

方案总数为 $ {\sum_{i = 0}^{l} C_{i+1}^{2}} $ 。

总数减不合法数即可。

CF1929F

要求节点构成一个二叉搜索树，发现二叉搜索树的中序遍历是有序的。可以直接 \(dfs\)，得到一个序列，由 \(-1\) 和其他数组成，问题就转换为了在序列里面填数，使得序列保持有序，求填数的方案。要满足序列有序，其实可以看做在值域里面选择一些数，因为可以重复，所以使用插板法求得答案即可。

Day13 组合数学(2)

CF1795D

题目要求一组点（一个三角形）中只有顶点颜色不同的点之间连的边才能产生贡献，一个三角形中最多只有 2 个点会被选择，所以一定是最大的两条边会产生贡献，如果有边权有重复的话，需要分类讨论：

1. 如果最大边有 3 条，那贡献的方案数有 3 种。
2. 如果最大权有 2 条，那么贡献为 1 种方案
3. 如果次大边权有 2 条，那么贡献为 2 种方案

最后考虑上色的区别，首先，被我们选择的两条边的公共顶点（下文称为交点）一旦颜色确定，那么这个三角形的涂色方案一定确定了，剩下的两个点一定是都不同于交点的颜色，同时还要满足蓝色点的数量等于红色点的数量，这说明红色交点的个数一定等于蓝色交点的个数，所以就相当于在 \(n / 3\) 个交点中选择 \(n/6\) 个涂成蓝色，其余涂成红色。最终答案就是选边的方案乘上 $ {\dbinom{n/3 }{n/6} }$。

CF1207D

正着算不简单，考虑容斥，无序的方案数就等于总方案数减去第一项有序的方案数，减去第二项有序的方案数，加上第一项和第二项都有序的方案数。考虑如何计算这些方案数。

单项有序的方案数就是按这一项排序之后连续相同段的全排列方案数之积，两项相同的就是连续两项都相同的全排列方案数之积。总方案就是所有项的全排列，分别计算即可。

Day14 图论(1)

CF1255C

记录一下每个包含 \(i\) 的组 \(q\) ，发现只出现过一次的数字一定是开头或结尾，从其中任意一个开始模拟。寻找到没有访问过的点 ，一个一个向下跳。

P9650

长得非常最短路。从汇点开始向起点跑，这样计算封锁的道路是更加简单，发现在跑 dijkstra 的时候从优先队列种取出的点一定是距离当前最近的点，而从怪物的视角看，一定会先封锁这些道路，所以 \(u\) 被取出的前 \(d_u\) 次就是前 $ d_u $ 短的出边，怪物一定会封锁，去除这些影响，然后正常跑最短路即可。

P5839

考虑 dp。记 \(dp_{i}\) 为前 \(i\) 个数都已经合法的最小消耗天数；$g_{i,j} $ 为将 \([i - k + 1, i]\) 的数都改为 \(j\) 的最小天数。\(g_{i, j}\) 的第一维可以滚动掉。两两之间的最小消耗天数可以使用类 Floyd 的 dp 求出。

\(dp_{i} = \min_{j = 1}^{m} g_{i}\)，\(g_i = \min (g_j + dis_{a_i,j}，dp_{i- k} + \sum_{p = i - k}^{i} dis_{a_p,j})\)

Gym - 104857J

可以枚举路径的最大值，发现如果一条边 \((u, v, w)\) 要产生贡献，那么 \(1 \rightarrow u\) 和 \(v \rightarrow n\) 的路径上的最大值都要小于等于 \(w\)，先跑一遍 dijkstra 求出 $1 \rightarrow u $ 的路径最大边权最小的路径的最大边 \(d1_u\)，再跑一遍 dijkstra 求出 $n \rightarrow u $ 的路径最大边权最小的路径的最大边权 \(d2_u\)，最后枚举判断即可

P2934

从 \(1 \rightarrow u\) 的所有最短路构成了一颗树， 发现如果要是路径最短，那么只可能经过一条非最短路树的树边。设非树边边为 \((u, v,w)\)，则新的最短路长度就是 \(dep_u + dep_v + w - dep_x\) ，其每一个节点的 \(dep_x\) 是不会变的。所以最小值就是当 \(dep_u + dep_v + w\) 取到最小的时候取得。所以直接对边排序后遍历每一条边，考虑一条边可以对那些点产生贡献。对与一条边 \((u，v)\)，可能被这条边更新的点只有以 lca(u, v) 为根的子树中的所有点，每个点最优的方案选择第一次更新它的边作为替换，所以被更新的点删掉即可，这个操作可以用并查集维护，直接每次将点的祖先挂到树上的父亲即可，从 \(u,v\) 开始跳，跳到 lca(u, v)，跳的过程中的点更新最终的答案。

CF875C

如果 \(n\) 个字符串两两有序，那么这 \(n\) 个字符一定有序。所以考虑从前向后两两处理，两个字符串 \(s_{i - 1}\) 和 \(s_i\) 可以分以下几类进行讨论：

1. \(s_{i - 1}\) 为 \(s_i\) 的前缀。不用更改，一定可行。
2. \(s_{i}\) 为 \(s_{i - 1}\) 的前缀。一定不存在可行方案。
3. 设 \(j\) 为 \(s_{i - 1}\) 和 \(s_i\) 第一个不相同的位置，\(x\) 为 \(s_{i - 1, j}\)，\(y\) 为 \(s_{i, j}\)。
   1. \(x < y\)。此时 \(x' < y' < x < y\)，可以发现，若 \(x\) 为小写，则 \(y\) 一定为小写；若 \(y\) 为大写，则 \(x\) 一定为大写，转换一下形式就变成了：$ (x \rightarrow y) \wedge (\neg y \rightarrow \neg x)$。
   2. \(x > y\)。此时 $ y' < x' < y < x$，可以发现，只有当 \(x\) 为大写，\(y\) 为小写时才能成立。转换一下形式就变成了：\(\neg x \wedge y\)。

发现上述两个式子和 2-SAT 的形式十分类似，而且只用输出方案，不用最小化步数，考虑使用 2-SAT。但是发现第二个式子只有一个与条件，并没有或条件，并不满足 2-SAT 的形式，所以考虑将左右两边根据大小写转换的策略变形一下，变为：\((x \rightarrow \neg x) \wedge (\neg y \rightarrow y)\)，此时就可以建图跑 2-SAT 了。

P6062

发现一个格子可能被一行或一列的木板覆盖，这些需要的木板是可以被预处理出来的。问题便转换成了如何选一些木板使得每一个点都被木板覆盖，同时选择的木板要最少。这样，问题可以考虑转化为一个图论问题，将每一个泥地看成一条边，边连接的两个点就是两块木板，因为并不会有两块木板同时盖住 2 个点，所以这一张图是一个二分图，而选择一些木板就等于选择一些点覆盖所有的边，问题就等于求出最小点覆盖，而再二分图中，最小点覆盖等于最大匹配，所以只用跑二分图最大匹配即可，用匈牙利算法和网络流都可以。

Day15 图论(2)

CF1679D

发现要让最大值最小，考虑二分。直接二分答案，二分答案 \(x\)，每次 check 一下可不可能合法地走 \(k\) 步。具体的，我们可以将所有大于 \(x\) 的点删掉，剩下的连边，然后跑拓扑排序，如果存在强连通分量，那么一定存在几个点不存在拓扑序，此时一定合法，否则判断是否存在大于等于 \(k - 1\) 的路径就可以了。

CF1213F

题目中给出了若干大小关系，考虑建图解决，把每个位置 \(i\) 看作一个点，每次将 \(p_i\) 向 \(p_{i + 1}\) 连一条有向边。发现建图之后如果点 \(i\) 和点 \(j\) 在同一个连通分量中，那么 $s_i = s_j $，此时我们直接 tarjan 跑 SCC，然后缩点。此时图成为了一张 DAG，这张图也是满足连边条件的，即小的点向大的点连边，此时直接按照拓扑序将每个强连通分量赋值，因为 tarjan 跑完之后图天然有序，所以直接按编号遍历就可以了。

CF2000G

考虑倒着跑最短路，记 \(f_i\) 为从 \(i\) 出发到达 \(n\) 的最大出发时间，初始时 \(f_n = t_0\)，对于 \(u \rightarrow v (l_1, l_2)\) 分两种情况：

1. \(f_u \leq t_1 \vee f_u - l_1 \geq t_2\)，此时并不会受到电话的影响，所以直接坐公交车，\(f_v = f_u - l_1\)。
2. 否则会受到电话的影响，现在有两种选择，走路或者在节点处等待，直到电话结束后再坐公交离开。这两种情况的时间分别是 \(f_u - l_2\) 和 \(s - l_1\)，再其中取最大值即可。

不难发现 \(f\) 数组可以很简单地通过最长路模型来计算，每次通过一个点更新它的邻居。从 \(n\) 号点开始跑 dijkstra，得到 \(f\) 数组，答案就是 \(f_1\)，注意时刻只能是正的。

Day17 树上问题（1）

CF1336A

每一个点对答案的影响分为正的和负的，正的方面就是会增加节点深度个满意值，负面的就是会使自己的子树内所有的点全部失去一点满意值，点对答案产生的贡献就是两个值的和，每个点的贡献都可以独立地算出来，直接计算，然后按照贡献从大到小排序，然后取前 \(k\) 大即可。

P5536

有两种做法，首先发现贪心地选择，能先选最长的链一定优，最好的情况就是选择一条直径，然后以直径的中心为根节点算出每个点的深度和以它为根的子树的最大深度，记 \(f_u = maxdep_u - dep_u\) 就是这个点的贡献，每个点按照贡献排序，选择前 \(k\) 个点，这 \(k\) 个点一定有边相连。证明：如果一个点 \(u\) 在集合中，那么他的父亲 \(x\) 也一定在集合中，应为父亲节点的 $maxdep_x \geq maxdep_u $，且 \(dpe_x \leq dep_u\)，先选父亲一定优。这样做完之后，答案就是没有被选中的点中的最大的 \(f_u\)。

第二种做法比较简单，考虑反着做，选择 \(k\) 个城市成为核心城市等于选 \(n - k\) 个城市不为核心城市，最好的选法一定是从叶子节点开始反向一层一层选择城市作为非核心城市，答案就是最多选择的层数。

CF771C

考虑 DP，记 \(dp_{u, w}\) 为 \(u\) 节点为根的子树中距离 \(u\) 为 \(w\) 的点的答案，每个点都会从儿子和父亲两个部分转移而来，所以正着 dfs 一遍跑出儿子的贡献，再跑一遍算出父亲方向的贡献。转移如下：

\[\begin{cases} dp_{u,0} = \sum_{fa_v = u} dp_{v,k - 1} + siz_v \\dp_{u,i} = \sum_{fa_v = u} dp_{v, i - 1} \end{cases} \]

父亲方面同理，只是要减掉 \(u\) 节点本身的贡献。

因为所求的是有序对，所以答案为 $ \sum dp_{u,0}/{2}$

Day18 树上问题（2）

P8578

发现如果要使子树中的极差最小，同一子树内的节点的值一定是连续的。所以直接遍历一遍树，记录下 dfs 序，按顺序依次赋值为 \(1\rightarrow n\) 即可。

CF1244D

发现题目中只有 3 种颜色，其必须满足每一个长度为三的路径必须两两颜色不同，那么这样一来不可能有一个点的度超过三，这样另外三个点的颜色一定有两个是相同的。所以这个合法的图一定是一条链，这样我们只用给链头两个节点赋值就能推出所有的颜色，赋值链头的方案只有 6 种，直接暴力枚举加 dfs 求出最大值和方案。

模拟赛

7.22 模拟赛 1

A. LIS

赛时写出，但由于 \(memset()\) 了一个较大的数组，直接起飞了，挂了 \(60pts\)。

单调栈维护一个数之前第一个比他大的数，在这之前的所有数都一定会转移到它。

B. 碰瓷

如果 \(T\) 可以碰瓷 \(S\)，一定满足三个条件：

• \(T\) 为 \(S\) 的子序列
• \(S_0 = T_0\)
• \(T\) 开头的连续的数的个数 一定大于等于 \(S\) 开头的连续的数的个数。

在 \(S\) 中枚举所有的 \(S_l = T_0\)，找到最近的 \(r\) 满足\(S_{l, r}\) 包含所有的 \(T_i\), 可以二分的找距离最近的 \(T_{i + 1}\)，然后分讨前缀情况，记录答案即可。

D. 非负

发现一个区间，如果最大子段和等于总和且非负，则这个区间就合法，前缀和后缀都是非负的。然后删掉一个 \(-1\) 总和会 \(+1\)，但区间最大子段和不变，所以直接删掉 (最大子段和 - 总和) 个 \(-1\) 即可。

7.25 模拟赛 2

A. 子段乘积

• 枚举中间的分割点 \(i\) , 要最大化答案，如果前缀为正，则尽量最大化后缀，反之则最小化后缀。可以用线段树维护区间 \([l, i]\) 和 \([i + 1, n]\) 最大 / 最小子段和。

B. 玩偶

• 赛时没有特判不用扔玩偶就合法的情况，Subtask 1 的最后一个点挂了， 因为数据捆绑的特性，这题爆干净了，挂了 \(100pts\)，警钟长鸣。
• 对 \(c_i\) 开一个值域线段树，记录每一个当前可扔的损失为 \(c_i\) 的玩偶个数。枚举所有的最大的玩偶，计算成为最大值需要扔掉玩偶的个数，在线段树上二分玩偶个数，计算答案即可。

C. 无人机

赛时想贪心，假了。

• 发现无人机的飞行方案一定是先上升同时移动，到达一个节点后再下降然后移动，或者平飞 \(1\) 个距离，然后再下降同时移动，平飞两个距离一定是不优的。
• 记 \(f_i\) 为无人机从第一个点出发到达 \(i\) 号点所用的时间，\(g_i\) 为无人机从 \(n\) 号点出发到达 \(i\) 好点的时间。对于每一个点 \(u\), 它可能可以从任意一个相邻的点来到，所以对于所有\(u\) ，\(f_u = max(f_v + 1, a_v)\) ，\(g_i\) 同理。得到这两个式子之后，就可以跑 Dijkstra 了，每次用点 \(u\) 松弛它的邻居，算出所有的 \(f_i\) 和 \(g_i\)。
• 最后考虑答案的计算。遍历所有可以作为拐点的点和边，计算答案即可。

D. 交集

• 发现如果一个区间包含其他区间，这个区间一定会被单独分成组或者不考虑答案的贡献，这么做一定是不劣的，所以拿掉所有的包含区间之后，剩下的区间的 \(l, r\) 一定都递增的，如此一来，所有分组都是连续的若干个区间。可以 \(dp\)，记 \(dp_{i,j}\) 为以 \(i\) 区间为结尾，已经分了 \(j\) 组的最大答案。答案还要考虑长区间的贡献。

7.27 模拟赛 3

A. 和除或

• 发现两个数如果二进制位有一位都是一就有 2 的贡献否则就只有 1 的贡献。所以直接容斥，发现一的位置很少，直接开一个 \(\text{map}\) 记下所有组合的方案的数量，容斥计算答案。

B. 礼物

• 分类讨论就可以了，注意到最多只可能存在 2 个连续的超过 \(k\) 的连续段，然后就此分讨。注意有一种情况是连续段的长度是大于等于 \(2k - 1\) 的，这种情况一定不行，因为无论怎么切都会存在大于等于 \(k\) 的连续段，注意细节。

C. 连续段的价值

• 最小值最大，考虑二分，因为 \(k \leq 17\)，所以每次二分时的 check 使用状压 DP 处理。令 \(dp_s\) 为填入了集合 𝑠 中的字母后用到的最短前缀长度，预处理出 \(f_{i,j}\) 为在尽量填入 \(j\) 的情况下，在 \(i\) 之后最靠前的长度为 \(mid\) 的均为 \(j\) 的连续段，dp 的转移直接按照 \(f\) 取 \(\min\) 值即可。

7.30 模拟赛 4

A. 建筑升级

• 枚举所有的建筑都至少升至 \(x\) 级，在剩下的建筑中选择最优的 \(p\) \((p < n)\) 个建筑，加上他们的贡献，取最大值即可。

B. 快速蜗蜗变换

• 发现若 \(i \wedge j \geq k\)，那么，\(i，j\) 一定为 \(k + 2^{p_1} + 2^{P_2} + ... + 2^{p_m}\) 此时我们可以枚举 \(p\)，算出满足条件的最大的 \(a_i \times b_j\)。这里只用枚举 \(p\)，计算 \(k + 2^p\)，因为如果将 \(k\) 加上很多位 \(\text{1}\) 的情况会被比 \(k\) 之前先遍历到的比 \(k\) 大的情况更新到。
• 注意！此题要计算 \(a_i，b_j\) 的最大值、最小值，算答案时要将这些两两相乘才能考虑完所有的情况（\(a,b\) 可能全正全负。）

D. 运货

• 考虑一个 \(\mathcal{O(n^2)}\) 的 DP，记 $dp_{i,j} $ 为后 \(i\) 个物品，选择了 \(j\) 个物品的最小载重。分类讨论得：

  \[\begin{cases} dp_{i,j} = dp_{i+1,j} & w_i>dp_{i+1,j} \\dp_{i,j} = dp_{i+1,j-1}+w_i & w_i\leq dp_{i+1,j} \end{cases} \]

  这是一个 \(\mathcal{O(n^2)}\) 的，考虑优化 DP。首先发现这一维只和上一维有关，所以可以滚动数组。

  发现 \(dp_{j}\) 是有单调性的，换句话说要装的东西越多，车的载重越大。其实上面的转移方程就变成了将 \(dp\) 数组拆成小于等于 \(w_i\) 的一部分和另一部分，用小于等于 $ w_i $ 的部分转移 \(dp_i\)，然后插入新的点 $ dp_i $ 。发现这个事情十分平衡树，用一个平衡树维护 \(dp_i\)，在树上打标记，每次 split ，找到第一个小于等于 $ w_i $ 的值，修改区间的值，然后 merge 起来即可。

8.2 模拟赛 5

A. 器材整理

• 发现答案的范围很小，只有 \(\frac{sum}{k}\) 到 \(1000 \frac{sum}{n}\)，这个范围并不大，所以可以直接枚举每一个然后 check，每次 check 可以使用一个 set，每次取出最优的值，将 check 的时间复杂度将为 \(\mathcal{O(n\log n)}\)，总复杂度可以接受。

B. 简单题

• 确实简单。一段一段考虑，发现一段连续的问号分为以下几种情况：
  1. 长度为 \(1\) 同时左右两边的位置都是 \(1\)，这样的连续段对答案的贡献是 \(-2\)。
  2. 长度不为 \(1\) 同时左右两边的位置都是 \(1\)，这样连续段对答案的贡献是 \(0\)，其最后一个位置的贡献为 \(-2\)。
  3. 长度任意，同时左右两边的位置有一位 \(1\)，有一位 \(0\)，这样的连续段的贡献为 \(0\)。
  4. 长度为不为 \(1\)，同时左右两边位置都是 \(0\)，这样连续段对答案的贡献是 $ +2 $。
• 为了让答案最小，所以每次贪心地选择以上的连续段，按 1 - 4 的顺序排序，每次贪心地加上答案的贡献就可以了。

8.4 模拟赛 6

A. 宝石展览

• 可以把每一种宝石拆开来算，不难发现每种宝石的贡献为：

\[ \sum_{i = 1}^{n}\sum_{j = 1}^{a_i} v_{i}^{j} \times \dbinom{a_i}{j} \times \sum_{k = 1\wedge k \neq i}^{n}\sum_{p = 1}^{a_k} \dbinom{a_k}{p} \]

式子可以用二项式定理 \((a+b)^n = \sum_{k = 0}^{n} \dbinom{n}{k} a^{n - k}b^k\) 来进行化简，最终式子为：

\[ \sum_{i = 1}^{n} ({(v_i + 1)}^{a_i} - 1)\times \prod_{k = 1\wedge k \neq i}^{n} 2^{a_k} \]

预处理出来阶乘和逆元，枚举 \(i\)，快速幂计算答案即可。

B. 乘积

• ​ 如果一个序列 \((a_1, a_2,a_3…… a_{2m}) < n^m\)，那么一定有一序列 \((\frac{n}{a_1},\frac{n}{a_2},\frac{n}{a_3}……\frac{n}{a_4},\frac{n}{a_5}) > n^m\) 所以小于 \(n^m\) 和 大于 \(n^m\) 的序列是一一对应的，所以数量是一样的，所以只用计算总方案 $ cnt $ 、序列之积等于 \(n^m\) 的方案数 \(x\) 就可以算了，答案等于 \(\frac{cnt-x}{2}\)。序列之积等于 \(n^m\) 的方案数用 dp 计算就行了。

8.7 模拟赛 7

A. 最长上升子序列

• 发现如果数据随机，那么最长上升子序列的长度的最大期望是 \(\sqrt{n}\) 的，所以直接暴力做。考虑从后往前，每次将一个数删去会对答案有什么影响。先做一遍最长上升子序列，然后考虑每一个数，如果这个数在最长上升子序中，那么就再跑一遍最长上升子序列，否则，就直接继承上一次最长上升子序列的长度。由于最长上升子序列的长度不会太长，所以这么做的时间复杂度是 \(\mathcal{O(n\sqrt{n}\log n)}\) 的，可以接受。