[整理]赛前训练

第一场

A 是简单题，注意到矩形形成的是一个单调的阶梯，我们只需要排序然后枚举计算即可。需要注意处理一下完全包含的情况，用二维数点即可。（找单调性）

B 见到树上路径，想到拆分成点到根的异或和。注意到每个点的异或和确定了，边权就都确定了（钦定 1 的异或和是 0），这样就和树的结构无关了，直接变成了给定一堆相同或不相同的条件，求方案数。显然不论是相同还是不相同，都相当于给出了一些点的限制，有这样关系的一个点集一定只有两种方式。还要注意使用扩展域并查集来判断矛盾。（拆树上路径）

C 简单的 DP 题，首先写出需要的状态：当前处理到第几个、每台机器剩多久。转移很好写。但是复杂度不对，注意到后两维有很多本质相同的状态，我们只关心差值，所以可以直接减少一维。（合并 DP 状态）

D 见字符串必散列。但是字符串太长了，我们可以倍增处理。（倍增计算大数据）

第二场

A 考虑实际上就是看哪两个前缀和更接近，可以排序后找相邻。另外还要注意处理相同的前缀和。（最接近的两数可以排序找）

B 二叉树计数，一眼 Catalan 数，打表可知数据范围内最多 19 项，可以递归求解。（Catalan 数）

C 考虑一个人说的话代表了什么，我们不能确定比他小和比他大的人具体怎么样，但我们可以确定某一个区间分数都是一样的。这样问题就转换成了取最多不交区间，可以 DP。（反向思考）

D 咕

第三场

A 直接排序处理即可，用一个堆。

B 注意到数据范围很小，直接 Floyd 预处理出每种变化的代价，然后枚举怎么变即可。（观察数据范围）

C 手模一下推出公式，发现可以写成矩阵乘法加速。然后排序也是一样的找规律，发现新的最大值一定是原来的最大值和次大值产生的，又发现系数是 Fibonacci 数列，也可以矩阵快速幂。（找规律）

D 注意到这个条件很苛刻，考虑什么样的数才能全胜：他必须是区间的最大公因数。显然区间的最大公因数如果在区间里，他一定是区间的最小值，这个值是很容易确定的。那么问题就转变成，求区间内某个值的出现次数，这是经典主席树应用。（找性质）

第四场

A 暴力搜索剪枝可过。（勇敢写爆搜）

B 题目非常复杂，考虑逐层剥开。我们发现每种宝石可以分开考虑，前提是需要记录每个人现在多少钱了。这样 DP 状态就有了。又因为总量不变，可以删去 C 的那一维，这样复杂度就比较小了。

C 考虑两层的和一维有什么区别：我们只需要枚举两头的状态即可。观察数据范围，猜测使用 \(n\log n\) 算法。于是可以倍增。（倍增在一维的应用）

D 题目很复杂，首先注意到确定了底面位置和长宽，就可以确定最大高度。但这个最大高度是跟底面范围内最浅处有关的，考虑如何快速求他。二维的情况不好玩，我们考虑如何把他降成一维问题。首先枚举一维的两个端点肯定是逃不过的，然后注意到这时另一维每个位置的最浅深度就确定了，所以相当于在一个凹凸不平的数列上找最大子矩形，可以用单调栈完成。（降维）

第五场

A 稍微推一下式子，然后矩阵优化。

B 路径相交问题一般与 LCA 有关。注意到一条路径选了之后，LCA 比他深的不受影响，LCA 比他浅的受到的影响是：一个子树毙掉了。所以为了减少影响，应该从深到浅选择路径，每次标记子树。（树上路径考虑 LCA）

C 没什么头绪，但是看 T 比较巨大，n m 又非常小，可以往矩阵猜测。当然矩阵优化需要先有转移方程，我们暂时想不出来，所以考虑减少性质。列出题目中的几个要求，发现集齐四种原料这个要求比较古怪，考虑如何杀掉。我们考虑直接不管他走会发生什么：我们会多统计上没买够的情况。那显然就是容斥了，由于只有四种，复杂度增加了常数级别。但是还有一个边长变化的问题需要解决，应当使用拆点的方式，对于点 \(i\)，单独建一条边 \(i\to i'\) 表示经过商店，这样就可以写出转移方程，然后矩阵优化了。（拆点）

D 比较复杂，先手玩一下。注意到有一些区间是不一样的：他们完整包含了另外某些区间，这导致他们加过去对结果不会有影响。于是按照有没有影响，可以把区间划分成“完整包含某些区间的”和“其他的”。注意到前者不是独立成一组，就是放到他完整包含的区间里，这样损失最小。比较麻烦的是后者，但是由于已经没有完整包含了，所以我们有强烈的冲动来排个序，此时就会发现，区间的左右端点都递增。然后需要用到一个贪心：一定要选连续的一段分组。这样就可以方便地写出 DP 方程，然后注意到方程里面有一项枚举的只跟枚举的下标有关，而且要求最大值，所以可以单调队列。（单调队列）

第六场

A 发现容量比较小，这启发我们从暴力的基础上优化：只要杯子满了，就跳过，可以用链表或并查集来实现。

B 烂题 C 撞题，不整理

D 考虑跑最短路的主要阻碍仍然是边权不固定，有可能需要先通过什么方式来确定每条边的长度。首先考虑特殊情况，如果我们一开始在 0 层，那么一定是每次飞之前先爬到对应高度，使得飞完恰好也在 0，这时没有多余的路程。这个方式可以启发初始高度不为 0 的。我们一定是尽量不爬，只在必须爬时爬一次。这样 Dijkstra 更新时就可以根据这个计算下一步的边权。由于跟当前高度有关，需要记录走最短路到每个点后的高度。

第七场

A 由于每行每列最多只有一个符合条件的，且这个数会增大，那么可以只记录这个数的大小和位置。

B 稳定的病毒很好判断，只要他是自己细胞最厉害的，就可以一直苟着。可行的病毒有些复杂，我们不能只看病毒或细胞了，需要结合起来考虑病毒 \(a_{i,j}\) 最后能否住进细胞 \(i\)。这种情况下，需要保证所有更能感染细胞 \(i\) 的病毒已经杀死了，靠什么呢？靠不如病毒 \(a_{i,j}\) 能感染细胞 \(i\) 的病毒，在其他地方杀死前者。所以可以维护一个能杀死的集合，用 bitset 加速。

C 树形 DP。利用了合并子树总复杂度平方的性质。

D 暴力枚举两个区间吃不消，我们考虑从什么角度能够减少枚举的数量。注意到有一些情况是绝对不会选到的：如果两个城邦都选了和小于一半的区间，那么直接全选那个更大的城邦即可。所以首先可以钦定 A 城邦必须超过一半。这里有一个小结论：这样的区间一定要经过某个点，这个点就是前缀和第一次超过一半的点，否则一定小于一半。这样我们就有了一个定点，考虑枚举 B 城邦，然后实时更新 A 中能扩展到的最远处。这样这道题已经可以做到 \(O(n^2)\) 了。
可不可以更快呢？考虑我们枚举 B 城邦的过程，如果已知右端点，能不能快速找到最佳左端点。假设我们已经知道了所有左端点的答案，考虑右端点右移带来的贡献。不妨只枚举在 A 中出现过的点，再不妨设他出现在那个定点左边。那么此时他会对一部分点产生影响：从后往前看，如果左端点对应的 A 中点更靠左，那么这个点的答案就要修改，否则他往后的点就不受影响。这是找靠前的第一个更大数问题，可以使用单调栈。然后怎么更新答案呢？注意到我们每次更新的是一个区间，最后要求全体最大值，那么可以使用线段树来维护每个左端点的答案。（考虑极限情况，单调栈的应用）

第八场

A 镜像字符串可以通过散列判断。对于后半部分的点，他们最多只镜像了一次，所以可以直接判断；对于前半部分的点，他们镜像一次之后仍然要判断，直到长度超过 n。由于镜像后长度增加，可以从后往前转移。

B 注意到一定有一条左上到右下的折线把网格分成了玉米田和豌豆田，而除了每个拐点处必须放水外，其他空地都有两种选择。那么可以对折线 DP，为了确定是否必须放，保存一个上一步的方向。

C 注意到一条边会导致这条路径上所有边坏了都能找他，所以树剖再维护一个区间取 min、单点查询的线段树即可。（考虑贡献）

D 申必期望题。首先注意到有一些点不动是最优的，对于一个点，我们可以枚举他两边这样的点，然后分别算概率乘价值，概率稍微推一下会发现是一个等差数列，所以 \(x\) 走到两边不动点 \(p\ q\) 的期望就是 \(f(p)\frac{q-x}{q-p}+f(q)\frac{x-p}{q-p}\)。但这样是 \(O(n^2)\) 的，考虑如何快速找到想要的不动点。再回去观察原来的式子，会发现他实际上是定比分点，我们只需要写出所有的 \((i,f(i))\)，那么期望值就是某两个点连线在当前点的纵坐标。所以直接单调队列维护上凸壳即可。（观察式子形状）

第九场

A 注意到对于同一个 j 答案有单调性，二分即可。

B 操作比较复杂，实际上就是给定 \(n\) 和 \(n_1=n\bmod a\)、\(n_2=n_1+b\)、\(n_3=n_2\bmod c\)，求可能的 \(abc\)，我们分层解决。对于最后一层，我们可以通过枚举因数来确定每种 \(n_2\) 可能对应的 \(c\)。对于倒数第二层，由于只有一个加操作，可以做一个前缀和。最后直接看有哪些 \(n_1\)，把他们的答案加起来。输出可以随便写写，不需要考虑复杂度的事。

C 首先注意到最终最大得分是固定的，我们希望在不改变这个得分的情况下字典序最大，那么每一步能出的牌就限制了一个上界，可以二分这个上界。那么怎么判断当前可以呢？我们需要一个能单点修改、整体查询答案的结构，由于得分跟数字大小有关，可以尝试权值线段树。如何求出答案呢？我们可以使用常见套路，即每次只算跨左右子树的贡献，由于左右值域不交，这很好算。（线段树算跨左右子树贡献）

D 首先二分答案，判断是否都能不超过一个值。但是接下来事情有点难办，由于总次数很少，可以枚举，但我们不知道每次该砍哪个。归根结底就是因为竹子有可能被砍没，我们不知道应该什么时候砍某个竹子才最优。如何规避这种特殊情况呢？我们可以时光倒流，这样就不需要考虑是否砍没了，因为此时砍操作变成了加，我们每次加一定会加一个完整的，就相当于让算法自己选择了最优的操作时间。而原来的限制就变成了，每天砍 \(a_i\)，可以有 \(k\) 次加 \(p\)，从某个固定高度开始，要求最终高度不能小于 \(h_i\)。（如果超过了就说明最终达不到二分的那个高度）这样我们就只需要看一下当前谁最需要加即可，用一个堆维护高度小于 \(h_i\) 的时间。（时光倒流）

第十场

A 观察一下总复杂度很小，可以用链表来维护需要删的。

B 考虑这个问题的弱化版即不相交区间。那个问题的策略是先按右端点正序，再按左端点倒序贪心。再搬到这个题，发现也是适用的，所以直接写一个线段树维护区间加减、查询最小值即可。

C 见到异或考虑 01-Trie。由于树上我们比较方便判断大于，所以原题条件先改成大于。思考插入一个数时如何判断是否大于 \(k\)，如果 \(k\) 当前位为 \(1\) 那么当前不能大于，要想有一线生机必须往反方向走达到相等；如果 \(k\) 当前位为 \(0\) 那么可以和反方向的所有点做出贡献，然后走正方向达到相等。

D 首先考虑一种机器时怎么做，我们肯定要优先放到完成时间最短的里面，所以可以用堆来实时维护这个信息。然后考虑两种机器怎么做，注意到两种机器其实是独立的，一个物品从第一种机器加工完就可以选一个第二种机器。那么什么时候最短呢，为了让所有物品的最大值最小，我们应该逆序匹配两个机器上的时间。