2026 年 3 月日祭

数据结构专题

Link

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

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

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

考虑查询，主席树 + 树上差分即可。考虑修改，类似于启发式合并，更新较小的一部分的信息即可。
D - The Classic Problem

拿主席树维护即可，屎。
E - 城市建设

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

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

难绷题。枚举的位置，钦定区间最大值在右侧（若在左侧，翻转后再做一遍即可），向右枚举右端点，可以根据最大值推出左端点，那么现在需要判断这个区间是不是一个排列，直接集合哈希即可。
J - Mass Change Queries

简单题，对每个值维护一棵线段树，再执行一个类似于线段树分裂与合并的过程即可。
K - ROT-Tree Rotations

简单题，线段树合并即可。
O - String Set Queries

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

联合省选 2026

D1T1 - 找寻者 / recollector

哎我好菜，这都没场切。upd. 过了。

设表示以点为链顶，链长为的期望，那么问题分为转移与统计答案两个部分。容易发现这两个部分都需要枚举的每个儿子，并把其他儿子的数组卷起来再算算系数。考虑实现，容易想到回退背包，因为回退和加入的复杂度是一样的，所以直接做就是的。赛时因为以为回退一次需要求个数的逆元，所以认为回退背包是的，于是没写。而事实上，回退一次只用求除数（多项式）最高次项的逆元；另外也有办法求出个数的逆元。总结还是我太菜了。
D1T2 - 摩卡串 / string

好神人的题，感觉题解看懂了又什么都没看懂。

考虑在末尾一个个添加字符，并维护字典序的子串数量，再通过 DP 转移还原构造。考虑如何统计增加一个字符新增的字典序的子串（在此处为后缀）数量，发现这样的串分为两类，第一类是的前缀，第二类的一个前缀是的前缀并且下一位为而的下一位为。发现对于第一类，它一定是的若干次 border，于是只用记录当前的 border 即可。设表示 border 为，第二类串有个，目前有个字典序的子串，是否已经匹配的最小串长。因为，所以这一维是的，转移是的，时间复杂度，空间上需要用 bitset 卡常。不会写。/kk
D2T1 - 排列游戏 / perm

简单题，要是放 CF 大概就 *1900 评个绿。

这东西容易想到两个入手的地方：一个是次询问求出第一项或最后一项，一个是次询问找出。我并不认为后面这个东西有前途，于是考虑前者。发现求出第一项与最后一项之后，会贪心地舍弃较大的一项并在被舍弃的一侧询问一个数，并且容易得出这个数的值或范围。反复如此即可，做完过后再对有范围限制的位置随便构造一下即可。不知道以找为突破口是怎么做的。

Educational Codeforces Round 188

Link

我在干什么呢，这么喜欢在 Edu 下分。

E - Sum of Digits (and Again)

赛时先在写爆搜，可惜没注意到有多测就寄了。发现第一个数之后都很小，所以枚举后面的数的数位和再判断一下即可。
F - Sum of Fractions

傻子题，容易想到最优策略，再拆拆贡献即可。它甚至还给你离线好了。
G - Grid Path

无聊题。看到数据范围容易想到矩阵加速递推，于是考虑 DP。首先容易写出 DP，转移可以通过前缀和与简单容斥做到。发现右式以及答案都只与和有关，那么只关注这个值，推推式子，发现它们之间已经可以转移，并且是线性的。容易算出转移矩阵，因为一位要放答案所以矩阵是的，时间复杂度，其中，模太慢了需要卡常，加次取模一次。

杂题

P12304 [ICPC 2022/2023 WF] 过桥

jmr 推荐的，后来才发现也是「洛谷 2025 年度试题推荐选集」中的题。

注意到可以把个人按照是否会从对岸返回分成两类，下文称作 A 和 B。发现具体的方案一定是让一些人过去，再让对岸最小的 A 回来，并且在对岸没有 A 时把最小的 A 都送过去，再顺带带一些 B。首先发现因为一次只能送个人过去，所以让对岸有个 A 显然是不值得的，完全可以用完了再送，因此对岸同时最多只有个 A。考虑我们送 A 过去的时候该怎么分配 B，发现此处应当贪心地选择最小的 B，且不必选够个人；而当我们只送 B 过去的时候，显然可以贪心地选择最大的个 B。将从小到大排序，容易发现当前在对岸的人恰好是一个区间和一个后缀（区间前面是 A 后面是和 A 一起过去的 B，后缀是一组一组过去的 B）。因为对岸的 A 最多只有个，所以左端点只有个取值；后缀是一组一组过去的，所以后缀只有个取值。因此状态数是的。转移就是前面讨论的两种情况，需要前缀优化。

晚练

Link

Budowa lotniska (20260302)

简单题，可是写挂了，怎么会是呢。
Przyciski (20260303)

并非困难，可是没写完，怎么会是呢。偶数解是直接找环；若没有环，那么一定是一个森林，在树上构造奇数解是容易的，做完了。
数列 (20260304)

简单题，随便 DP 一下即可。
斗地主 (20260305)

hyw 题，搜索 + 剪枝即可。
現代的な屋敷 (20260309)

建个图跑 dij 即可，因为没开 long long 而挂分。
摆渡车 (20260311)

简单题，容易发现时间其实是的，乱 DP 一下即可。
Cowmpetency G (20260312)

有趣题，分讨一下发现所有区间除了端点都不交，于是 DP 即可，需要前缀和优化。因为没处理相同的情况几乎挂完了。
Minimum Longest Trip G (20260313)

无脑做法是倍增哈希找出两个串第一个不同的位置并比较。确定性做法是仅保留在最长路转移时需要用的边于是图分为若干层，对于每一层一次求出 rank 即可。
Džumbus (20260315)

难点在于读懂题。树形 DP 即可。
赛道修建 (20260316)

哦我是唐，二分 + 贪心即可，赛时贪心部分错了。
幸运数字 (20260317)

hyw，嘟。

闲话

20260306

好久没写闲话了。

今天在浏览之前的日祭，看到了一段话。

原文

Link

我的信竞，在进步么？看起来好像是的。要是拿现在的我和一年前的我对比，那已足以倍杀。但……补过的题还是不会做，码量大一点的又不愿意写，一到晚自习就写不动了，于是写一会儿又开始划水。我倒有一个优点，就是一般不会去刷水题（除了入门赛）。但是，难一些的题……绿题效率低，蓝题想不全于是又看题解，紫题几乎无法独立完成。

最终做了的题似乎是白做。

……

终究还是人的问题。

当时或许是考 NOIP- 模拟赛不太顺利，于是有点不开心。不过 OI 水平本身就是缓慢增长的，当时是不是稍微有点急。不过顺便再吐槽一句我初二的训练。另外原来我在后来的日祭中提到过这一天啊。

另外感觉看之前的日祭好有趣啊，按日期记录也是有它的好处的。