2026 年 4 月日祭

数据结构专题 2

Link

专题名字有盒子，比赛 ID 的后两位是「我生日（MMDD）」模「我出生月份（MM）的平方」。

A - SUM and REPLACE

板板势能线段树。
B - 带修莫队 / [国家集训队] 数颜色 / 维护队列

不会带修莫队 /ll。把修改看成时间轴即可，于是变成了三维莫队。
C - 一个简单的询问

四维莫队即可。也可以差分一下变成二维。
D - 访问 Visits

哦我有点烫了。考虑到较大时跳的步数很少，于是可以暴力地跳，利用倍增或长剖；当较小时则可以树上差分，找到 lca 过后只用调整次。时间复杂度或或。我处理后者时本来想写倍增可是发现空间不够于是写了类似弹飞绵羊的分块 /wul。
E - Mobitel

好题。直接 DP 是的，显然过不了，并且难以优化转移，因此考虑优化状态。将第三维改为还要乘上才能，那么一定可以被写成的形式，而后者一共只有个，因此离散化后再 DP 即可，时间复杂度。
F - May Holidays

好题。发现这东西用一般方式极其难以维护，不过发现分块可以维护，于是树剖后用分块维护即可。时间复杂度或。
G - You Are Given a Tree

我好菜。容易写出的贪心，类似于赛道修建。显然有，也就是较大时答案较密集。因此，对于直接暴力；对于，有，所以枚举答案再二分即可。时间复杂度或，需要卡常。这几道题还是挺有启发性的，一定程度上刷新了我对分块算法的认知。
H - 裁剪线

不会平面图欧拉定理 /dk。答案为「交点数量」-「线段数量」+「线段连通块数量」，前两个是好维护的。对于第三个，使用一棵线段树维护，线段树中的每个节点维护的是当前这个区间内的水平线段集合；插入一条竖直线段时，将其在线段树上拆为个区间，对于每个区间，先将其中的线段与竖直线暴力合并，再贪心地保留其中右端点最大的线段即可。
I - 美好的每一天

这是怎么不会的？因为只关注区间内字符出现次数的奇偶性，因此容易想到做一个前缀异或，接下来就跟异或序列差不多了。时间复杂度
J - 树套树

写了个线段树套 FHQ-Treap。
K - Machine Learning

/bangbangt 题，带修莫队即可，求这个东西的是的。
L - 糖果公园

树上莫队板子，学了就会了。
M - 网络管理

一坨，可以树上莫队或树套树。
N - 歴史の研究

哦原来是回滚莫队板子，但是我不会，写了个的做法但剪枝后常数极小。回滚莫队的做法是，对于左端点在一个块内的询问，先固定当前左端点并对右端点进行扩展，再临时对左端点进行扩展，扩展完之后复原即可。也可以用区间众数的做法做。
O - Path

回滚莫队是容易的，记一个单做法。枚举每个节点，那么要在子树内和子树外各选两个点。考虑子树外的部分，先找出一组全局最优解，那么只有的祖先不一定取得到最优解，对这一部分单独做一下即可，每个点只会被插入次，因此时间复杂度是。考虑子树内的部分，显然可以启发式合并，但是不太优雅。依然对的祖先单独考虑，对于其他的点，它们子树外的贡献都相同，因此只用考虑极大的子树，同样每个点只会被插入次。时间复杂度。
P - 作业

简单题，莫队 + 分块即可。
Q - Minimum Difference

简单题，不同的出现次数只有种，随便维护一下即可。
R - Closest Equals

简单题，扫描线即可。
S - TEST_107

简单题，扫描线即可，卡了半天常。/lh
T - フードコート

好题，自己做法假了，我好菜。容易去掉操作二，那么剩下部分扫描线一下即可。

DP 专题

Link

把之前没做的题补了。

J - 麻将

经典题，好困难。先考虑判定，设表示用了，预留了个和个，是否预留了对子的最大面子数。因为，所以只需要存储两个的矩阵就可以表示当前状态。对于转移，考虑枚举添加了几个即可。建出自动机后在自动机上跑 DP 即可。
R - Making Shapes

好牛的题。首先容易转化成一车限制，发现难以直接计数。发现到和值域很小而很大，于是考虑数位 DP。数位 DP 暴力做即可。感觉这个 trick 挺牛的。
U - Bear and Cavalry

做这题的时候在想啥。发现答案一定是之一，那么直接 DP 即可，卡卡常能过。DDP 部分也是容易的。
V - 邮局

决策单调性 + WQS 二分即可。
W - The Bakery

简单题，设表示分了段，最后一段是的最大权值，枚举用线段树维护这一维即可。
X - Lightning Conductor

决策单调性优化板子。
Y - 柠檬

每一段的第一个和最后一个一定相同，据此写出 DP 方程再斜率优化即可。我太烫了没想起。
Z - 征途

斜率优化即可，不过顺便学习了一下 WQS 二分。
AA - Building Bridges

李超线段树优化 DP 即可。
AB - Akvizna

WQS 二分 + 斜率优化即可。

NOIP 模拟赛 20260403

Link

A

随便维护一下即可。
B

随便 DP 一下即可。
C

赛时想复杂了。容易写出 DP，发现状态数极少，于是矩阵快速幂即可。我再不会自动机上走路题我可以跳了。
D

屎题。把矩形和用前缀和表示出来，再把平方暴力拆开拆成项，再对于每项分别维护即可。

CSP-S 模拟赛 20260411

Link

午练说是。

Codeforces Round 1092 (Div. 1, Div. 2)

Link

E - Star Map

三角形不合法的条件时单增或单减，于是考虑将所有点按照排序并遍历，对维护两个单调栈，一个单增一个单减。加入一个点时，若把一个点出栈了，那么就可以形成一个三角形（若栈中还有点）。感性理解一下，这样构造出来就是最优的。

计数专题

Link1 Link2

A - Stairs and Lines

并非困难，咋 *2700。

容易写出 DP，且容易想到矩阵加速递推，于是变成了。
B - Easy Sequence

简单题，按照高度相同的连续段分组即可。
C - ?

简单题，矩阵优化递推即可。
D - ColorfulJewelry

咋是枚举题，我想多了。暴力枚举两个矩形，求出所有可能的对。固定，的范围显然形如，因此记录即可。统计答案时同样枚举，简单组合数一下即可，需要人工容斥掉回文串。
E - Pass to Next

原。
F - Research Rover

简单题，简单 DP 再人工容斥即可，做的时候因为边界条件调了半天。
G - TwiceTwiceTree

手模一下容易写出的式子，然后随便推一推式子就可以得到的递推式。
H - SemifinalAssignment

简单题，数据范围只允许枚举队线再 DP，发现只需要给 DP 加一个常数维，大力转移即可。
I - 图腾

原。

Codeforces Round 1093 (Div. 1, Div. 2)

Link

终于回紫了。

F - MEX Replacement on Tree

咋是树的价值陈。考虑操作一个点的影响，随便分讨一下就可以得到一坨东西，然后再维护一下这一坨即可。感觉没啥意思，不想写。

早练 20260414

Link

为啥不叫「早练计划」。

A

简单题，我咋写假了。
B

典题。
C

容易发现是单调的，也是好求的，于是二分即可。赛时我在干嘛。

早练 20260416

Link

咋是原，不过这场挺牛的。

A

分块即可，可以预处理。
B

发现按照排序是困难的，于是按照排序再随便 DP 一下即可，需要前缀和优化。
C

显然最优操作是一层套一层的，因此枚举内侧的位置再 BFS 一下即可。

模拟赛 20260418

Link

A

简单题。
B

简单题。
C

我好菜，对着一个自认为很有用的 Key Observation 做了半天没做出来。尝试找到一些严格更劣的解，发现对于若有则一定不优。转化一下变成是左侧第一个不比小的元素或是右侧第一个比大的元素，于是现在只留下了对可能的。剩下的就扫描线消掉一个限制再数据结构维护一下即可。
D

一个经典结论是和本质相同且区间长度为或。直接 DP 是的，发现难以优化状态数，于是考虑分治，然后闵可夫斯基和一下即可。时间复杂度，有大常数。

Educational Codeforces Round 189

Link

终于在 Edu 上分了，可惜晚上神志不清没切 F。/ll

疑似是切了 F 能上橙的。

F - String Cutting

简单题，随便讨论一下可以把有效答案缩减到，再二分 + 哈希即可。

早练 20260422

A

简单题，莫队即可。算下来时间复杂度应该是。
B

典题，容易维护出每棵子树内和子树外的直径，做完了。

早练 20260424

Link

A

nth_element 会把第小的元素放在第位，并使它前面的元素不大于它，使它后面的元素不小于它。
B

简单题，没开 long long 挂了点。
C

先枚举左右边界，再枚举上边界的区间，就可以得到下边界的区间，拿棵树状数组维护一下即可。我好菜这都没切。

CSP-S 模拟赛 20260427

Link

这场 gap 好大。

A

简单题。
B

简单题。
C

难绷题。首先需要知道一个结论：期望个值域为的数中有相同的数。将数组分成块，在每块中找出两个集合使得它们的和的差不超过，期望找次。随后在每个块中选择一个找出的集合，并找出两种方案使得总和相同。因为每个块最多相差，所以总共最多相差，期望次找到答案。取左右最优。
D

难绷题。首先显然有。容易发现当我们有个和一个时，若，那么可以将变成。因此我们只用考虑中前小的元素，将这些元素复原后剩下元素就可以直接复原。具体地，对于当前序列若，那么可以删除，不会影响答案。于是记搜即可。

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

Link

终于上橙了 /ll。咋这才上橙 /ll。感觉上橙并非困难啊 /ll。

F - Building Tree

我咋没场切。线段树分治即可。

Codeforces Round 1095 (Div. 2)

Link

这场好难。/ll

懒得补了。

早练 20260429

A

简单题，我咋写了个线段树优化建图。/ll
B

先将和排序，枚举高度，发现高度可能为的位置形成了一个 L 字形的区域，并且要求每行每列都要有的位置，容斥一下即可。
C

太困难了。/ll 容易发现最终每个人离别人的最短距离是固定的，因此可以将离别人最短距离相同的人化为一组。对于长度为偶数的区间，我们钦定选择靠左的位置，那么只需要在求出答案之后再镜像一次即可。在一组以内，设表示前个人，占用了个偶数区间的概率，直接转移即可。

NOIP 模拟赛 20260430

Link

A

不是咋是原。
B

简单题。
C

乱搞可过。
D

LCT 维护一下即可，不会。/ll

晚练

Link

五步 (20260401)

简单题，只有矩形不合法，DP 一下再 bitset 一下即可。
故障 (20260402-1)

正难则反再乱维护一下即可。
跳舞机 (20260402-2)

简单 DP。
传奇团子吃家 (20260407)

我前几天甚至还看到过这题。容易写出贪心，设当前权值为，那么可以按照分段，分段后即可倍增。考虑如何分段，对于每个位置，要找到它右侧第一个段使得在模意义下这一段穿过了。发现对于一个段，它能贡献的是模意义下的一个区间，因此 set 维护即可。
传话 (20260408)

略写复杂了点。答案是排序后加 rank 再求 max，线段树维护即可。
Yet Another Graph Coloration Problem (20260409-1)

找到环上的一个点再随便搞搞即可。
枫 (20260409-2)

随便 DP 一下即可。
DYN-Dynamite (20260413)

大概确实不太会这种树上贪心 + DP 吧，虽然好像跟赛道修建差不多。显然先二分，设表示离最远的未被覆盖的炸弹到的距离，表示离最近的被选中的点，这两者的转移是显然的。转移完后再判断一下的关系，检查能否覆盖或是否需要新加点即可。
配对序列 (20260414-1)

我咋在小朋友时期还打过这场并在这道题中取得了分的好成绩。

简单题，记两个即可。我咋写了个树状数组。
扶苏出勤日记 (20260414-2)

简单题，二分再单调队列即可。
HUR-Warehouse Store (20260415)

简单题，但是写成 IIIDX 了。考虑贪心，用大根堆维护一下已经选的数即可。
Odd Rows (20260416)

并非困难，我咋没做出来。设表示考虑了列，有个奇数行是否可行，转移是区间覆盖的形式，随便搞搞即可。还原方案也是容易的。赛时在想什么神奇 DP。
army 汗国军队 (20260420)

这不跟游园会差不多吗，我咋没切。考虑从小到大插入数，设表示插了，上一个关键点在位置，LIS 数组的前缀的差分是的方案数，大力转移即可。
Boundary (20260421-1)

简单题，随便 DP 一下即可。
SAM-Toy Cars (20260421-2)

简单题，转成区间覆盖再贪心即可。咋挂了。/ll
魔术 (20260422)

嘟。我咋还想了一会儿。以及题面符合 Gemmer 中魔术师的设定。
小矮人派对 2 (20260423)

随便 DP 一下即可。我写法好屎。/ll
美食家 (20260426)

简单题，直接矩乘即可，赛时没反应过来向量乘矩阵是的。
云音泛 (20260427-1)

简单题，离散化一下即可。
Game (20260427-2)

细节题，分讨一下即可。
搭塔 / Tornjevi (20260428)

简单题，数据结构维护一下即可。我咋写了半天。/ll
Droga do domu (20260429)

简单题，DP 次即可。我咋没过。/ll