2026 年 1 月日祭

容斥、计数专题

Link

Hello 2026

Link

这场 ABC 做得过于不顺了。

D - Tree Coloring

考虑到一个 naive 的按照 mex 的构造，发现显然假了。为了在新的一层不产生新的颜色，考虑让每个点都继承它一个儿子的颜色，再循环移位一下，然后就做完了。实现上有一些细节，比如某些情况依然需要按照 mex 构造。
E - LCM is Legendary Counting Master

Solution。
F - Jumping Man

Solution。
G - Snake Instructions

牛牛题，考虑询问 L R LR 这题就变成了构造题。发现 L 答案的集合和 LR 的答案集合显然是一样的，因为 L 把能创飞的都创飞了，所以 L 中的蛇和 LR 中的蛇是一一对应的，并且可以求出这些蛇的速度。考虑剩下的蛇的速度，均可以通过 L 和 R 讨论出来。注意到无解当且仅当存在 010 或 020 的结构，构造出来过后再判断即可。

USACO 2026 JAN

金银铜都是唐，那我为啥不会金二。

话说我赛时发现了金二的经典结论但是以为是假的。

另外我甚至还做过金二的原。

春季测试 2023

D - 密码锁

是容易的，考虑。首先二分答案。固定全局最小值所在行数（设为 A 行），枚举全局最大值所在行数（设为 B 行），设剩下一行是 C 行。对于第列，枚举每种状态，判断 A、B 行是否合法，若合法则以颜色把 C 行列的数的数涂到数轴上。现在只需要判定数轴上是否存在满足中有每种颜色的点，随便维护一下即可。考虑，只是多了一行，变成了二维问题，即求是否存在满足以为左下角、长宽均为的矩形中有每种颜色的点。随便处理一下之后用线段树维护即可。

Codeforces Round 1073 (Div. 1)

Link

依然下分嘟嘟嘟。

B - Sub-RBS

充要条件是存在 )(...( 的结构，随便 DP 一下即可，赛时不知道为什么重构了好多次才写出来。

Codeforces Round 1075 (Div. 2)

Link

F - Zhora the Vacuum Cleaner

好奇怪的题。设表示在对某个点操作次后始终是空的，那么答案是显然的。考虑计算，若点自己为空且有不超过两棵子树非空，那么（始终为空）；否则，是任意一颗以为根的子树的带权大小的最小值。

数据结构专题

Link

A - ふたつのアンテナ (Two Antennas)

太牛了，没想到打个 tag 就可以达到删除的效果。显然离线下来做扫描线，用线段树维护一下区间最大值、最小值和最大答案，那么加点和删点就是单点更新，其中删点是把最大值设为极小值最小值设为极大值；新增一个点，相当于对于一个区间，用与最小值或最大值作差并更新最大答案，这也是可以维护的。时间复杂度。
B - middle

太牛了，原来中位数也能用技巧。考虑二分，把大于等于答案的设为，小于答案的设为，那么合法当且仅当总和。取的最大后缀、的全部与的最大前缀加起来即可。因为每个数都要一棵线段树，所以可持久化一下即可。
E - 城市建设

考虑 CDQ 分治，发现一个节点的左儿子对右儿子并没有贡献，而是儿子可以继承父亲的部分信息。称静态边为当前节点之外的已确定的边，动态边为当前节点修改的边。若一条静态边未出现在所有静态边的最小生成森林中，那么一定可以舍弃这条边；若强制选择尽可能多的动态边（将动态边的边权临时设为 ninf）但最小生成森林中依然存在一些静态边，那么这样的边是必选的，可以用并查集将这条边所连接的两个点合并起来。因为缩点后处理每个节点时的点数都是区间长度级别的，所以时间复杂度是。注意整个过程（包括并查集）需要支持撤销。
F - 第七学区

太牛了。显然有一个的暴力，可惜过不了。发现过程中我们维护了一个长度为值域为的数组，其中表示第位连续有几个。数组的本质其实是一个的 01 矩阵，考虑转置为的 01 矩阵，即维护一个长度为值域为的数组，发现对于新增的一个数，恰好可以维护。时间复杂度，只用跑 1s。
O - String Set Queries

太牛了。删除可以看成是添加了一个权值为的串。一个简单的在线做法是当前串长每达到就建一个自动机，时间复杂度，不太能过。考虑二进制分组，因为合并两个自动机的时间复杂度是线性的，一个串最多被合并次，一次查询只用在个自动机上查，所以时间复杂度是的。

Codeforces Round 1077 (Div. 1)

Link

Yeah 及时止损。

晚练

Link

No Change G (20260120)

随便状压 DP 一下即可。
Emiya 家今天的饭 (20260121)

随便容斥再 DP 一下即可。
逛公园 (20260122)

一个 naive 的想法是，对于判无解，跑两遍 dij，再找找零环，然而发现 DP 似乎很难写。DP 的设计和转移是显然的，但是转移顺序是困难的，那就搜索即可。
Grass Cownoisseur G (20260125)

不能逆向是容易的，所以缩点后枚举逆向哪条边即可。
消防 (20260126)

易证答案一定在直径上。双指针即可。
飞扬的小鸟 (20260128)

随便 DP 一下即可，细节比较多。