本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-16 22:41:19
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
考虑可以删掉一段长度为奇数的区间，于是分奇数偶数分别维护最优决策即可。
T2
P7967 [COCI 2021/2022 #2] Magneti - 洛谷
连续段 dp 好题，首先发现最后中间是一段区间，然后把空白位置插进去即可，于是考虑对长度为 $k$ 的方案计数，如何做呢？
从小到大插入，设 $f_{i,j,k}$ 表示插入了 $i$ 个，分成 $j$ 段，花费了 $k$ 的空间，共有三种转移：
- 新开一段 $f_{i,j,k} = f_{i - 1,j - 1,k - 1}$
- 合并两段 $f_{i,j,k} = f_{i - 1,j + 1,k - 2 \times a_i + 1} \times C_{j + 1} ^ 2$
- 接在一段后 $f_{i,j,k} = f_{i - 1,j,k - a_i} \times j \times 2$
最终答案就是 $\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
首先考虑无解的情况，由于每种颜色刷子只有一个，因此考虑对于一种颜色，设他最前面出现的位置为 $st_{c_i}$，则若出现 $st_{c_j} < st_{}c_i < j < i$，则无解，也就是两个区间交但不包含，剩下的则直接维护出每种颜色区间 $[l,r]$,直接从前往后染色即可。
T2
P4785 [BalticOI 2016] 交换 (Day2) - 洛谷
考虑设每次取出的三个位置为 $A,B,C$，考虑每次操作，一定让最小值放到 $A$ 上，于是如果 $\min = A$，则不变，若 $\min = B$ 则交换前两个，否则我们发现 $A,B$ 我们不能确定如何分配，此时我们记忆化搜索下去，由于交换形成了类似完全二叉树的结构，因此复杂度有保证。
T3
考虑当确定 $a,b$，$c$ 和 $s$ 之间是成二次函数关系的，因此最优一定取到 $\max$ 或 $\min$，枚举 $b$，可以得出 $c$，随后找到最优符合条件的 a 即可。
T4
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 - 洛谷
之前题单里的一道题，考虑从大到小取，如果一个人同时作为多个集合的最大值，则只能把他删掉，要不然不合法，贪心用堆维护即可。
Luogu NOIP 模拟 T1，起来比较晚，发现其实合法的一定是在最大能凑出来之内，首先特判掉一些边界情况，剩下的肯定贪心从大到小取比较优，这里还需要注意到 $a_i$ 是假的，最多只有 $n$ 的级别，然后二分答案就做完了。
【MX-S11】梦熊 NOIP 2025 模拟赛 3 & WAOI R7 & FeOI R6.5（同步赛） - 洛谷 | 计算机科学教育新生态
性质题，首先如果最开始 $suml > sumr$ 直接搞到最左边然后一直向右平推即可，否则看看能不能吃掉右边第一个，如果此时右边能吃回来则 $l$ 必败，否则则是要比较两边的和，注意到只会攻占一个位置就做完了，前缀和维护一下。
比较简单的题，看到性质 $C$，考虑实际上每个点的区间，维护一下从根到这个点的前缀和，对路径上限制取更紧的，然后就可以求出每个点合法限制区间，相当于是给定若干个区间，每次询问这个点在多少个区间内，差分一下就行，这里还写了树状数组的差分。
哇，非常难的一道题！
其实是性质题，考虑当区间出现了超过 $27$ 个数字，则一定可以取到 $\max$，于是先计算这些区间，具体的使用一个单调栈，然后考虑小区间如何计算，发现式子可以拆成 $x \ominus (y \ominus (\dots))$，此时只有 $x$ 某一位只有一个 $1$ 才能产生贡献，我们直接枚举区间一维，枚举 $x,y$，然后计算贡献即可。
具体计算，我们需要满足 $x$ 和 $y$ 按位与的结果这些位置是不合法的，同时对于区间内不存在的这些位置，只保留这些位置，然后计算贡献即可。
要注意当我们需要使用单调栈统计每个数作为最大值的区间，统计贡献时，需要注意钦定相等的贡献算在左边或右边，否则会算多或算少，这里可以在从前往后单调栈时使用 $>$，从后往前使用 $\geq$ 即可。
11.15 ABC
掉大分了，E 是一个比较简单的线段树，考虑算一下贡献就做完了，G 貌似是多项式科技，据说要用 NTT，不会。
F 写了一个 IDA*，最后 TLE 了没卡过去，D 题怎么还是大模拟，这场输麻了。
鲁ICP备2025150228号