2025 年 9 月日祭
鲜花 (2025.9.1)
注意到我停课了。
另外注意到我今天上午做了三道题，下午也许是在尝试改上一场 CF 的 Div. 1 E，顺便学习了一下反射容斥。学了之后发现改不出来，于是放弃了，并开始补日祭。总之就是下午一道题都没做？啊？什么效率？但是我不是挺认真的吗？啊？
MX NOIP 3
A - Novelist
略。
B - Bicycle Tour
根据部分分容易想到从小到大一条条加边，并在形成环时做一个链上的 to min。于是先建出原图的最小生成树，然后树剖即可。
C - 数列色ぬり
题解。
D - DequeQL
改不动。
多校杂题选讲 20250905
A - [NOISG 2025 Prelim] Itinerary
考虑直接把
的路径描到树上，计算每一条边会被经过几次，这一步可以用树上差分解决。接下来，若 是起点，我们只用关注 到 的路径，如果在 的基础上加上这一条路径，每条边的经过次数依然 则合法。实现上，从 开始 dfs，记录 到每个点的路径上的每条边的经过次数的最大值即可。 B - [USACO24DEC] 2D Conveyer Belt S
考虑哪些位置是不合法的，显然是环形传送带及其内部。环形传送带是容易找的，但是内部并不好找。于是正难则反，考虑从边缘开始洪水填充，能走到的位置就是合法的位置，剩下的就是不合法的位置。不过对于每个询问都搜索一遍显然会挂，所以考虑倒着处理询问，每次删掉一个传送带，若当前位置原本不合法但四连通有合法的位置，那么从当前位置再次开始洪水填充即可。
-
首先有结论，若机器人
与机器人 最终停在第 行，那么区间 的机器人一定都可以停在第 行，因为机器人 到第 行的过程中一定会经过第 到第 行， 同理。所以可以停在第 行的机器人一定是连续的一个区间。于是考虑对于每个 ，求出可以到达第 行的机器人的区间，于是问题就转化为了用最少的给定区间覆盖询问区间，这个问题可以用 ST 表实现。具体地，设 表示从 开始，使用 个区间，能达到的最右侧的位置。 D - [NOISG 2023 Finals] Curtains
将询问
转化为，判断是否有 。考虑先离线下来并且按 排序，这样就少了一个限制。考虑使用线段树维护从每个位置 能够完整覆盖到的最右侧的位置 ，那么回答询问就变为了单点查询，增加幕布 是对于 区间修改。具体地，对于所有 的位置 ，执行 。发现这个操作难以实现，但是发现多个这样的操作可以合并（具体过程略），所以使用一棵维护 lz tag 的线段树即可。 E - From the Unknown (Hard Version)
略。
G - [HEOI2013] SAO
好神秘的树形 DP。设
表示考虑到 子树，且 在子树中的拓扑序为 时的方案数。转移时根据 关系分讨，再推推式子就可以得到一个 的 DP，然后发现可以前缀和优化，就变成 的了。 -
发现问题类似于传递闭包，并且似乎也只能用类似于传递闭包的做法解决。不过先考虑暴力，显然是从
开始 bfs，发现这样反复 bfs 太浪费了，于是考虑用一次 bfs 解决所有问题。设 表示对于点 ， 能否通过 的边到达它，这显然可以用 bitset 维护，考虑转移，发现还需要定义辅助数组 表示边 是否属于 ，它同样可以用 bitset 维护，并且可以通过差分预处理。此时对于边 就有 。时间复杂度 ，空间复杂度 ，后者无法接受。于是考虑把 个询问分 次处理（或每次固定处理 个询问），理论上时间复杂度不变，只是增加了一些常数，并且空间复杂度变为了原来的 。 取一个小常数即可。
MX NOIP 4
炼屎计划。
A - xorseg
被 Ad-hoc 了一会儿，原因是认为满足第二个条件的区间数量是
级别的，后来才反应过来应该是 或者 级别的，具体的也没证。 B - heap
什么屎题，手写堆。
C - toptrees
什么唐题（虽然我更唐，赛时没写出来），直接回退背包即可。
D - lca
什么不可做题，不会。
多校联考 20250906
A - string
唐题。
B - ball
我好唐。发现计算答案时
需要升序，但是乱序时严格更劣，所以考虑 DP，设 表示考虑了 ，当前已选的数组成的集合是 的最大美观度，转移是容易的，但是需要高精度。 C - tree
我好唐，65 分部分分都不会写。显然合法的连通块需要满足大小是偶数并且每种权值出现次数不超过一半，后者转化一下就是众数出现次数不超过一半。设权值
出现了 次。考虑枚举众数 ，并将众数的权值设为 ，其余的数的权值设为 ，那么上述条件就又转化为了连通块的权值和应该为非正偶数，这容易用树形 DP 做出来。可是发现直接这样统计是没有正确性的，因为当枚举的众数并不是实际的众数时，连通块的权值也可能是非正偶数。于是考虑反过来，先计算大小是偶数的连通块个数，再减去其中众数出现次数超过一半的连通块个数，即权值和为正偶数的连通块个数，这样才有了正确性。又发现树形 DP 的第二维只用取到 ，所以时间复杂度是 的。
鲜花 (2025.9.7)
虽然前几天看着还有那么多日祭没写，但其实一写起来还是挺快的。（这句话好人机，好唐，但是不管了。）
另外把一个月的日祭写在一起不就不叫日祭了么，应该叫月祭（？）。
Atcoder Regular Contest 205 (Div. 2)
D - Non-Ancestor Matching
E - Subset Product Problem
好妙的一道题。如果直接用桶统计有着优秀的
的时间复杂度。考虑优化。首先把 写成 的形式，使得 都是 10 位整数。接下来，设 ，其中 都是 10 位整数，表示 ，那么答案就是 。代码极其好写，时间复杂度 。
Atcoder Beginner Contest 422
F - Eat and Ride
我好唐，只想出了一个伪的做法。容易想到拆贡献，那么设
表示从 走到了 ，还剩 步没走的最小花费，转移显然，答案是 。 G - Balls and Boxes
问题一原来就是背包啊，有点难绷，自己只想到了扩欧。
你说得对，问题二是生成函数，但是根号分治是个好东西。
考虑暴力，枚举
，计算 ，时间复杂度 ，支持 。于是现在需要一种 的暴力。设 表示 的方案数，直接转移即可，支持 。
Codeforces Round 1047 (Div. 3)
G - Cry Me a River
设
同阶。首先容易写出 的简单 DP。容易发现，如果 A 或 B 从某个点开始游戏，最终会来到一个红色点，那么我们可以认为当前点在 A 或 B 操作的时候也是红色的。将一个点染红之后，我们并不用全部重新 DP，只需要考虑它对入边的影响，如果有新的点被染红，那么再递归考虑它的影响即可。发现每个点在每种状态下只会被染红一次，所以时间复杂度 。
多校杂题选讲 20250912
A - Towers
容易想到把最高的节点作为根，那么有权值的位置一定是叶子，且有两个叶子的权值恰好等于高度的最大值。对于每个子树，一定存在一个权值为最大值的节点不在这个子树内，所以我们只需要这个子树内存在一个叶子节点的权值大于等于这个子树内高度的最大值即可。选择权值大于等于这个子树内高度的叶子节点时，贪心地选择当前权值最大的叶子节点即可。对于根也类似，只需要选择前两大的叶子节点，将它们的权值设为高度最大值即可。
B - Fairy
见 電圧。
-
才做完就升紫了。因为这题自己写得完全没有题解清楚，并且也达不到总结的目的，所以就不记了。
D - 01 on Tree
神秘贪心。容易发现，如果我们选了一个点，那么会贪心地把它孩子中所有的
选完，这样一定不劣。那么就可以理解为这些孩子与父亲“捆绑”在一起，形成了一个连通块。那么同理，我们可以用并查集维护当前的连通块，并且把所有连通块放进优先队列中，如果交换两项顺序之后逆序对个数更少则贪心地交换，这么做是有正确性的。每次取出最靠前的连通块并与父亲合并，边合并边计算贡献，直到只剩一个连通块。做完后答案就算出来了。 E - Wine Thief
发现直接拆贡献不好做，考虑其他做法。发现链上的独立集没什么有用的性质，然而如果是在环上，每个点的贡献次数都是相同的。于是先假定此时是在环上，但是发现会算漏
与 都被选的情况。为了补上这种情况，钦定 被选，那么此时要在 里面选 个，加上对应的贡献，再递归解决子问题即可。 F - Interesting Problem (Hard Version)
困难的题目。同样感觉记起来没什么用，也写不清楚，所以就不记了。
G - Family Photos
不想记。
Codeforces Round 1048 (Div. 2)
第一次 Div. 2 打进第一页，虽然是 VP，而且这场 unrated。
C - Cake Assignment
想到了 SGU 126。这道题正难则反。
D - Antiamuny Wants to Learn Swap
似乎有线性做法，但是不管了，线段树和 ST 表一样草过去。发现一个序列是好的的充要条件是不存在长度为
的下降子序列，那么记 表示以 结尾，长度为 的子序列中，子序列的第一个数的下标的最大值，这个显然可以用线段树维护。然后再用 ST 表维护一下 的区间最大值即可。 E1 & E2 - Maple and Tree Beauty
我好菜，花了 80min+。首先想到答案不会超过所有叶子深度的最小值
，然后考虑如何让答案达到 。赛时一开始认为答案总是取每个叶子的名字的一段前缀与一段后缀，后来手模 组样例又吃了一发罚时之后才发现只取前缀。那么，我们只需要考虑深度 的节点，并把其中深度相同的节点涂成一种颜色即可，其余节点可以任意涂色。正确性显然，因为如果匹配的位置越深，需要涂色的节点数严格不降。最后，还要判断能否将 层分为黑白两色，这一步可以通过 bitset 优化背包 DP 实现。时间复杂度 。如果用根号分治可以再优化到 。
MX NOIP 5
这场是我考成屎了，甚至还垫底了。
A - 阿蛮
在 NOIP T1 放样例极弱的概期 DP 的出题人，愿你们的母亲的天堂相遇。
赛时爆零了。因为赛后没有立即发题解，所以甚至还是 GPT-5 给我讲的。
首先发现题目里面给的带权随机数其实是诈骗，因为当确定了新来的人数
与舞娘获得的总票数 ，是容易求出这种情况的概率的（用其他 个舞者分得 个观众的方案数除以 个舞者分得 个观众的方案数）。设 表示新来的人数为 ，舞娘获得了 票时的加分， 表示概率，那么现在只需要求出 即可。直接计算是 的，但是通过一些组合恒等式就可以将其优化到 。 B - 菟园 & [HNOI2010] 弹飞绵羊
自从之前有一次把 LCP 当成 KMP 写之后就感觉终于完全理解了 KMP 与 fail 指针等内容。
容易想到建出 fail 树，那么问题就转化为了在树上支持某点到根路 径修改与单点查询，类似与弹飞绵羊，所以下文介绍弹飞绵羊的做法。
看起来平衡树与 LCT 这些数据结构的学习成本都挺高的，确实像牢祝说的那样，这些问题都可以用线段树或者暴力数据结构解决。
对于弹飞绵羊，暴力的做法是
修改 查询。考虑均摊一下，将 个数分为 个块，记 表示从 开始跳父亲，跳到的第一个块外的节点， 表示跳的次数。这样，对于修改，我们只需要对块内节点进行更新，时间复杂度 ；对于查询，我们只需要一个块一个块地跳，时间复杂度 。显然当 取 时最优。时间复杂度
Codeforces Round 1049 (Div. 2)
D - A Cruel Segment’s Thesis
考虑
是偶数的情况。拆一下贡献，答案就是 ，其中 ，再拆一下贡献就变成了 。于是按 排序取较小的一半即可。若 是奇数，那么枚举那个区间不选即可。 E - Prime Gaming
好题，但是难绷。考虑
的 ez version，发现是容易做的。然后考虑重新定义状态，钦定一个阈值 ，让状态中的 表示 的数， 表示 的数。这样，对于一个状态 ，它可以表示的序列数量就是 ，那么答案 的序列的个数 就应该是 。可以把 按照 归类，即设 ，这样就可以 计算 了。答案即为 。时间复杂度 ，前半部分有小常数。
MX NOIP 6
A - 句法分析
唐题。
B - 树上前 k 大菊花
目前见过的题中，极多个物品中选前
大 / 小的题其实做法挺单一的。容易想到把每个点作为中心，先让菊花的权值取到最大值，并放到优先队列中，然后再将权值调小，把新的菊花放进放进优先队列中，直到取了 个即可。 C - 相关聚类
根据特殊性质并观察样例发现是偏结论类型的题，并且如果是树形（基环树）DP 显然不可能做到
。手模几个样例就发现只需要计算出环的大小与环上 的数量，根据 的数量分讨一下即可。
多校联考 20250915
明明就是没什么辨识度好不好，考了个 CW rk 2 还被表扬了。
C - 发喷山火（CF2119F 加强版）
对于原题：容易观察到路径结构如下：从
出发，先经过若干个 1 -1到达一个1 1，在获得了足够的生命之后再前往某一个终点。赛时没写出 50pts 是因为没有发现：在全程中就算存在多个1 1，都只会在第一个1 1获取到足够的生命。（话说要是发现了这个点，赛时还写出了 50pts，那场切黑也是很难绷了。）根据这几点，我们可以先处理出每个点经过若干个1 -1能够到达的最近的1 1，这可以用多源 bfs。接下来，我们可以从开始 dfs，再传一些神秘的参数，就做完了。 D - 走路赚钱（JOISC2019E 弱化版）
对于弱化版：把条件转化一下可以变成当
时，若 或 ，可以获得 的价值。离散化过后用扫描线维护一下即可。
Atcoder Beginner Contest 423
质量场。
Edu Codeforces Round 182 (Rated for Div. 2)
被降智了呜呜呜。/dk /dk /dk
D - Price Tags
一眼极其数论分块，然后无脑写了之后被卡了。后来才发现是想复杂了，根本不用对于
去更新 ，直接拿 找对应的 即可。这题显然是不难的，主要是有些诈骗。 E - Looking at Towers
思维为零的数据结构题。容易写出一个
DP，然后发现可以用加乘线段树优化，然后就做完了。
MX NOIP 7
A - 地球往事（[Gym105170E] Connected Components）
唐题。
B - 纪元（[Gym104976E] Period of a String）
挺有趣的一道题。考虑
与 两个串，发现 对 有一些限制，每个限制形如： 的前 位形成的可重字符集是 。那么同理， 本身也有一些限制，发现 的限制是可以与 对 的限制，合并形成对 的限制的。所以倒序维护当前的每一条限制，根据限制判断是否有解；若有解，再根据限制构造出 ，便可以推出所有 的值。 C - 黑暗森林（[Gym105170A] Eminor Array）
赛时找规律过了？（
实则是很没素质地用了 oeis。）发现答案是：D - 死神永生
原来我在 7 月 10 日并没有意识到我在那一天算是学会了虚树。
题目要求是「到每个点距离的最大值最小的点」，发现离一个点最远的点一定是直径的一个端点，而满足条件的点就一定是直径上的一个点。
于是这道题就做完了。用线段树动态维护虚树的直径即可。时间复杂度
。
Codeforces Round 1051 (Div. 2)
难绷主要难绷在我每次在晚上打 CF 都要慌，而太慌了导致 D 没切出来，放弃 D 去看 E 的时候也许 20min 就秒了？具体时长记不到了。
D1 & D2 - Inversion Graph Coloring
实则挺唐的。设
表示选了 ，其中的最大值是 ，最大的满足 且 的 是 的方案数。转移显然，时间复杂度 。用树状数组维护 与 即可优化到 。赛后补题的时候因为初始化漏了一点导致调了 inf 久。/dk E - Make Good
比较一眼的题，与这道题类似的题还有 [ARC203B] Swap If Equal Sum。对于一些通过若干次可逆的操作将初始状态变为目标状态的题，容易想到先将初始状态变为一个相对规则的状态，再变为目标状态。对于本题，容易想到尽量把
)都变成(，但是如果只是将))变为((，那么还会留下一些单独的)。观察操作的性质，发现我们可以交换与 ，而这样交换是不会改变下标的奇偶性的。于是考虑把奇数位置上的 )与偶数位置上的)匹配并变成((，此时剩下的)的下标的奇偶性一定相同。接下来，给每个剩下的)匹配一个(。此时还剩一些(，再翻转一半的(变成)并与另一半的(匹配即可。边做边判断无解即可。一个 Corner Case 是，如果剩下的)全部在奇数位上，且奇数位上全是)，此时无解。
鲜花 (2025.9.18)
前几天还有十几个 To-Do 现在居然补完了。
虽然动用了一些特殊手段。（好唐）
虽然今天晚一点又新增了两个 To-Do。
MX NOIP 8
B - 计树
赛时写了一个完全没有正确性的 DP。
发现最后一个节点一定是叶子，那么我们就可以推出倒数第二个节点的几种状态。依此类推，考虑倒着 DP，设
表示考虑了 的节点，还缺 个父亲与 个儿子的方案数，大力分讨转移即可。答案是 。
Atcoder Beginner Contest 424
G - Set list
Codeforces Global Round 29 (Div. 1 + Div. 2)
E - Maximum OR Popcount
显然先把问题转化为达到每个答案至少需要多少次操作。贪心地，我们每次让或和中最后一个
变成 。具体地，选择 个数中的某一个，使得将这一位变成 的代价最小。可是这时，可能低位不再是 。所以对于下一位进行同样的操作，直到后缀变成全 即可。 F - Exchange Queries
考虑先按
排序，那么交换 也可以转化为交换 。接下来，我们只需要对 建边，并用线段树维护 SCC 即可。
Codeforces Round 1052 (Div. 2)
D1 & D2 - Max Sum OR
对于 D1，考虑
，此时恰好可以两两匹配。那么当 时，就有一段前缀无法匹配。对于这段前缀解决子问题即可。对于 D2 也类似，两两匹配后解决子问题即可。 E - Yet Another MEX Problem
考虑钦定
，那么就可以用一棵线段树来维护对于每个钦定的 ，子数组的最大长度，查询就是全局 。发现钦定的 不是实际 时一定不优，所以并不影响。
多校杂题选讲 20250926
A - Bit Counting Sequence
发现
即当前的进位位数，根据这一点构造即可。挂了几发一是因为 __builtin_popcount(unsigned int)，二是因为左右移负数位是 UB，洛谷评测机上会 TLE。B - 一安在？ / Gdzie jest jedynka? 2
发现
的性质不算特殊，最特殊的是 ，于是考虑把 找出来。考虑对于一个数，询问它与其它每个数的 ，其中的最大值就是它本身，并且能取到最大值的要么是 要么是它的倍数。所以我们把 和它的倍数再单独拿出来，解决子问题，最后最多会剩下两个数，其中一定有一个是 。再拿这两个数去找到 即可。精细实现即可达到题目要求。 C - 健身房 / Siłownia
有点难绷的贪心。首先容易想到一个天真的 DP，类似于最小点覆盖。然后你发现这样是错的，因为当存在
使得 时，这样会挂掉。发现我们肯定不能延后选，只能提前选，所以令 即可。 D - Letter Stamper
也许算是第一道独立做出的紫？虽然得知这是 DP 好像是从讨论区得出的，并且调不出来的时候还看了题解，但是最后没看懂，还是自己调出来了？不管了。Solution。
I - Decoration
题面好唬人的样子，但是其实对这个东西建一个图就是一个基环内向树森林，要求的就是长度为
的简单路径的长度的最小值。倍增即可。
Codeforces Round 1053 (Div. 2)
B - Incremental Path
不是有点难绷赛时只要不着急，认真手摸一下，几下就做出来了。
E - Limited Edition Shop
我写了一个很难写的做法，显然是有更好写的做法的，但是不管了。对物品按 A 的喜好排序，设
表示选了物品 ，B 选到了物品 的最大价值，转移是 。要用线段树维护，即区间（并且是前缀）加，并取前缀 。对于后者，可以用线段树二分与区间覆盖实现。好写的做法的状态定义是一样的，转移略有些不同，但是不管了。写这种数据结构优化 DP 都写烦了。 F - Attraction Theory
不错的题。手模一下样例可以发现，如果我们关注位置
上最终留下来的人数 ，那么 一定是连续的一段有值，并且除两端之外都应该是奇数。直接计算是不好做的，于是我们用与 Wine Thief 类似的 trick，先把尝试问题转化为对称的。考虑枚举区间长度与端点的奇偶性，于是此时就可以钦定端点为奇数，最后再加上常数项即可。通过一些简单的计算可以得到 的期望与不同的 序列的数量，再利用 的前缀和与二阶前缀和即可计算出答案。 G1 & G2 - Hidden Single
Atcoder Beginner Contest 425
E - Count Sequences 2
发现这个东西其实有两种算法。记
，一种是 ，另一种是 。你会发现把第二个化简之后就是第一个，但是第二个显然更好算。其实第一个也能算，但是赛时我饭堂了，只单独处理了每个数的质因数分解，而没处理每个数的阶乘的质因数分解。 G - Sum of Min of XOR
好简单的 G，赛时没切出来是因为回寝室了，话说这应该是我第一次独立做完一套 ABC。一种暴力是建 01trie 暴力，时间复杂度
。考虑反过来，对于每个 ，有哪些数与 异或能取到最小值，再简单拆贡献计算答案即可。时间复杂度 ，精细实现可以做到 。（感觉做法好抽象，讲不清楚。）
- Title: 2025 年 9 月日祭
- Author: Getaway_Car
- Created at : 2025-09-01 00:00:00
- Updated at : 2026-01-19 20:21:41
- Link: https://getawaycar1024.github.io/article/diary/2025/09/
- License: This work is licensed under CC BY-NC-SA 4.0.