2026 年 10 月日祭

NOIP 模拟赛 20261006

Link

A

简单题。
B

真难吧 /ll。考虑链上的情况，发现相交的两个区间可以带来的贡献。考虑环上，发现并不影响区间相交，扫描线一下即可。
C

简单题，随便维护一下即可。
D

简单题，并查集维护边双，顺便维护点信息即可。

计数小测

Link

A

简单题，斜率优化即可。
B

典题，先是自动机上走路，后面集合划分容斥的系数是，赛时记不到系数猜了半天。
C

简单题，发现回退是容易的。
E

自己没注意到决策单调性 /ll。注意到之后随便维护一下即可。

NOIP 模拟赛 20261008

Link

这场在做梦。

A

简单题，把能消的消了那么剩下的是一个平方串。
B

简单题，先定根，容易发现限制是外向树森林的形式，随便数一下即可。
C

好题。首先一个点的权值是其邻居权值的，于是可以 DP。也给显然的性质是权值上界不超过。设表示点权值为且其父亲权值的方案数，表示点权值为且其父亲权值为的方案数。对于转移，要求中的权值均要出现，于是可以容斥。直接做是的样子。设点的权值上限为，那么容易证明，于是转移时设个上限就是的了。但还可以更优。目前的瓶颈是，从儿子转移到容斥数组是的，以及从容斥数组转移到也是的。对于前者，容易发现对的贡献只与低位有关，于是对这部分可以做一个形如前缀积的东西。于是我们只需要对进行转移，复杂度就变成了。对于后者，转移是全集去掉某一位的子集和，发现这东西可以拆成共个区间，于是做个前缀和即可。
D

并非困难。Solution。

NOIP 模拟赛 20261010

Link

A

简单题，随便搞搞即可。
B

简单题，随便搞搞即可。
C

并非困难，我们要找的是最小的不与原树任何子树同构的树，写个搜子拿树哈希判定即可。

NOIP 模拟赛 20261013

Link

A

简单搜索题，赛时挂了点。
C

注意到我们只需要求出相邻的每对数是否合法。于是先处理出前后缀背包，发现合并的复杂度无法接受，于是在前缀背包上枚举，要求的是后缀背包上若干个等长区间的，单调队列维护即可。
D

有点牛逼。可以证明在进行所有不影响连通性的操作后，剩下的部分是一棵树。也可以乱搞创过去。

综合题训练 20261014

Link

A

简单题，找出生成树按欧拉路径构造即可。
B

容易发现 SCC 之间是独立的，且每个 SCC 内的答案是全源最短路的最大值。
C

原来也能过吗。考虑直接在状态里记录当前加入的点与当前的叶子节点，注意到直接做会算重，于是需要对树确定一个唯一的生成顺序。考虑从小到大加入最终的叶子，那么要求当前加入的叶子是加入后所有叶子中最大的，直接转移即可。时间复杂度。
D

有点绷。注意到答案下界是，并有上界。上界的证明是，如果当前还有剩下的物品，那么车上剩余空间一定，否则一定能继续装。也即此时一定会装的物品，装车一定能装完。于是暴力即可。
E

简单题，线段树优化 DP 即可。
F

简单题，容易把限制转化为：区间内第一次变化是变大还是变小，于是对连续段（或者说变化的位置）进行 DP 即可，转移是一个二维前缀和的形式。
G

容易发现最优策略一定是选若干组完整的和至多一组的前缀。于是二分后贪心即可。

NOIP 模拟赛 20261015

Link

A

简单题。
B

简单题，容斥一下即可。赛时没判自环挂到 40。
C

简单题，线段树维护即可。
D

首先 min-max 容斥。对于当前集合，设为第一个出现的概率，，那么对每个均有。可以理解为每个赌徒都是按照下注，当串中出现时停止。另有。将这些式子联立起来即可解得。注意到理论上分母可能出现模数的倍数，但仔细想想发现其实很难构造。

NOIP 模拟赛 20261017

Link

A

简单题。
B

简单题。
C

莫队被卡常了 /ll。注意到对于，若 $\mathrm{col}{\mathrm{lca}(a, d)} = \mathrm{col}{\mathrm{lca}(b, c)} $，那么$ (a, d) $一定是没用的，因为包含$ (a, d) $的区间也一定包含$ (b, c)$。于是在 LCA 处统计，我们只关心极小的 LCA 为当前点的点对。对于子树中的一点，只需要找出其他子树中编号与它最接近的两个点。于是启发式合并即可。
D

TBD

NOIP 模拟赛 20261021

Link

A

有病吧。
B

样例强度。对于存在边的情况，直接树形 DP 即可。否则，Bob 可能选择路径上某点的子树走进去。因为 Bob 走的时候 Alice 也可以删边，发现不是很好维护双方的决策。于是考虑二分，Alice 的策略是，对于一棵子树，如果 Bob 进去会导致他次数不够则提前断掉。做完了。
C

并非困难，我咋不会呢。本质上是两棵树上两条点到根的路径两两形成点对的并。可以在一棵树上直接用线段树维护可以到达另一棵树上的哪些点，线段树合并的时候，如果一个区间已经满了就不管了，这么做好像是 2log 的。一个更优的做法是，考虑若干个点到根路径的并，可以看成是经过这些点的欧拉回路状物，于是可以在 DFS 序上维护欧拉回路的长度。具体地，线段树节点维护的是区间内被加入的点的 DFS 序的、以及从第一个点依次走到最后一个点的路径长度，显然随便维护一下即可。
D

并非困难，场上没怎么做。首先需要维护出当前这个数的斐波那契表示，手模一下发现只用维护 1010...101 这样的段，加一位的影响就是进位成一个 1 或平移一位。对于计数部分，容易发现一个 1 可以展开成 11010...1010 状物，且两个 1 展开后是一定不相交的。发现是否展开唯一的后效性就是展开后会有一个 0 的位置，于是设表示考虑到第个 1，是否展开的方案数，容易用矩阵转移。考虑维护这个过程，发现插入或删除一个段只会影响个段的转移，于是拿 set 维护段，线段树维护答案即可。可以先做一遍把需要用的下标拿出来并离散化，第二遍再算答案。

NOIP 模拟赛 20261023

Link

A

好难啊。注意到答案有单调性，但是二分后方程没法解。注意到在答案处一定存在，且存在时一定是最优方案。于是可以先把序列变成全，这个过程直接模拟的复杂度显然是对的，再找到的最小值退回去。
B

又被卡常了，有啥办法呢。分治做法是容易的。
C

咋是简单题，赛时没开。容易把每一步的贡献拆成与差分有关的形式，注意到贪心地往差分更小的一边走是对的。因为，所以可以在每层上二分出向下走的位置。用线段树维护的差分即可。
D

并非困难。是偶数是简单的。对于是奇数的情况，可以把图画出来，那么限制就是不出现环。若把两侧按奇数到偶数的边对齐，那么所有环的形态都是先走一段偶数再走一段奇数，且长度一定是。于是可以 DP，设表示考虑了组，左侧连续段长度为，右侧连续段长度为的方案数。注意左侧连续段必须是前面从右侧连过来的（包括右侧的长度）。直接转移即可。

NOIP 模拟赛 20261024

Link

A

转移时按排序即可，容易通过邻项交换证明。
B

简单题，随便搞搞即可。
C

简单题，线段树维护哈希，再启发式合并一下即可。
D

困难题。显然先二分。发现我们的操作区间一定有包含关系，于是考虑 DP。注意到操作次数是的。设表示操作次能否让变为全，容易优化变为表示操作次后最多能让变为全。对于个左端点我们显然只用保留互不包含的区间，于是左右端点都递增。对于转移，可以考虑一个区间相对原序列的贡献。考虑优化，从后往前扫描线，那么加入一个区间时可以弹掉贡献比它小的。考虑把转移条件构造成单调的形式以用单调队列维护，发现问题在于不单调。但又注意到左端点只可能在的前缀最小值上，否则一定可以扩展。于是大力维护即可。

NOIP 模拟赛 20261026

Link

A

啥唐。赛时读错题了。
B

原。
C

简单题，赛时没调出来。在处统计即可。
D

Solution。

NOIP 模拟赛 20261028

Link

A

简单题。赛时循环条件写错了挂了点。
B

并非困难。建出表达式树会方便很多。
C

啥一坨。考虑操作区间的端点可能的位置，容易两者要么不交，要么存在一个没有限制，于是开始分讨。对于两边都没有限制的情况，即原串合法的情况。对于左边有限制的情况，容易发现取区间最大值是优的，此时的限制在上。直接 DP 是的，因此我们可以分前后两段 DP。枚举处的后缀和，DP 一遍再和前面合并即可。右边有限制也类似。对于左右都有限制且不交的情况，容易发现左右两侧至少有一侧取到最大值，于是可以类似地 DP，注意需要限制存在一个位置的后缀和。还需要减去两边同时取到最大值的情况，也是类似的。
D

并非困难。显然扫描线。容易写出一车限制，主要需要维护的是，其中是一给定值。前两项都是容易维护的，考虑最后一项。发现满足前两项的一定是当前的后缀最小值，于是可以单调栈维护，第三条限制就可以直接二分了。

NOIP 模拟赛 20261030

Link

A

折半即可。
B

注意到只有长度为二和三的段，并且长度相等的段一定不交，于是可以直接 DP。也可以二分，拆成若干段后，容易发现每段至多只有一个长度为三的段，直接枚举判断即可。
C

注意到当前先后手谁占优取决于本质不同排列方案数，感知到方案数是奇数的限制很严，手推一下容易得到方案数是奇数的充要条件是，即。考虑博弈部分，如果初始时方案数为偶数，假设 Bob 有必胜策略，因为 Alice 在前期拥有控制权，所以 Alice 可以在 Bob 进入必胜状态之前把自己换成后手从而必胜，矛盾，故 Alice 必胜；如果初始时方案数为奇数，那么若一方操作后方案数为偶数就直接寄了，要保持方案数为奇数，双方都只会依次取，判奇偶性即可。于是问题转化为前面的条件，一两个维护一下即可。
D

对于一棵树的任意一棵子树，有，即。利用这个就可以把数子树改成数点，点分治即可。之前没见过这种形式。

CSP-S 2026

A

简单题。
B

简单题。
C

并非困难，场上做了好久。考虑从左往右和从右往左贪心构造出两条路径，容易发现两条路径只有一步不同，并且且两个点一定是相邻的。枚举不同的这组点，两边的方案数是容易维护的（吗）。
D

并非困难。显然先二分。先去掉次叶子，因为把叶子涂黑一定不如把父亲涂黑。随后把剩下的点全涂黑，如果剩下点数不超过则显然合法，否则需要将一部分点涂白。注意到把叶子涂白一定是不合法的，把度数大于二的点涂白则一定会出现超过两个连通块，于是我们只会涂白一个二度链。把每个二度链取出来维护一下即可。

DP 基础 + DP 优化

Link

J - 摩天大楼

原 + 典。

Link

B - Kendama Challenge

简单题，随便维护一下即可。
C - Dynamic Instability

原，但不知道咋升黑的。
E - Colorful Segments

简单题，线段树优化 DP 即可。

晚练

Link

N

Chase (20261005)

啥唐题，树形 DP 即可。
百花齐放的太阳花田 (20261006)

啥唐题，二进制分组即可。
旅行 (Day 2) (20261008)

最开始看错题了 /ll。考虑枚举取到最大值的边，即从小到大加边。当前边有三种情况：原图最小生成树上的边、边双内的边、形成边双的边。对于第一个可以先把生成树建出来，第二个没用，第三个可以更新这个边双的根所在子树的权值。拿个并查集维护边双，拿两棵线段树分别维护当前点权和答案即可。
交换 (Day 2) (20261009)

好题。考虑按位贪心，容易发现当前位置能取到的值只有个，于是大力维护一下每条边的状态即可。
蔬菜 (20261011)

首先时间倒流。对于单询问，考虑从大到小贪心，并且每个蔬菜放在最早的能放的位置。注意到可以把限制转化为每天最多个、总共最多个，从而去掉天数的限制，视作固定的天。于是一个个加进去即可。
Difficult Mountain (20261012)

简单题，随便 DP 一下即可。也有很牛的贪心做法。
信使 Messenger (20261013)

宝宝容斥题，我咋没调出来，赛时差三个字符。
线段树 (20261015)

并非困难。设分别表示上有 tag 的方案数和的任意祖先（包括其本身）上有 tag 的方案数，大力维护一下即可。赛时差四个字符。
星座 3 (20261016)

容易想到笛卡尔树上 DP，转移容易线段树合并维护，做完了。赛时没写出线段树合并。以及有反悔贪心做法。
比赛 (20261020)

啥屎。扫描线一下，线段树维护后缀与乘积之和，发现修改可以写成矩乘的形式，然而常数太大了，不过卡卡常能过。这个矩乘本质上就是一个合并懒标记的过程，于是可以手动展开维护。
旅行 / Tourism (20261026)

虚树简单练习题。可以回滚莫队，也可以扫描线。对于扫描线，按从小到大扫，扫到一个位置就把这个点到根路径上的所有点染色为，那么询问的答案就是整个树上颜色的点的数量，再减去中点的 LCA 的深度。这个过程容易树剖维护。
水池 (20261027)

简单题，建出笛卡尔树贪心即可。
Hard route (20261028)

把路径分成经过直径和不经过直径的，前者可以分治算，后来想了想好像可以笛卡尔树，后者可以直接做。好像有很简洁的做法，大概是枚举交点之类的。

S

彼方的她 (20261005)

啥卡常题，大力 DP 即可。
天气先生 (20261006)

啥唐题，乱维护一下即可。
⼤魔法师 (20261007)

啥屎题，还是原。
Jumping Man (20261008)

咋是姜萍人。Solution。
建筑抢修 (20261009)

咋又是这个反贪。
Waterfront (20261011)

与 N 组的题类似。
数据备份 (20261012)

板子反贪。
No cost too great (20261013)

与 N 组的题类似。
Crave Wave (Ver. 2) (20261015)

好难。Solution。
异或粽子 (20261016)

原。
酸雨 (20261020)

原。
道路建设 / Road Development (20261026)

板。