2026 年 5 月日祭

树上处理技巧

Link1 Link2

A - Lomsat gelral

树上启发式合并板子。
B - 线段树合并 / [Vani 有约会] 雨天的尾巴

线段树合并板子。
C - 最悪の記者 4 (Worst Reporter 4) (Day4)

简单题，线段树合并板子，我咋调了半天。
D - 命运

简单题，线段树合并板子。感觉这两道题的技巧类似于 P5298，见过一道过后就很典了。
E - 重链剖分 / 树链剖分

树剖板子。
F - 语言

可以转化成个矩形求面积并。
G - 礼物

简单题，倍增或者树剖维护一下即可。
I - LCA

有趣的 trick。注意到的一种求法是，对于中的每个，将到的路径加一，再查询到的路径和。于是离线即可。

Codeforces Round 1097 (Div. 1)

Link

C - Zhily and Signpost

赛时写了个树剖 + 二分没卡过去。单做法是，设表示到路径上点的儿子数量的对取，那么若，则的出边只有一种可能，可以直接路径压缩。因为一条路径上不同的只有个，所以时间复杂度是。赛时观察到了这个性质，但没往这个方面思考。

ACM 20260509

Link

D - P16344 [科大国创杯初中组 2026] 构造题

最开始也是在想二进制构造，然后想了一会儿突然画出来一个斐波那契构造，然后发现是对的。
E - P10042 [CCPC 2023 北京市赛] 三染色

好题。发现在模意义下考虑是困难的，注意到对于数组使得且相邻两个位置的差的绝对值不超过一，与形成双射。于是通过可以证明合法的条件是不存在，那么第一问直接轮廓线 DP 即可。将第二问放到上考虑。对于一个确定的，答案是中的最小值到的曼哈顿距离的最小值。考虑 DP 状态需要记录哪些信息，发现除了轮廓还需要记录的最小值、曼哈顿距离的最小值、轮廓上一特定位置的值（以推出新位置的值），发现直接 DP 过不了，考虑优化。发现我们并不关心最小值具体的值，因此可以钦定最小值是；发现我们也并不关心最小值的位置而只关心其曼哈顿距离，而曼哈顿距离相等的点构成一个斜列，记录该斜列与当前列的交点即可，若无交点则无法更新。时间复杂度。
F - P10044 [CCPC 2023 北京市赛] 最小环

并非困难，如果有时间是有概率自己做出来的。发现没有入度或没有出度的点没用，又发现入度和出度均为一的点可以缩掉，那么剩下的点的度数都，有，解得，那么直接做即可。
G - P10040 [CCPC 2023 北京市赛] 替换

容易发现巨大时限，考虑用 bitset 模拟。发现需要切片操作，然而 STL 的 bitset 的切片是的，直接做变成了。发现手写 bitset 就可以让切片操作变成的，而，因此可以做到。好屎 /ll。
J - P7143 [THUPC 2021 初赛] 线段树

注意到这种题要么是推式子要么是矩乘加速要么是分治（不同的区间长度只有种），发现前两个都不行，于是考虑第三个。考虑如何将两侧的信息进行合并，发现只需要对每个区间记录、与的答案即可。
L - P7136 [THUPC 2021 初赛] 方格游戏

好屎 /ll。答案是「任意位置到任意位置的答案」-「障碍到任意位置的答案」+「障碍到障碍的答案」+「绕路的部分」，对于每部分大力推式子即可。

DP 专题

Link

A - Zero-One

好题。特判掉和的情况。容易写出贪心并手模出 hack，发现最终形态肯定是一段一段的，其中每一段最多被一对数包围，那么直接 DP 即可。做法是，对于前缀，要么与花费配对，要么与前面的一个位置各花费配对，做完了。
B - Balanced Problem

好难啊。首先由于原序列是生成的，所以有用的位置只有个，可以直接处理出来。钦定某个集合是答案，考虑求出最小的使得可以把这个集合全部变成，发现是积木大赛。于是考虑 DP，设表示考虑了并选了，当前最小的是的最大花费，树状数组优化一下即可。
C - Caterpillar on a Tree

简单贪心。
D - Ostap and Tree

设表示离最近的黑点到的距离，转为对序列计数。设表示，当前是否存在一个的邻居使得，大力转移即可。
E - Path Counting

把式子写出来，发现其中一部分可以 DP 预处理出来，做完了。
F - Region Separation

算出表示分成块是否可行就可以 DP 了。注意到，后面那一坨可以处理出来，做完了。
G - Flights for Regular Customers

欸我咋没想到多源 bfs /ll。只需要求出每个时刻的状态再多源 bfs 即可，前者可以 bitset 矩阵优化。
H - Preorder Test

简单题，二分再换根即可。
I - LCS Again

DP 套 DP 即可，另外还有个神秘做法。

NOIP 模拟赛 20260516

A

线段树分治板子，hyw。
B - P9870 [NOIP2023] 双序列拓展

好题。题意是，问能否从只经过走到。发现取到最小值时限制是最松的，并且当时有，否则有，后者一定无解；对于的最大值同理。于是判掉无解后，我们有了一个十字型的区域，可以对左上方与右下方分别处理，本质相同。对于左上方，找出当前的最小值与的最大值，若满足条件则可以缩小范围并继续递归，否则一定无解。做完了。
C

转成二进制数再差分，再随便做做即可。
D - P7710 [Ynoi2077] stdmxeypz

不是题。先转成区间问题并分块，对于整块的修改再根号分治，若小于阈值则直接拿桶存，否则枚举深度再区间修改（差分）即可。

Codeforces Round 1099 (Div. 2)

Link

嘟嘟嘟乱打的。

D - Maximum Prefix Sums

拿最后一个搞搞即可，我咋写了一车会导致 WA 的特判。
E - Graph Cutting

简单树上背包，赛时忘了这东西按照子树大小是的。
F - Quadratic Jumps

首先答案。答案是容易的，考虑答案，枚举第一步，需要判断答案。如果是那么是容易的，如果是，发现只需要找到最小的和最小的。做完了。

分治思想及其运用

Link1 Link2

A - 移球游戏

分治转化为即可，核心操作是将一个柱子中某种颜色的球全部放到顶部。
B - Pudding Monsters

分治即可，不如 P5979。
C - 四维偏序

CDQ 套 CDQ 板子。
E - 假定之夏加强版

差分一下再 CDQ 分治即可。
F - 二逼平衡树

树套树板子，虽然是想拿这个讲整体二分的。

ACM 20260523

Link

D - Perfect Life

Solution。
L - Larger or Smaller

Solution。

其他题有空再补。

Codeforces Round 1100 (Div. 1 + Div. 2)

Link

F - Load Unbalancing

好题啊。猜测最后一步是的最大值，并且加上后成为的最大值，那么只需要最大化原来的最小值，于是可以二分。发现此时往上加的限制是不重要的，因此可以状压。可以证明这样做是对的。

杂题

[CF1867E] Salyg1n and Array

好困难 /ll。先把整块询问了，接下来再询问和即可，不知道是怎么想到的。
[CF2108D] Needle in a Numstack

去年这题我咋没写出来 /ll。次求出，次来二分，再从二分到的位置开始询问次即可。
P15851 [NOISG 2026 Finals] 柠檬

随机看了看，好像也并非很难。对于 Sub 1，Alice 直接把后个给 Bob，由于，可以在后个中吃两个来表示答案。对于 Sub 2, 3，考虑选择柠檬后面的一些数，用它们的异或和来表示柠檬的编号。分讨一下可以想到：Alice 先把线性基中所有数的异或和作为传过去，Bob 的答案是与所有被吃掉的水果的编号的异或和；每收到一个非柠檬的水果，若它在线性基中，则吃掉它；收到柠檬时，若它可以被后面的数表示那就做完了，若不能则吃掉后面所有在线性基中的水果即可。。

晚练

Link

铁路旅行 2 (20260505)

简单题，倍增即可。我咋对着想了半天还因为挂了。/bangbangt
竞选 (20260506)

题面锅了，虽然疑似不影响做法，以及我赛时思路是对的。正难则反即可，需要拿一个并查集维护颜色相同的点，拿一个并查集维护点。因为要启发式合并所以是的。
宴会 (20260507)

简单题，咋又挂了 /ll。
单图 (20260508)

终于没挂了 /ll。发现需要满足不存在，但允许存在仅向对方连边，那么随便预处理一下即可。
计数问题 (20260511)

hyw。
划艇 (20260512)

诶我在干什么呢。显然需要离散化，然后一层层 DP 即可。
淋雨 (20260514)

发现是个三维偏序，又发现有个条件没用，于是是个二位偏序。我又在干什么呢。
Miny (20260517)

发现直接 DP 有后效性，于是不妨设表示钦定不被引爆的方案数，数据结构或分治优化即可。
训练路径 (20260518)

很困难吧。题意是保留一些非树边使的不存在偶环，最大化非树边的权值之和。设表示点被第条非树边覆盖的答案，需要用状压转移。
决算报告 (20260519)

简单题，随便 DP 一下即可。
Island (20260520)

咋是板子。
朋友 (20260521)

好题，操作一是加边，操作二是，操作三是，写个并查集应该能直接做，也可以直接 DP。
三目运算符 (20260524)

观察发现维护 110、001、101、010 的位置即可。