【记录】MX 11.10 ~ 11.16

· · 个人记录

11.10 ~ 11.17 集训记录

11.10 限时训练

T1

P10206 [JOI 2024 Final] 建设工程 2 / Construction Project 2 - 洛谷

考虑新的最短路一定是 s -> u + d + v -> t, 于是考虑正反两遍最短路，枚举每个点之后拼起来即可，要注意最开始就合法要单独计算。

T2

P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2 - 洛谷

考虑实际上是对于一段 b 的前缀和要 \geq a_i，于是线段树维护前缀和，每次变化后缀修改即可。

T3

P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 - 洛谷

发现对于配对的 i,j,他们之间最多拿上一张牌，否则 i 就会被扔掉，因此设 f_i 表示以 i 结尾，强制 i 配对的最大贡献，那么转移分为中间有没有牌，线段树维护一下即可。

实现上还有个小细节，对于区间取 \max，询问区间最大值，可以少维护一个 tag，递归修改为循环查询即可。

T4

P11726 [JOIG 2025] 最悪の記者 5 / Worst Reporter 5 - 洛谷

考虑倒着做，每次就是钦定两个位置相邻，直接维护 id_i 表示 i 位于时刻 m 的哪个点的位置，每次交换并连边，如果出现点度数 >2 即不合法，环也不合法，否则直接字典序最小输出链即可。

lca NOIP

T1

CF1844C Particles - 洛谷

考虑可以删掉一段长度为奇数的区间，于是分奇数偶数分别维护最优决策即可。

T2

P7967 [COCI 2021/2022 #2] Magneti - 洛谷

连续段 dp 好题，首先发现最后中间是一段区间，然后把空白位置插进去即可，于是考虑对长度为 k 的方案计数，如何做呢？

从小到大插入，设 f_{i,j,k} 表示插入了 i 个，分成 j 段，花费了 k 的空间，共有三种转移：

最终答案就是 \sum\limits_{i = 1}^n {l - i + n \choose n} \times f_{n,1,i}。

T3

比较简单，难点在于复杂度分析，树形 dp 维护子树内同色节点数量，注意树形 dp 转移上下界优化到平方即可。

11.11 模拟赛

T1

最开始以为是 ABC 的 F 题，容易想到一个贪心，维护一个 set，每次找到最大合法的删掉，但是会发现大样例 #1 就寄了，问题在于可能会取到一些过大的值，这些值可以作为后续新的段的起点。

如何解决呢？我们考虑二分答案，接下来问题在于如何 check，我们考虑先把每一组第 i 个元素全部填完，再填第 i + 1 个元素，这样类似一行一行填，当一个数在当前不能被匹配，则在所有当前可以接上的位置都无法匹配，由于我们是顺着填下来的，所以其他位置一定 < 当前位置，于是排完序直接枚举 1\sim n，不合法直接扔掉就行了，时间复杂度 O(n\log n)。

T2

考虑到了前面很多的性质，唯独没有发现最后的性质，考虑每次操作相当于向右压缩整个连续段，但是最终无法删掉连续段，最短也会留下 1 的长度，而我们可以在左边任意添加新的元素，因此只要对于任意位置均满足 X 的后缀连续段数量 \le Y 的后缀连续段数量即可，使用线段树维护，每次只会修改 O(1) 个位置。

维护最小的差值，可以转化为一个加一个减，维护区间最小值。

T3

考虑最优策略一定是打 \lceil \frac{suma}{x} \rceil 轮，最后会额外有一些，贪心的按照 b_i - a_i 从大到小依次填进去即可。

考虑如果 x 很大，我们可以不枚举 x，观察这个式子是类似整除分块的形式，我们可以按照整除分块，对每个块内同一计算答案，具体的维护出每个块合法 x 区间 [l,r]，找到和区间有交的 pre 统计答案即可。

T4

考虑图实际上是一个竞赛图，有一个比较好的性质是，从一个点出发能到达的所有点，均可以在同一条链上，于是问题转化为了从三元组 0 出发能到达的三元组数量，考虑 BFS 如何更新。

发现条件看似是一个三维偏序，实际上只需要满足其中两维，我们考虑分讨三种合法情况，以 A,B,C 为下标，另一个为值建立线段树，每次暴力找合法的点即可，每个点只会被删除 O(1) 次，因此总时间复杂度 O(n \log n)。

11.12 限时训练

P11453 [USACO24DEC] Deforestation S - 洛谷

考虑贪心如何做？按右端点排序，每次尽量在最右边种树，这样可以对后面区间贡献尽可能大，现在问题变成了维护区间内已经覆盖的点的数量，以及找到范围内最右端的点，分别使用树状数组和 set 维护，由于每棵树只会被种 O(1) 次，总复杂度 O(n \log n)，记得离散化一下，处理一下细节。

P10193 [USACO24FEB] Bessla Motors G - 洛谷

考虑从哪个 c 过来其实不重要，对于每个点我们只关心 k 个有用的点，因此可以直接在状态多加一维表示从哪个 c 转移过来，如果一个点已经被转移了 k 次那么这个点就没有用了，因为走前 k 个一定更优，用 map 维护即可。

P10282 [USACO24OPEN] Smaller Averages G - 洛谷

考虑 dp，O(n^4) 是好想的，方程如下 f_{i,j} = \sum\limits_{k = 1}^{i - 1} \sum\limits_{l=1}^{j-1} f_{k,l} \times [\frac{pre_i - pre_k}{i-k} \le \frac{pre_j-pre_l}{j-l}]

考虑如何优化，发现限制条件其实是 i,k 对和 j,l 对的限制，考虑枚举 i,l，另外两维可以双指针维护。

P10138 [USACO24JAN] Cowmpetency G - 洛谷

对每个位置维护状态 1,-1,0 表示是否可以作为前缀严格最大值，考虑一个限制 a,b 实际上是 [a + 1,b - 1] 这段区间一定不能作为前缀最大值，b 一定是前缀最大值。

然后设计 dp，设 f_{i,j} 表示前 i 个位置，前缀 \max 为 j，转移分 1,-1,0 分别转移，可以用前缀和优化。

发现一个连续段内是互相不影响的，于是考虑对每个连续段去做，于是就变成了 O(QC \log C)，其中 \log 是快速幂，具体 dp 方程比较好推，是在推不出来可以看题解，式子很详细。

P12029 [USACO25OPEN] Election Queries G - 洛谷

首先考虑 x,y 作为两个合法首领的充要条件是 c_x + c_y \geq mx，其中 c_i 表示选 i 的人数，mx 表示 \max c_i，要不然肯定要选 mx 这个。

于是可以想到对每种 x 去双指针找到 y，用 set 维护 c_i = k 的所有编号，取最大最小即可。

想一下，发现 c 最多只会有 \sqrt n 种，想要卡满就是每个人分别有 1,2,3,\dots 票，其实就是等差数列求和，所以是 \sqrt n 的，于是我们维护一下序列里当前有哪些 c_i，直接按上面的做，总时间复杂度 O(n\sqrt n)，可能要带个 set 的 \log ？应该不需要。

11.13 模拟赛

T1

Problems

首先考虑无解的情况，由于每种颜色刷子只有一个，因此考虑对于一种颜色，设他最前面出现的位置为 st_{c_i}，则若出现 st_{c_j} < st_{}c_i < j < i，则无解，也就是两个区间交但不包含，剩下的则直接维护出每种颜色区间 [l,r],直接从前往后染色即可。

T2

Problems

P4785 [BalticOI 2016] 交换 (Day2) - 洛谷

考虑设每次取出的三个位置为 A,B,C，考虑每次操作，一定让最小值放到 A 上，于是如果 \min = A，则不变，若 \min = B 则交换前两个，否则我们发现 A,B 我们不能确定如何分配，此时我们记忆化搜索下去，由于交换形成了类似完全二叉树的结构，因此复杂度有保证。

T3

Problems

考虑当确定 a,b，c 和 s 之间是成二次函数关系的，因此最优一定取到 \max 或 \min，枚举 b，可以得出 c，随后找到最优符合条件的 a 即可。

T4

Problems

P8996 [CEOI 2022] Abracadabra - 洛谷

考虑每次归并，实际上是形成了若干个有序连续段，这里有序指的是最开始的一个元素有序，连续段则为，从最开始的数，以它作为开头且最大值的极长区间，随后每次操作变成了拆开一个区间，由于最多 O(n) 个区间，每个区间只会被拆一次，因此可以直接维护，使用权值线段树维护每个段的长度，查询时线段树二分即可。

11.14 限时训练

T1

P9186 [USACO23OPEN] Milk Sum S - 洛谷

比较简单的一道题，首先考虑无修改，贪心去做肯定让效率高的多产几天，于是我们排序，每次修改找到原来的位置和新的位置，计算一下增量即可。

T2

P9527 [JOIST 2022] 洒水器 / Sprinkler - 洛谷

给定一棵树，对树上不超过 d 的点 \times k，单点询问。

首先考虑一个比较暴力的，每次跳父亲，对其子树能覆盖的范围区间乘，但是发现会重复，观察重复部分，发现每个父亲会覆盖向下 d 和 d-1 两层，每次跳父亲时 d 都要 -1，于是可以直接维护 tag，每次询问暴力跳父亲即可。

T3

P9981 [USACO23DEC] Minimum Longest Trip G - 洛谷

第一问拓扑是好做的，考虑第二问，实际上我们可以考虑整个过程，在每一步转移都是取字典序最小转移，因此我们每次只考虑 f_u = k 和 f_v = k - 1 的这些点即可，每次处理出排名，按照先边权，后排名的顺序取即可。

T4

P9525 [JOIST 2022] 团队竞技 / Team Contest - 洛谷

之前题单里的一道题，考虑从大到小取，如果一个人同时作为多个集合的最大值，则只能把他删掉，要不然不合法，贪心用堆维护即可。

P14507 缺零分治 mexdnc - 洛谷

Luogu NOIP 模拟 T1，起来比较晚，发现其实合法的一定是在最大能凑出来之内，首先特判掉一些边界情况，剩下的肯定贪心从大到小取比较优，这里还需要注意到 a_i 是假的，最多只有 n 的级别，然后二分答案就做完了。

【MX-S11】梦熊 NOIP 2025 模拟赛 3 & WAOI R7 & FeOI R6.5（同步赛） - 洛谷 | 计算机科学教育新生态

P14520 【MX-S11-T1】战争游戏 - 洛谷

性质题，首先如果最开始 suml > sumr 直接搞到最左边然后一直向右平推即可，否则看看能不能吃掉右边第一个，如果此时右边能吃回来则 l 必败，否则则是要比较两边的和，注意到只会攻占一个位置就做完了，前缀和维护一下。

P14521 【MX-S11-T2】加减乘除 - 洛谷

比较简单的题，看到性质 C，考虑实际上每个点的区间，维护一下从根到这个点的前缀和，对路径上限制取更紧的，然后就可以求出每个点合法限制区间，相当于是给定若干个区间，每次询问这个点在多少个区间内，差分一下就行，这里还写了树状数组的差分。

P14522 【MX-S11-T3】空之碎物 - 洛谷

哇，非常难的一道题！

其实是性质题，考虑当区间出现了超过 27 个数字，则一定可以取到 \max，于是先计算这些区间，具体的使用一个单调栈，然后考虑小区间如何计算，发现式子可以拆成 x \ominus (y \ominus (\dots))，此时只有 x 某一位只有一个 1 才能产生贡献，我们直接枚举区间一维，枚举 x,y，然后计算贡献即可。

具体计算，我们需要满足 x 和 y 按位与的结果这些位置是不合法的，同时对于区间内不存在的这些位置，只保留这些位置，然后计算贡献即可。

要注意当我们需要使用单调栈统计每个数作为最大值的区间，统计贡献时，需要注意钦定相等的贡献算在左边或右边，否则会算多或算少，这里可以在从前往后单调栈时使用 >，从后往前使用 \geq 即可。

11.15 ABC

掉大分了，E 是一个比较简单的线段树，考虑算一下贡献就做完了，G 貌似是多项式科技，据说要用 NTT，不会。

F 写了一个 IDA*，最后 TLE 了没卡过去，D 题怎么还是大模拟，这场输麻了。