2025 年 12 月日祭

DP 专题

Link

A - Matching

唐。
B - 乘积，欧拉函数，求和

类似 G。
C - 互不侵犯

唐。
D - Eat The Trees

插头 DP 模板弱化版。
E - Tree Planting

屎。考虑分治，对于较小和较大的情况分开讨论，两种情况的暴力都是好写的，只需要再剪剪枝卡卡常就能过了。
F - 游园会

DP 套 DP 板子。设表示文本串的前位与模式串的前位的 LCS，表示考虑到了文本串的第位，，且匹配匹配了位的方案数。发现，所以只用记录的差分数组。直接转移即可，时间复杂度。
G - 寿司晚宴

考虑如何方便地表示出一个数质因数。发现对于任意一个数，它至多拥有一个的质因数，于是考虑把的质数状压一下，再单独记录的质因数（若有）。考虑按照的质因数分类，没有的质因数的数每个数单独分为一类。容易发现，对于每一类数，要么只有 A 取，要么只有 B 取，要么都不取。除此之外，还有最基础的的质因数不交的限制。于是考虑设表示考虑了类，当前 A 和 B 的状态分别是，直接转移即可。
H - 集合选数

发现建图过后这东西就是若干个残缺的网格图，对于每个网格图 DP 一下即可。
I - 一双木棋 chess

记搜即可。
K - 滚榜

哦哦看错题了。

首先容易写出暴力，发现判断合法时只关注相邻的两个队，于是考虑拆拆贡献，就彻底只与相邻两个队有关了。设表示当前选了，其中最后选的一个队是，当前花了费的方案数，转移枚举下一个选的队即可。
L - 卡牌

类似 B 和 G，但是加了个容斥就不会了呜呜呜。

发现容斥过后，每部分是独立的，所以可以直接相乘。然后直接暴力容斥即可。
M - V

原。
N - 巧克力

绷，不会博弈论。会了博弈论之后就是一个简单数位 DP 了，需要卡常。
O - XOR Triangle

扫码题。
P - 同类分布

唐题。
Q - Minecraft

唐题，进位数量是的，所以 DP 即可。
S - NRE

唐题，设表示考虑到并且向后覆盖了的最小值，线段树搞搞即可。
T - Isolation

分块优化 DP 倒是第一次见。转化一下题意，变成区间，查询前缀的之和。对于每个块，维护表示块内的答案，表示懒惰标记，表示的之和。对于修改，只需要同时维护与即可，查询可以直接查。

Codeforces Round 1068 (Div. 2)

Link

差点切 E Round。

E - Shiro’s Mirror Duel

Solution。
F - Isla’s Memory Thresholds

不难想到，对于一次询问，出现的不同步长的数量是级别的，并且步长是单增的，于是不难想到根分。设阈值，对于步长的部分，我们可以把询问离线下来，并且预处理出对于每个与每个步长，可以走到最右侧的位置；对于步长的部分直接暴力二分即可。理论上，当时，时间复杂度为。实际上，因为第二部分显然跑不满，所以小一些还跑得更快。

Codeforces Round 1069 (Div. 1)

Link

傻逼 Round。

C1 / C2 - Beautiful Patterns

傻逼题吧，只能说是我没见过这样的 trick。

题意可以转化为选两个回文串的方案数。考虑枚举两个回文串各自的长度再计算，此时又分为两种情况，一种是两个串的回文中心相同，另一种是不同。注意到对于后者，无论两个串是否相交，两个串是回文串的期望是独立的，所以可以直接算。再随便搞搞就了。
D - Secret Message

为啥赛时过的人这么少。

注意到如果最小的条边不构成树就直接做完了，所以考虑最小的条边构成树的情况。发现此时可以删掉一条边再加一条边，具体地，若删掉，新增，那么要么都在的子树中，要么都不在的子树中，这一部分可以用 LCA 和扫描线实现。但是可能不止删一条边，那么贪心地，考虑删掉第小的边并加上第小的边，这种情况错解不优，所以就做完了。时间复杂度。

NOIP 模拟赛 20251213

Link

NOIP- 模拟赛。

A - 平均

唐。
B - 逃离奶龙

板。
C - 碰大碰车战

Link。Solution。
D - 和求

Link。这是真模数技巧。考虑把原式变成，其中。暴力把这个式子拆开，变成一堆乘积的和，发现对于一坨乘法，若其中有个，这个式子在模意义下就是，于是只用关注个的式子。设表示连通块以为根、大小为、取了个的答案，这个 DP 是的。发现显然可以最后再计算，并不影响 DP 过程，所以这个 DP 只与有关，而的取值只有个，所以对于每个做一次 DP，时间复杂度

容斥、计数专题

Link

基本原理：

主要类型：

一般容斥
- 子集容斥（SOSDP / 高维前缀和）
- 通过 DP 与组合数学进行计数
- 在 DP 中直接计算容斥系数
反射容斥
人工容斥
A - 810975

推式子题。
B - 硬币购物

人工容斥题。
C - 旋转排列

推式子题。
E - Timber

推式子题。
K - 染色问题

反复容斥题。
L - 游戏

容斥之后转化为树上背包。
M - 唱、跳、rap和篮球

考虑容斥，难点在于计算，发现本题可过，然后就做完了。

考虑做法，把上式拆成，发现里面的式子可以预处理，所以整体就可以了。
N - At Most 2 Colors

设表示考虑前位的答案。发现转移有两种，第一种是前个位置颜色不同，那么当前这个位置有且仅有两种选择；第二种是前个位置颜色相同，那么当前这个位置可以涂任意颜色。所以有，初始状态是。
O - Square Constraints

个人感觉是严格小于员工招聘的。把图画出来是环形的四分之一，我们对前一半，令；对后一半，令。考虑对前一半容斥。首先对所有位置按照排序。我们称一个位置被选了，当且仅当它初始在前一半并最后系数为。枚举表示共有个位置被选，设表示前位置有个被选的方案数，转移是容易的，讨论一下当前位置是否被选即可。
P - Road of the King

有趣题，并非很困难，那我咋不会。整个图的信息显然是冗余的，尝试减少信息量。考虑这条路径在做什么，发现它是先经过一些点，再把这些点“带回” 所在的 SCC。于是容易设表示当前经过了条边，所在的 SCC 大小为，总共经过的点数是的方案数。对于转移，分讨下一个点的类型即可。
Q - Pass to Next

好困难。转化一下题意，即对于所有满足的，求出。首先把最小值为的条件人工容斥掉。接下来，可以对这个式子直接暴力拆开求解递推式，也可以状物求出递推式。对于断环为链，只需要修改 DP 的初始值即可。
R - Good Division

困难题，做这题时感觉被降智了一样。首先容易转化成每个区间没有绝对众数，并写出一个的 DP。发现有效的转移数量是的，于是直接优化没什么前途。考虑人工容斥，求出所有位置的 DP 值之和与不合法的位置的 DP 值之和，其中前者显然是好维护的，考虑如何维护后者。考虑新加一个元素对后者产生的影响，发现暴力枚举还是的。尝试减少枚举次数，对于每个位置，处理出当它作为区间左端点或右端点时，有哪些数可能成为区间的绝对众数，而这个东西的总和是的。于是拿桶维护即可，时间复杂度。
S - First Come First Serve

牛牛题。考虑第个人，他有的贡献，当里面没数时有额外的的贡献。设第个人到第个人的一个端点在中，那么要让第个人有的贡献，显然可以确定的安排，于是令即可。
T - LEQ and NEQ

原题。
U - MST on Line++

拆贡献题，讨论一条边什么时候出现即可，有点无聊。
V - Colorful Balls

唐唐题，发现最多只有一个的连通块，找一下这个连通块中的点即可。
W - A Nameless Counting Problem

牛牛题。单调不降是困难的，因为存在相同的数。发现相同的数可以消掉，所以可以转化为单调递增，从而又转化为互不相同。设表示长度为、值域为、异或和为且元素互不相同的序列数量，那么答案可以用表示出。可是求又是困难的，考虑先求出允许相同的方案数，这可以求出。考虑容斥，对于当前长度，枚举表示出现奇数次的数值的数量，表示出现奇数次的元素的数量，表示出现偶数次数值的数量，那么令减去一个系数乘即可，系数分两次计算即可做到。
X - 局部极小值

考虑暴力容斥，枚举所有可能的情况。对于每一种情况，用状压 DP 即可。
Y - 图腾

牛牛题。通过一些想象力进行人工容斥，答案可以变成几个好求的东西。树状数组维护即可。
Z - Yet Another ABC String

牛牛题。难点在于不合法子串可能合一起，所以难以对不合法子串进行容斥。既然不合法子串可能合一起，那就定义不合法子串是极长的，这样就可以容斥了。枚举不合法子串数量，其他字符的方案数是好算的，把个不合法子串插进去，因为串是极长的，所以除了开头的串，每个串都只有两种方案（不能和前面接上）。稍微讨论一下是否有串在开头即可。

反射容斥

求从向上或向右走到且不触碰直线的方案数。设与关于对称。考虑人工容斥，用总方案数减去触碰直线的方案数，后者是走到的方案数。
求从向上或向右走到且不触碰直线和直线的方案数。考虑容斥，设表示触碰过一次的方案数（连续触碰也只算一次），同理，那么答案应为，时间复杂度，因为翻折那么多次后就没有贡献了。

D - 骗我呢

转化一下限制即可。
F - count

牛牛题。首先考虑用什么东西来刻画区间最值，想到了笛卡尔树，那么两个序列同构当且仅当笛卡尔树的结构相同，所以考虑对不同的树计数。考虑把好的序列的限制放到树上，第二条限制是，第一条限制是左链长度（点数）。发现限制左链很难受，所以把每条左链拆下来，形成一棵新树，限制转化为深度（边数），容易发现新树和原树形成双射。再把新树转为括号序列，就可以反射容斥了。
G - Bessie and Cards

画一个函数，轴是抽卡次数，轴是当前剩余摸卡次数。抽卡和特殊卡相当于；抽卡相当于，完全没用，不用考虑；抽卡相当于。画出来过后将其旋转即可。
H - Again Counting Arrays (Easy Version)

显然容易把数转化为数再算算贡献，反射容斥是的，而直接 DP 是的，根分一下即可。
I - No Streak

牛牛题。暂不考虑第四个条件，即去掉反射容斥，此时可以组合意义搞搞求出答案。我太菜了不会这一步。考虑如何反射容斥，发现碰到线的前一步一定是 Bob 胜，而接下来有以下三种情况：
- Alice 胜，反射后是 Bob 胜。因为不能连胜，所以需要强制插一个 Bob。
- 插一个平局，接下来 Alice 胜或平局。
- 插一个平局，接下来 Bob 胜。因为不能连胜，所以需要强制插一个 Bob。
用总方案数减去这三者即可。
J - 生成字符串

转化一下限制即可。

NOIP 模拟赛 20251219

Link

A - 序列

Link。DP 搞搞即可。
B - 公司

Link。最终的形态一定是若干棵最小生成树。所以预处理出每个子集的最小生成树，再 DP 一下即可。
C - 种树

Link。第一问是积木大赛，考虑第二问。重新定义后，。以这个位置为分界点，求出从这个位置开始的前缀与后缀的答案，就可以求出对于每个断点的答案。求前后缀答案的时候用单调栈维护一下即可。
D - 游戏

Link。考虑以为根，设表示确定子树内的端点或确定子树内没有端点的最小询问次数，有。为了最小化，显然需要对它的儿子按照值从大到小排序。因为我们需要以每个点为根求一次答案，所以换根 DP 即可。对于交互，按照 DP 的理解模拟即可。

Codeforces Global Round 31 (Div. 1 + Div. 2)

Link

Ad-hoc Round，ABED hyw？

C - XOR-factorization

讨论是偶数的情况。对于从高位到低位考虑，若第位是，则从中尽量选一个非的数异或上，这保证了的异或和为；否则从中选偶数个非的数（尽可能多）并将它们分别异或上，因为是从高到低考虑的，所以这之后每个数依然，且最大化了之和。
D - Insolvable Disks

贪心 + 模拟，维护当前区间右端点的范围即可。
E - No Effect XOR

Solution。
F - Control Car

傻逼题，不如玩原神。

NOIP 模拟赛 20251227

Link

A - 出关

求出 Z 函数之后优先队列优化 DP 即可。
B - 补天

按照题意模拟即可。
C - 理水

先缩个点，对于每个边双，若其中有边，那么这个边双内的点可以到达所有点。缩点过后形成一棵树，对于树上的两个点，若其简单路径上有边或点，那么这两个点可达。模拟即可。
D - 非攻

无聊推式子题。

Good Bye 2025

Link

上分场，Hello 2026 能否送我上橙呢？

D - Xmas or Hysteria

时显然无解，时容易构造，的时候需要特判。
E - Flatten or Concatenate

显然二分一下，把数组分成两段，最大值一定在更短的那一侧出现，于是递归即可，次数是的。
F - Conquer or of Forest

典中典中典中典中典中典中典中典中典中典中典。对于一棵子树，若其根是白色，其它点都是黑色，那么把它拆下来再安回去，它的根依然是黑色，其他点依然是白色，且不对外部产生影响。所以直接把所有白点断开，形成若干个连通块，剩下的数数是好做的。
G - deCH OR Dations

笑点解析：场切了 ABC424F 但是不会随机赋权的 trick。设表示以第条弦结尾的链的数量的奇偶性，设表示对于以第条弦结尾的所有链，每条链的弦的集合的异或和，那么问题就转化为了求，于是只需要求出就可以求出答案。显然有，对于每条弦随机赋权并集合哈希即可。
H - Create or Duplicate

感觉比较 Ad-hoc，看了 Tag 和两个 Hints 就会了。考虑只有的情况，显然直接同余最短路即可。发现「把一类物品翻倍」非常困难，只能考虑「把所有物品翻倍」。发现若初始时没有物品，我们可以通过后者达到前者的效果，但题目要求三个物品初始各有一个，于是再额外加一维表示当前选了哪些物品即可。
I - Numbers or Fireworks

嘟嘟嘟的非多项式时间复杂度题。考虑建图，可以证明这个图一定是二分图。钦定左侧的点更少。枚举左侧有哪些点是黑点，一一考虑右侧的点是黑点还是白点，设表示考虑了右侧的前个点且左侧的白点中已匹配右侧黑点的点集为的方案数，转移是个 SOSDP 的形式，理论时间复杂度，有小常数。

Educational Codeforces Round 186

Link

下分场，主要是赛时 D 和 E 做太慢还吃了几发罚时。这下 Hello 2026 难以橙名了吧。

这场好招笑啊，第一次独立订完一场 Div. 2，虽然我没场切 F1 / 2 更招笑。

F - Christmas Reindeer

Solution。
G - Short Garland

之前没怎么写过长链剖分优化 DP，写这道题就当练板子了。设表示以为根，子树中最后一个点到的距离为的方案数，转移是显然的。因为第二维与深度有关，所以长链剖分即可。时间复杂度，是因为快速幂。