2025 年日祭
Getaway_Car · · 个人记录
最新内容见 此处。
本文将同步发表于洛谷（暂无法访问）、CSDN 与 Github 个人博客。
2025.1
2025.1.4 新的一年
今日歌曲：New Year's Day
去年停课的时候是有记日祭的，但是有一些是手写的，一直都还没有整理好。今天看到一个简单的trick，想记下来。于是，就又开始写日祭了。
-
[洛谷 P2831] [NOIP2016 提高组] 愤怒的小鸟
一道远古状压题了。（一是指题目本身远古，二是指这道题是好久之前就该做的题。）看到第一篇题解的trick，想起去年暑假集训的时候也有这样一个trick，但是忘了是哪道题。这个trick挺简单的，但也挺好用：状压时，如果目标状态是全0或全1，并且转移顺序不影响结果，那么可以直接从最低位的1或0转移，因为最低位最终一定会被转移，而顺序又不影响结果，所以这样做可以优化掉
O(n) 的复杂度。其他的按正常状压即可。 -
[Atcoder ARC100E] Or Plus Max
今天学了 SOSDP，挺神奇的一种 DP。这个题算是板子题吧。只用维护子集的最大值与次大值即可。
今天下午给初二机房的办了一场比赛，整体比较顺利。（所以没做什么题。）比赛链接：CWOI ER 1 & NYR。
今天感觉要掉橙了，但是Rated的比赛还要等一周。想着把之前那篇被打回的题解改了交了，但是晚上写给初二机房的的题解了，没空。看明天改吧。
2025.1.10 新的开始
今日歌曲：Castles Crumbling
今天考完期末，回来一看，天塌了，掉橙了。明天打一场比赛。
现在终于确定15班后续的各种事项了。又是一个新的开始。
另外，我就莫名奇妙地进省选了（尽管是体验名额）。还有一个有趣的事实：
我没有提高组一等奖，然而我进了NOIP（体验名额）；我没有NOIP一等奖，但我进了省选（体验名额）。
期待人生中的第一场SCOI（希望不要爆零）。
2025.1.12 言而无信
今日歌曲：Back To December （好吧其实是存货）
我果然是一个言而无信的人。踩一脚前天的日祭，昨天还是没打比赛。
今天%你赛，除了暴力的B和C，其它全挂了分。至于A，调试的时候把模数写掉了。被暴扣70分呜呜呜。
最终荣获
-
A - 括号序列
题目：给一个由左右括号构成的字符串
s ，对于每一个位置i ，输出有多少个子串，满足这个子串是一个合法的括号序列，并且i 这个位置在子串中。题解：简单维护前缀与后缀的括号数量即可。（忘写该死的模数暴扣70pts。）
-
C - 矩阵删除
题目：给一个
n \times m 的 01 矩阵，我们想在每一行删除一个元素，得到一个n \times (m - 1) 的矩阵。其中删除的元素的位置(i, a_i)(1 \le i \le n) ，满足\vert a_{i} - a_{i + 1} \vert \le k(1 \le i \lt n) 。请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的。由于答案很大，输出答案对10^9+7 取模的值。题解：比较板的DP，但是赛时思路没那么清晰，也没去推式子。分别维护对于每一个位置的方案数以及与旁边位置重合的方案数，推出式子后发现全都是求和，于是用前缀和维护即可。
2025.1.13 乐极生悲
今日歌曲：Wonderland
今天期末考试考完了，整体还行，语文更是考到了惊人的
下午体育课，刚好初一体锻放歌，放得全是霉霉的歌，我还去点了几首。开心。
然而下课要集合的时候，我小跑了一下，而这下就恰好被足球爆头，眼镜镜架直接断掉，箍牙的铁丝直接断掉，嘴皮直接被铁钉磨得烂掉，鼻子被眼镜压了一个印子，还在流鼻血。
真是乐极生悲。
2025.1.17 傻子游戏
今日歌曲：Foolish One
今天开始上课六天。
昨天听说 jmr 拿了清华一等约。祝贺他。
这周二（1.14）已经回到15班了。
昨天晚上玩梗发癫，还玩了离谱的傻子游戏。达成成就：在5.5h里睡够8h。
上午%你赛，T1忘了判零挂了10pts，T3是之前做过的一道原题，于是赛时死磕，最后没调出来。赛时的思路基本上是对的，但是没想到容斥；又因为我钦定的一个条件有问题，导致正确性略有问题，最后没调出来。
喜提
-
A - 串
题目：在虱子王国，一句话由
n 个词组成，其中恰好有k 个词是怪的，其它的词都不是怪的。众所周知，负负得正，我们定义一句话的一个区间是怪的，当且仅当其中含有奇数个怪词。请构造一句符合条件的话，使得其中怪的区间数量最多。题解：发现答案为奇数块乘上偶数块。构造即可。
-
B - 艺术家
题目：给定一个长度为 n 的颜色序列
c 。再给出m 个区间，第i 个区间为[li, ri] ，保证任何两个区间都是不相交或包含的关系。在接下来的q 个单位时间内，第i 个时间会给定x, y ，表示将c_x 变为y 。请对于每一个区间求出，最早的其中所有颜色都互不相同的时间。题解：
保证任何两个区间都是不相交或包含的关系。
所以可以把区间建成一棵树。当一个子区间合法，其父区间才有可能合法。在原数轴上维护
lst_i 表示i 之前第一个颜色与i 相同的点，则一个区间内部颜色互不相同等价于\max\{lst_i, l \le i \le r\} 。使用线段树维护。对于lst 的更新，用 set 维护。即可。（难写死了，还没写完。） -
C - 黑白树 （[Atcoder ARC108F] Paint Tree）
题解：画一个直径上吊着节点的图，讨论一个节点在什么时候可以带来贡献。容斥计算即可。
晚上打了入门赛，可以加咕值了。
晚自习最后10分钟，记一些话。
我的信竞，在进步么？看起来好像是的。要是拿现在的我和一年前的我对比，那已足以
k 倍杀。但……补过的题还是不会做，码量大一点的又不愿意写，一到晚自习就写不动了，于是写一会儿又开始划水。我倒有一个优点，就是一般不会去刷水题（除了入门赛）。但是，难一些的题……绿题效率低，蓝题想不全于是又看题解，紫题几乎无法独立完成。最终做了的题似乎是白做。
……
终究还是人的问题。
2025.1.18 正难则反
今日歌曲：Wildest Dream
这两天换了头像。
今天上午VP CodeForces Round 997 (Div. 2)。
-
[CodeForces 2056A] Shape Perimeter
计算重叠部分即可。
-
[CodeForces 2056B] Find the Permutation
我们总是建从小节点到大节点的有向边，对这个DAG进行拓扑排序。因为我们有时并不想让一个小节点往大节点连边，所以用堆维护入度为零的点即可。（可恶，赛时多测不清空卡了我一发。）
-
[CodeForces 2056C] Palindromic Subsequences
挺玄学的构造题。我们希望大概长这样的结构：
\underbrace{1,\ 1,\ 1,\ \dots,\ 1}_ {a个1},\ 2,\ 3,\ 4,\ \dots, a + 3,\ \underbrace{1,\ 1,\ 1,\ \dots,\ 1}_ {a - 1个1} 这样构造出的答案有
a(a + 2) + 1 = a^2 个，可以通过。稍微分讨一下即可。赛后看了一下题解，发现自己好唐：
1,\ 2,\ 3,\ \dots,\ n-2, \ 1,\ 2 -
[CodeForces 2056D] Unique Median
又是一道正难则反，计算坏的序列的个数。这道题的trick挺巧妙的，但没接触过，确实想不出来。发现长度为奇数的序列一定不是坏的，所以只考虑偶数长度序列。对于一个序列的中位数
x ，将序列中\le x 的数化为-1 ，其它的化为1 。若最终区间和为0 ，那么这个序列就是坏的。另外要注意去重。维护前缀和即可。 -
[CodeForces 2056E] Nested Segments
组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量，那么需要构造成二叉树。（这里具体不想证明。）对于某一个节点，设其儿子数量为
cnt_u ，则计算\prod C_{cnt_u - 1} （卡特兰数）即可。
下午先把E题改了，学习了一下吉司机线段树。这东西挺好理解的，写起来也很爽，但就是又臭又长又难调。
-
[洛谷 P10639] [BZOJ4695] 最佳女选手
这道题本来是第二道模板题的，但因为第一题相当于第二题的子问题，所以直接冲着这道题来了。写板子即可。（啊啊啊终于还是讨厌上吉司机线段树了啊。）
今天整理了一些去年的日祭。还没把手写的整理上去。
2025.1.19 简直糖丸
今日歌曲：All You Have To Do Was Stay
今天上午%你赛，T1爆零了，简直糖丸。一共得了
下午给初二讲题，讲得……简直糖丸。
烦球，今天最后几乎啥都没干。
啊不是为什么T1爆炸啊。
2025.1.20 简直乐丸
今日歌曲：Daylight
昨晚又是在5.5h内睡满8h的一晚。
今天上午VP CodeForces Round 998 (Div. 3)。才做四道，糖丸了。
-
[CodeForces 2060E] Graph Composition
赛时就很唐。并查集查连通并算连通块即可。
-
[CodeForces 2060F] Multiplicative Arrays
一道很好的DP+组合数学题。赛时推式子感觉推出来了，结果赛后再一看伪了。很容易发现，
\sum_{i=1}^{len}[a_i \neq 1] \le 16 ，所以DP计算非1 元素的情况，再用组合数学即可。 -
[CodeForces 2060G] Bugged Sort
这个题就挺有意思的。这篇题解感觉讲得比官方题解还要清晰。可以观察到，当
n \ge 3 ，我们可以任意（正常）交换两组的位置。因此，我们可以将两组数进行翻转。换而言之，进行翻转的次数必须是偶数次。这里记翻转次数为cnt 。我们把较小的数放在a ，较大的放在b 。若按a 排序后b 有序，那么该组数据有解，当且仅当满足这三个条件之一：-
2 \mid cnt -
-
否则无解。判断即可。
-
今天下午看了一个2025年度第一个乐子（原帖，内部帖），简直乐丸。
又一个新梗诞生了：
@chen_zhe 管理制度错了就要改，不能让无辜的人以泪洗面，如果管理制度还是这样的话，洛谷将会越来越腐败！！，我大不了就棕名，我要让洛谷知道瞎诬陷的严重性！
2025.1.21 反则难证
今日歌曲：deja vu
今天上午VP CodeForces Round 999 (Div. 1 + Div. 2)，状态还好。
-
[CodeForces 2061C] Kevin and Puzzle
有点思维的DP，题目挺好的。
-
[CodeForces 2061D] Kevin and Numbers
又是一道正难则反。我们很难将
a 合并，那就把b 中不合法的进行拆分。用 map 维护即可。其实这道题也好证，只是想凑一个小标题罢了。 -
[CodeForces 2061E] Kevin and And
这题有点……难评。为什么字典树过不了啊……
因为
m 很小，所以对b 进行状压，再将a 的变化量压进堆里选最大的k 个即可。（好吧其实不是特别理解。）
F 听不懂。
附一张梗图。
（这里声明一下，不是 jmr 讲得不好，而是实在听不懂。）
2025.1.22 比特塞特
今日歌曲：Maroon
年前最后一天了。
上午%你赛
-
A - bins （[洛谷 P6807] [BalticOI 2010 Day2] Matching Bins）
差分即可。
-
C - candies（[洛谷 P6808] [BalticOI 2010 Day2] Candies）
题解。
2025.2
2025.2.8 水讨论区
今日歌曲：Bigger Than The Whole Sky
今天洛谷讨论区关闭了。（以后不能水讨论区了。）
这个寒假，什么也没干。一看进度，已经和初二的差不多。但是他们第一遍拉得挺快，估计效果不大。
我如果现在回去，在那边又吃不饱。于是，就只有多肝一肝，把之前的进度补上来。
晚上打ABC392。
-
[Atcoder ABC392E] Cables and Servers
略考细节的题。先找连通块，之后再找每个连通块中的返祖边（即无用的边），再把连通块连通即可。
（可是这题我赛时AC，后来突然想到一个hack。还没改，烦死了。）
2025.2.9 终于战胜
今日歌曲：Holyground
综合题1。
-
[Gym 103466I] Space Station
神奇搜索题，暴搜+剪枝+略微组合数学即可。
神奇卡常题目，拼尽全力，2700ms+，终于冲进3s。
-
[Gym 101982D] Count The Bits
很普通的一道DP题，可是赛时都在想组合数学。
-
[Gym 102428F] Fabricating Sculptures
神奇DP题。最开始看题解都没看懂，一是自己确实不理解是怎么算的，二是题解写得比较简略，看了好久才看懂。
设
dp_{i, j} 表示从上往下一层层放，当前一共放了i 个，最下面一层放了j 个的方案数。有方程dp_{i, j} = \sum_{k = 1}^j dp_{i - j, k} * (j + 1 - k) （希望没写错）。将这个式子拆开再维护前缀和即可。（开了long long见祖宗。） -
[Gym 104172F] Sum of Numbers
很有趣的一道题。很容易发现，两个相邻字符串长度之差（的绝对值）为
0 或1 。暴搜即可。赛时的想法是，将原字符串平均分，再给
0 或1 的偏移。可是偏移少了一些，虽然没 TLE 但一直 WA，拼尽全力无法战胜。赛后再改一改，拼尽全力终于战胜。
今天本来说再补补昨天的 F，改改昨天的 E，结果今天的第三题看半天看不懂，昨天的 E 和 F 都没做。
最终今天做了四道题。
感觉心态有点崩。（尤其是看第三题的时候。）
……
2025.2.10 放弃即可
今日歌曲：Peace
综合题2。
今天还做出了一道题。
-
[Gym 100861E] Extreme Programming
看了题解真的好简单。首先我们先确定这些问题的顺序。推推式子，排序即可。现在，我们不用考虑顺序，只用直接背包，找出最大的
EV 与最小的ET 即可。可是这道题不知道哪里写挂了，WA on test 15。
放弃即可。 -
[Gym 100217I] Sharing the Sweets
分拆数板子题。（可是我不会。）写板子即可。
分拆数 OI Wiki。
-
[Gym 100202A] Little Brackets
这题着实简单。设
dp_{i, j, 0/1} 表示放了i 个括号，当前高度为j ，是否到过最高点（深度为k ）的方案数。直接转移即可。可是赛时想多了，一直在想组合数学。或许先设方程再推会好一些。
赛时还因为多测不清空挂了四发。
今天还举办了 CWOI ER 2 & 1 > 2 Round，感觉对于他们还是太难了。
（今天字符数破
2025.2.11 放弃即可
今日歌曲：Pink Pony Club
模拟赛
-
B - 刀言刀语 （[洛谷 P6864] [RC-03] 记忆）
今天给的题解以及同学讲解的都是非矩阵做法，可是听得迷迷糊糊。一下午尝试乱搞做法，结果没搞出来，最后，一道题都没改出来，
放弃即可。晚上终于学习了矩阵，基本学懂了，这才发现矩阵有多好用。之后又看了这道题的矩阵+线段树做法，终于基本懂了。将这些数据打包成矩阵：
\begin{bmatrix} ans & cnt & 1 \end{bmatrix} 。对于操作一，等同于\begin{bmatrix} ans & cnt & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 \newline 1 & 1 & 0 \newline 1 & 1 & 1 \end{bmatrix} 。对于操作二，等同于\begin{bmatrix} ans & cnt & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 \newline 0 & 0 & 0 \newline 1 & 1 & 1 \end{bmatrix} 。对于操作三，若是恢复某个操作，则与操作一二相同；若是删除某个操作，则将这个操作设为单位矩阵（\begin{bmatrix} 1 & 0 & 0 \newline 0 & 1 & 0 \newline 0 & 0 & 1 \end{bmatrix} ），不会对答案产生影响。用线段树维护每个操作对应的矩阵，区间求和（求积）即可。这道题记得比较详细，毕竟是第一次接触矩阵。
-
C - 刀妙构造
题目：给定一个长度为
n 的排列a ，通过尽可能少的操作，使得\forall a_i = i 。判断是否有解。若有解，输出具体的操作。操作的定义：选择x, y 满足1 \le x, y \le n, \left | x - y \right | = 1, a_x \ne x, a_y \ne y ，交换a_x 与a_y 。题解：原本就满足
a_i = i 的位置将原数组分割成若干个块。对于每个块，若是目标的一种排列则有解。设当前块为[l, r] ，则依次把数l \sim r 移到位置l \sim r 。要注意的是，在移动的过程中，可能会使得其它的a_i = i 成立。所以我们将这些即将成立的位置先进行偏移，再将当前的数移到目标位置即可。扩展：尝试在
O(n \log n) 的时间复杂度内求出有解的排列个数，对998244353 取模。
这几天强度还是比较高，因为跟进度跟得有点吃力了。今天晚上眼睛疼，难受。
2025.2.12 罚时吃饱
今日歌曲：two years
今天上午VP Codeforces Round 1004 (Div. 2)，下午改Codeforces Round 1004 (Div. 1)。上午C题因为少判了一个条件，罚时吃饱了。
-
[Codeforces 2066A & 2067D] Object Identification
神奇交互题。观察到一个性质：对象
A 的答案可能是0 ，但对象B 的答案不可能是0 。若
x_1, x_2, \dots, x_n 不是1 \sim n 的一个排列，一定可以找到一个不在x 中的数k ，对其与另一个不同的数询问。若是对象A ，因为k 没有向任何点连边，所以答案一定为0 。若答案不为0 ，则是对象B 。若
x_1, x_2, \dots, x_n 是1 \sim n 的一个排列，那么找到满足x_i = 1, x_j = n 的i, j 。询问(i, j) 与(j, i) 。若是对象B ，那么两个答案应该是相等的，并且都\ge n - 1 （因为\left | x_i - x_j \right | = n - 1 ）。然而如果是对象A ，那么当n \ge 3 ，不可能同时存在一条长度至少为n - 1 的i 到j 的路径与一条长度至少为n - 1 的j 到i 的路径（因为2(n - 1) \ge n ）。综上所述，若两个答案相等并且都\ge n - 1 ，则是对象B ，否则是对象A 。按照题解模拟即可。 -
[Codeforces 2066B & 2067E] White Magic
这题似乎挺简单的，只是赛时看了一眼但是没多想。
首先可以注意到，没有
0 的子序列一定是合法的，有两个及以上的0 的子序列一定是非法的。所以要么选所有非零元素，要么选所有非零元素与一个0 。若是选一个
0 ，显而易见，选最左侧的0 是最优的。于是判断这么选是否合法即可。 -
[Codeforces 2066C & 2067F] Bitwise Slides
很有意思的 DP 题。
我们根据题意可以得出，对于时刻
i ，记sum_i = \oplus_{j = 1}^i a_j ，有P \oplus Q \oplus R = \oplus_{j = 1}^i a_j 。于是对于某个时刻，有这三种状态：\{sum_i, x, x\},\ \{x, sum_i, x\},\ \{x, x, sum_i\} 。设dp_{i, x} 表示这三种状态的情况数，经过推导（具体过程略），可以得出dp_{i, sum_{i - 1}} = 3 \times dp_{i - 1, sum_{i - 1}} + 2 \times dp_{i - 1, sum_i} 。发现可以滚动。由于值域较大，用 map 维护 DP 即可。 -
[Codeforces 2066D1] Club of Young Aircraft Builders (easy version)
有趣的组合数学题。
因为下面的楼层并不会影响上面的楼层，所以从下往上考虑。对于某一个高度，丢飞机的次数最多为
c ，假设它实际丢k 个，则有c \choose k 种情况。所以设dp_{i, j} 表示到了第i 层楼，已经丢了j 个飞机的情况数。有转移方程dp_{i, j} = \sum_{k = 0}^ c {c \choose k} \cdot dp_{i - 1, j - k} 。答案为
dp_{n, m} 。直接 DP 即可。扩展：求证答案为
nc - c \choose m - c 。
今天晚上略水……没做题。但是今天一天综合下来……还将就吧。
2025.2.13 笑点解析
今日歌曲：evermore
今天 jmr 终于回来了。
今天学习了李超线段树。
-
[洛谷 P4097] 【模板】李超线段树 & [HEOI2013] Segment
刚开始学李超线段树，觉得挺简单的。其实它跟吉司机线段树有点像，只是维护的东西要少一些，并且代码更好写。
对于每个节点，考虑维护在它中点处的最高线段编号，那么用类似于吉司机线段树区间取
\mathrm{max} ：若当前线段完全优于原有线段，那么直接替换；若当前线段完全劣于原有线段，那么直接舍弃；若当前线段与原有线段有交点，那么递归更新当前线段较大的那一段。对于查询，直接把路径上所有的线段取\mathrm{max} 即可。时间复杂度O(n\log^2n) -
[洛谷 P4069] [SDOI2016] 游戏
纯堆码量的题。首先这题一眼树链剖分，一眼李超线段树。这题算是很基础的树剖，只是套的是李超线段树。
于是 LCA + 树剖 + 李超线段树 就算是码量炸弹了。也许树剖都这样，只是我没怎么写过。所以……先把模板题写了再说。
- [洛谷 P3384] 【模板】重链剖分/树链剖分
第一道真正意义上的树剖。之前倒是写过一个有点树剖思想的贪心（但那个好像是长链剖分）。
一共交了四发，笑点解析：前三发线段树没 pushup。由于当时另外没找到问题，于是我严重怀疑是线段树的问题。然后用那个线段树，写了一个线段树的板子，一测挂了，才发现是没写 pushup，糖丸了。
第一次写树剖，稍微参考了一下题解代码，但整体还是自己在写。树剖其实挺好理解的。
写完模板题，该写这道题了。这道题从下午就开始写，一直调到晚上都没调出来，只有明天再补了。
今天
今天晚上
2025.2.14 绝世好题
今日歌曲：Red Wine Supernova
今天%你赛，
-
B - permutation （[Codeforces 1827B2] [加强版] Range Sorting (Hard Version)）
绝世好题之神秘计数（？）题。
又是一道正难则反。容易发现，答案为：
\sum_{i = 1}^n (i - 1) \cdot (n - i + 1) - \sum_{i, j, k}^{1 \le i \le j \le k \le n} [\max_{p = i}^j a_p \le \min_{p = j + 1}^k a_p] 考虑枚举
a_x 满足a_x = \max_{p = i}^j a_p ，那么a_x \le \min_{p = j + 1}^k a_p 。显而易见，a_{j + 1} 是a_x 右侧第一个比它大的数，那么i \in [p + 1, x], k \in [j + 1, q - 1] ，其中p, q 满足a_p 是a_x 左侧第一个比它大的数，a_q 是a_{j + 1} 右侧第一个比a_x 小的数。维护即可。这题……题解给的用 set 维护，可惜常数太大，被
\mathrm{yishu2} 卡掉了。他又给了个链表的实现，不想看，于是自己开始研究。由于要求的值都是最近的最大/最小值，所以考虑使用单调栈维护。
j + 1 与p 都非常好求，可是如何求q 是个问题。当时做这道题的时候自己没想出来，后来看原题题解区才懂。做法是，对于前文所提到的
i, j ，维护n 个集合S_i ，满足\forall i \in S_{j + 1} 。接下来倒序遍历a ，对于每个i ，顺序枚举j \in S_i ，将单调栈中\gt a_j 的数弹出，栈顶元素即为q 。在将每个j 操作完后，将a_i 加入单调栈。正确性证明如下（部分摘自原题题解）：记
(x, j + 1) 表示查询j + 1 右侧第一个比a_x 小的数。（x, j 含义同上。）若这个询问弹出了a_l ，那么(x' \gt x, j + 1) 的答案显然不为l 。现在需要证明(x', (j + 1)' < (j + 1)) 的答案不为l 。-
若
(j + 1)' \lt x ，因为a_x \lt a_l ，所以x 可以作为答案，答案不可能是l 。 -
若
(j + 1)' = x ，因为a_{x'} \lt a_{(j + 1)'} = a_x \lt a_l ，所以答案不可能是l 。 -
若
x \lt (j + 1)' \lt (j + 1) ，那么a_{(j + 1)'} \lt a_{x} ，否则a_x 右侧第一个比它的的数不可能是a_{j + 1} ，所以a_{x'} \lt a_{(j + 1)'} \lt a_x \lt a_l ，答案不可能是l 。
终于证完了。按上述步骤维护即可。
这题本来就有一定的思维难度。如果用单调栈，这道题的思维难度就更高了。如果用有的数据结构（比如 set），倒是好想好写，可是
\mathrm{yishu2} 卡常。 -
因为今天一下午加晚上一直苦攻 T2，所以昨天的题还没来得及补。
今天写得很晚了，准确来说已经第二天凌晨了。今天就到这里。
2025.2.18 无处不在
今日歌曲：I Forgot You Existed
“我无处不在。”——
\mathrm{yishu2}
今天在改游戏那道题，最终决定重构！
2025.2.20 笑点解析
今日歌曲：The Archer
今天还是在改游戏，最后终于还是改出来了。笑点解析又来了。
-
在
dfs1 里计算了dfn 。 -
-
另外还有一些很糖的低级错误，比如右儿子写成
p << 1 之类的。
2025.2.22 显而易见
今日歌曲：wish you were gay
- 欧拉定理
a^{\varphi(n)} \equiv 1 \mod n - 满足
\gcd(i, n) = m 的数的个数\Leftrightarrow 满足\gcd(i, \frac n m) = 1 的个数\Leftrightarrow\ \varphi(\frac n m) 。 -
\sum_{i \in [1, n] \land \gcd(n, i) = 1} i = \frac{n \cdot \varphi(n)} 2 (n \ne 1)
利用以上结论即可完成：
- [HDU 2588] GCD
- [51Nod 1040] 最大公约数之和
- [UVA 11426] GCD - Extreme (II)
- [洛谷 P1891] 疯狂 LCM
-
[Codeforces 1149D] Abandoning Roads
CF 3000* 远古题，洛谷黑，所以也算是首黑吗。
这题复杂度鬼能想出来。
首先先把重边断掉，这样就会形成若干个连通块。将这些连通块“缩点”之后，用 dij 做新图的最小生成树即可。具体地，设
dp_{i, st} 表示当前在第i 个点，已经到达的连通块为st 的最短路径。显然每个连通块只会被访问一次，所以复杂度是O(2^nm\log 2^nm) 的。注意到当一个连通块的大小\le 3 时，若先离开这个连通块再回到这个连通块，至少要经过2 条重边，而走连通块内部只需要最多2 条轻边，所以显然不需要考虑这个连通块，因为跑 dij 的时候显然会选择走连通块内部而不会重复经过。那么连通块数量被优化到了\frac n 4 ，时间复杂度2^{\frac n 4}m \log 2^{\frac n 4}m 。
2025.6.30
今日歌曲：Down Bad
昨天终于也是稳 1= 了。
这高中语文老师还是非常正常，但是这高中英语老师是比我还抽象。
今天补题。
-
[Atcoder ARC180D] Division into 3
很久之前一场模拟赛的题了。
一件显然的事情，就是一个区间的最大值
mx 一定会做出贡献。若mx 放在第二段，那么当第一段与第三段的长度为1 时可以取到最小值，用 ST 表维护即可。若mx 放在第一段，那么当第二段长度为1 可以取到最小值。设x = \min_{i = l}^r i \cdot [a_i = mx], f_i = a_i + \max_{j = i + 1}^r a_j ，那么答案即为mx + \min_{i = x + 1}^{r - 1} f_i 。将询问离线再用单调栈与线段树维护f_i 即可。若mx 放在第三段，则与放在第一段类似。 -
[洛谷 P6864] [RC-03] 记忆
这道题显然是之前记过的，今天终于补了。
2025.7
2025.7.1 好的标题
为什么你不写标题了呀？——@_O_vO
因为没想到好的标题。——@Getaway_Car
另外，注意到，我一月到六月的日祭数量如下：
| 月份 | 数量 | 有标题数量 |
|---|---|---|
我们的日祭正在蒸蒸日下！
-
[Codeforces 1610G] AmShZ Wins a Bet
CF 3300* 远古题，洛谷黑，所以也算是第二道黑吗。
赛时想到了每次删除的是一段合法的括号序列，可是竟然连最基本的 DP 都没想到，how sweet！
考虑倒序做，设
dp_{i} 表示[i, n] 的答案，那么它可以由s_i + dp_{i +1} 与dp_j 转移而来，其中j 是能与i 匹配的第一个位置。时间复杂度O(|s|^2) 。发现比较字符串还是太慢了，所以考虑使用倍增与哈希实现字符串比较，具体实现类似于树上跳 LCA，一直跳直到
j 跳到边界或者s_i \ne s_j ，即可知道两者的大小关系。
2025.7.2
-
[CS Academy] Sugarel in Love
我还是太唐了，这样的唐题都不会。
设
dp_{i, 0/1/2} 表示i 的子树中，i 目前度为0/1/2 的最大答案。直接转移即可。 -
[CS Academy] Divided Kingdom
对于任意两条相邻的边
u 与v ，答案不会超过w_u + w_v ，因此可以初步确定答案上界p 。另外，看到最小值的最大值，很容易想到二分。二分答案x ，那么有对于任意在同一集合内的a, b ，满足dis(a, b) \ge x 。转化一下，即对于任意a, b 满足dis(a, b) \lt x ，都有a, b 不在同一集合内。那么我们可以把所有满足dis(a, b) \lt x 的边a \leftrightarrow b 建出来，当且仅当新图是一个二分图，x 合法。此时时间复杂度为O(n^3 + n^2\log m) 。又注意到，对于新图中两个点a, b ，存在关系dis(a, b) \lt x \le p ，由于p 是原图中相邻两条边权值和的最小值，而dis(a, b) \lt p ，这意味着a, b 一定在原图就已经相连。所以只需要从原图上把满足dis(a, b) \lt x 的边拿出来建为新图即可。时间复杂度O(m \log m) 。
2025.7.3
-
[Codeforces 407D] Largest Submatrix 3
一道唐题，可是竟然不会。
设
dp_{u, l, r} 表示下界为u 、左界为l 、右界为r 的最小上界。注意到dp_{u, l, r} \le \min\{dp_{u - 1, l, r}, dp_{i, l + 1, r}, dp_{i, l, r - 1}\} ，发现在这基础上，还需要满足a_{u, l} \ne a_{i, r}, a_{u, r} \ne a_{i, l} 。维护lst_{i, j} 表示第i 列中j 最后一次出现的位置即可。注意要特判一下l = r 。 -
[Atcoder ABC176F] Brave CHAIN
第一眼感觉这个题好像来财啊。我们把每次操作剩下的左侧的两张牌叫做手牌。考虑什么时候能够产生贡献。
-
三张新牌相同。此时手牌状态不变。
-
有两张新牌相同，且手牌中有一张与它们相同。此时会将手牌中的相同的那张打出，并换来新牌中不同的那张。
-
两张手牌相同，且新牌中有一张与它们相同。此时会打出两张手牌，并换来新牌中不同的两张牌。
上面三项对应的状态更新如下。（
\leftarrow 默认取\max ）- 直接全局
+1 。 - （假定
x = y \ne z ）dp_{i, z} \leftarrow dp_{x, i} + 1 - （假定
x 与两张手牌相同）dp_{y, z}\leftarrow dp_{x, x} + 1
引入通配符
0 ，表示f(0) = \max\{f(x)\} 。以下是无贡献的状态更新。（x, y, z 可相互替换。）-
dp_{i, x} \leftarrow dp_{i, 0} -
dp_{x, y} \leftarrow dp_{0, 0}
容易发现每一轮一共只有
O(n) 级别的状态更新，所以我们只需要在当前状态的基础上修改即可。另外注意，以上所有操作都是同时进行，所以需要提前存储操作信息。时间复杂度O(n^2) 。 -
2025.7.4
-
[洛谷 P2568] GCD
推式子即可。并不想打公式，
详见原题题解。 -
[Codeforces 1114F] Please, another Queries on Array?
看题的时候没看到a_i, x \le 300 ，所以想了一会儿直接去看题解了。要维护区间乘与区间积的欧拉函数，发现区间积可能很大，不能直接分解质因数。所以考虑维护原数的质因子，发现
\le 300 的质数个数恰好是62 ，可以用long long维护。而一些数的乘积的质因子状态，即其中每个乘数的质因子状态的或和。区间修改也是类似的道理。
2025.7.6 蒸蒸日上
这已经是七月的第
-
[Codeforces 2119D] Token Removing
神秘 DP。题解。
2025.7.7
今天 VP Codeforces Round 1036, Div. 1 + Div. 2。
-
[Codeforces 2124E] Make it Zero
沟槽的构造题，并不想记严格的证明。大概就是找到一个位置
pos 满足s_{pos - 1} \lt \frac{s_n}2 \le s_{pos} ，然后分为[1, pos), \{pos\}, (pos, n] 三段，设三段的和分别是x, y, z ，我们只需要找到一个w 使得(x - w) + (z - w) = y ，接下来可以在两步内解决。再把前两步合并，就变为了第一段清空，第二段减去x - w ，第三段减去w ，剩下的就是第二步。
2025.7.8
模拟赛挂了
第四题不会，所以也没什么题需要改。
2025.7.9
-
[Atcoder JOISC2014J] 電圧
要使这条边端点颜色相同，且删掉这条边后图形成二分图，那么这条边在所有奇环中，且不在任意一个偶环中。
考虑建 DFS 树。对于树边，我们可以通过树上差分维护出当前边属于的奇环与偶环数量。对于非树边，根据奇环数量来讨论：若有且仅有一个奇环，则该非树边合法；若有多个奇环，且存在一对奇环没有交集，那么没有树边合法；若有多个奇环，且这些奇环都相交，那么必定会形成更大的偶环，那么没有树边合法。综上所述，只用讨论合法的树边数量，并特判奇环是否只有恰好一个即可。
2025.7.10
-
B - 树
题意转化后即动态维护树的直径，具体需要支持向树中加点。
考虑当两棵树合并的时候直径会怎样。容易发现，新树直径的端点一定由原树直径的端点产生，一一判断即可。考虑使用线段树维护区间直径，支持单点修改即可。
2025.7.12
线段树合并要把我的左脑和右脑合一起了。
这篇日祭是线段树合并学习笔记，未来会有补充。
线段树合并顾名思义，就是把两棵线段树的信息按照特定的规则合并起来，一般与动态开点配合使用。
线段树合并常用于优化 DP，尤其是树形 DP（与 DAG 上的 DP），用来优化 DP 转移。（或者是一些需要在树 / DAG 上进行信息转移的东西。）
比如一个树形 DP 的转移方程如下：
我们需要将儿子的信息转移到父亲上，而每个节点存储的又是一个数组，常规的做法是一一合并，转移的时间复杂度为
而对于一些转移方程，我们会发现合并信息的操作可以用线段树合并来优化。于是我们就将转移的时间复杂度优化为了
具体的，假设现有
可这时我们会发现，开
于是你就写出了线段树合并。
-
[Vani有约会] 雨天的尾巴 /【模板】线段树合并
首先可以把区间修改通过差分变成单点修改。
对于
u ，我们需要维护它每种救济粮的数量与最多的救济粮的种类，显然使用线段树维护。因为我们做了树上差分，所以 DFS 的时候要做一次树上前缀和，即将dp_u 和\forall v \in son(u), dp_v 合并起来。于是就做完了。时间复杂度
O(n \log n) ，但常数极大。另外记一种树链剖分的做法，其实就是离线的树剖。
先正常树剖一下，然后你就会得到
\log n 个 dfn 序连续的区间。由于是离线，所以可以用差分标记这些区间。
所有操作结束后，用权值线段树进行一次前缀和即可。
时间复杂度
O(n \log^2 n) ，常数极小。
2025.7.13
-
A - [UVA 12170] Easy Climb & [SPOJ CCROSS] Cross Mountain Climb
赛时基本想到了但是没做出来。显然有
O(nV) 的朴素 DP（单调队列优化）。可以感知到，
\forall i \in [1, n], \exists j \in [1, n], h_i' \equiv h_j (\mathrm{mod}\ d) 。（我也不知道我赛时是怎么感知到的，总之就是感知到了。）即，
\forall i \in [1, n], \exists j \in [1, n], h_i' \in \{h_j + kd \mid j \in [1, n], k \in [-n, n]\} ，那么有效的值的个数就来到了O(n^2) 。（为什么我想到了又没做出来呢？因为我思考的时候把k 取到[-10^9, 10^9] 了，然后就不会了。）进行一下离散化再 DP 即可。
-
B - [黑暗爆炸 4160] Exclusive Access 2
赛时写了一个没有正确性的乱搞做法，得了 70 pts。
我们可以把原题转化一下，看成把原图分成若干层（若干部，更严格的说法是用反链覆盖原图，即 dilworth 定理），使得每一层内两个点互不直接相连，求最小层数。发现就是求图的色数。先
O(n2^n) 预处理一个子集是否有直接相连的元素，再O(3^n) 做 DP 即可。
2025.7.14
-
[洛谷 P3623] [APIO2008] 免费道路
一个做法是直接取
k 条鹅卵石路。可是发现这么做没有正确性。
因为容易发现有一些鹅卵石路是必选的。
那么我们可以先做一次 kruskal，并且先选水泥路，再选鹅卵石路。第一次被选中的鹅卵石路就一定包含了必选的鹅卵石路。
所以接下来只用再做一次 kruskal，先取够
k 条鹅卵石路，再取水泥路。 -
[洛谷 P8386] [PA 2021] Od deski do deski
看了题解觉得很简单但是自己就是做不起的 DP。
首先容易发现一个合法的序列一定可以表示为若干个首尾相同的串相连。
换句话说，我们可以在一个合法的序列后面再加上一个首尾相同的串以得到一个新序列。
再换句话说，对于任意一个序列，我们可以通过在末尾增加一个特定的元素，让它与原序列中的某个相同元素匹配成一个区间，以让新序列合法。
考虑 DP，设
dp_{i, j, 0/1} 表示考虑了[1, i] ，当前有j 个左端点（新数与它们匹配后能使新序列合法，并且它们被匹配一次后依旧可以被匹配），当前序列是否合法的方案数。那么有四种 DP 转移。答案是
\sum_{j = 1}^n dp_{n, j, 1} 。注意到j \le i ，所以时间复杂度是O(n^2) 。 -
-
HJJOI Day2 A 堆
先转化一下题意，看成先插入元素再删除元素。注意到，如果插入的元素是当前的最大元素，那么直接删除它；在这样的条件下，其它被删除的元素一定是单调不增的。所以只需要一个桶与一个指针维护当前的最大元素即可。
-
[洛谷 P3960] [NOIP 2017 提高组] 列队
题解。
-
[LOJ 6029] [雅礼集训 2017 Day1] 市场
挺有趣的势能线段树。
看到取模、开根这一类运算容易想到势能线段树，除法也是。但这道题的难点就在于难以看出是哪个数据最终会趋于不变。
动用人类智慧，发现是极差。对于加法操作，并不会改变极差，而除法至少可以让极差减半，即在
\log V 次内变为0 。先写一个正常的线段树，然后单独实现除法操作。
注意到，当一个区间的极差为
0 即所有元素相同时，区间除法相当于区间加法，所以直接做一个区间加标记即可。另一个可以像上面这样处理的情况是，最初极差为
1 ，操作后极差依然为1 ，此时区间除法与区间加法也是等价的。单独讨论一下上述两种情况并直接返回，其它情况继续递归下去即可。
时间复杂度是
O(q \log n \log V) ，不会证。在 sjx 的讲义中，还讨论了最初极差为
1 ，操作后极差为0 的情况，此时区间除法等价于区间覆盖，所以似乎还要单独实现区间覆盖，导致代码更屎，所以干脆不讨论这种情况，直接暴力递归即可。（甚至可能会赢过两个 lazy tag 的常数。）
2025.7.15
-
[洛谷 P8990] [北大集训 2021] 小明的树
终于也是洛谷首黑了。这题的转化好妙啊。
美丽的定义的转化如下：对于任意一个白点，它的子树中都是白点
\to 对于任意一个黑点，它的父亲一定是黑点\to 所有的黑点构成一个连通块\to 黑点个数减去黑边个数等于1 。当一棵树是美丽的，因为所有黑点构成一个连通块，所以白色连通块的数量等于黑白边的数量。于是我们就可以用一棵线段树维护每个时刻的黑色连通块数量（即黑点个数减去黑边数量）与白色连通块数量（即黑白边数量）。对于每一条边，容易处理出它在哪个时间段是一条黑边（可以给黑色连通块数量带来-1 的贡献），在哪个时间段是一条黑白边（可以给白色连通块数量带来+1 的贡献），当然改边也是容易处理的，实际就是撤销一条边再加一条新边。这个时候还缺了一步。我们要求的并不是每个时刻的白色连通块数量之和，而是黑色连通块数量为
1 时的白色连通块数量之和。我们可以通过维护黑色连通块数量的mn, mncnt 与当黑色连通块数量取到mn 时对应时刻的白色连通块数量之和sum 来解决这个问题。修改白色连通块数量时，我们只需要将sum 加上mncnt \cdot \Delta 即可。由于在第n - 1 个时刻（与第n 个时刻）黑色连通块数量一定为1 ，所以mn 一定为1 。 -
[QOJ 7980] 区间切割
这不是人类智慧是什么？
先考虑离线下来，记
time_i 表示位置i 被切割的时间，那么依次处理区间[1, n] ，就可以做到实时记录time 。对于一个区间，发现它在随机数据下，长度会快速减小，且最多被切割\log m 次，所以可以每次直接找到当前区间内time 的最小值，然后从最小值对应位置处切割。但是对于非随机数据，一个区间可能会被切割m 次（从左往右切），显然不能沿用上面的做法。区间被切割的次数多的原因是有许多切割的位置都很靠近端点，导致长度减小缓慢。所以我们充分发扬人类智慧，对于一些靠近端点的切割操作，直接更新端点；对于一些处于区间中部的切割操作，再沿用上述做法。可是“靠近端点”具体又应该是处于区间的什么位置呢（比如前
\frac 1 4 ）？或者说“区间中部”的长度应该取到多少，才能既保证正确性又保证时间复杂度呢？若中间块太长，则会导致区间长度减小依然缓慢，而当中间块较短时则可保证区间长度较快减小。所以我们要尽可能最小化中间块长度。若中间块太短，在进行一系列对区间两端的切割操作后，我们并不能保证中间块一定会被保留下来；而当中间块长度大于两侧长度时，在进行一系列对区间两端的切割操作后，我们一定可以保证中间块被保留。综上所述，我们只需要将区间三分即可。
具体实现上，我们需要一棵线段树维护
time ，它需要支持单点修改、区间查询（查询区间中间段的最小值）、查询给定位置左 / 右侧第一个小于给定值的位置（查询两端的切割情况）。对于第二类查询，需要使用线段树二分。对于区间的迭代，只需要按题解模拟即可，先直接更新左右端点，再进行区间切割。时间复杂度O(n \log^2 m + m \log m) 。 -
[Codeforces 461B] Appleman and Tree
设
dp_{i, 0/ 1} 表示考虑到第i 个点，当前点是否与黑点在一个连通块的方案数。转移时直接考虑是否删除当前边即可。 -
[洛谷 P3177] [HAOI2015] 树上染色
直接考虑染色对答案的贡献。设
dp_{i, j} 表示考虑到第i 个点，以当前点位根的子树中有j 个黑点的贡献。做一个树上背包，价值是以儿子为根的子树与其他节点能产生的匹配次数（即经过当前边的次数）乘以当前边的权值。注意转移时要控制好变量的上下界，否则会被卡成O(n^3) 。
2025.7.16
踩一脚 2025.1.17，现在比那时候还是有了一些进步。（现在很难想象之前有段时间天天都只考几十分，接近垫底，但是竟然没觉得什么。）
怎么说呢，教练和家长也都给我聊了好多次了，也是该到努力的时候了。我之前确实学习就没有真正用过全力，所以今天教练说我潜力很足，我也这么认为。只是说面临的困难也挺多的，比如我心理上的一些问题。我无法解决，所以只有尝试不想那些事情，尝试逃避问题。
今天上午考试，一道不会。下午应该是因为天气比较热，所以人有些浮躁，状态不是特别好，效率很低，听课也没怎么听进去，一天只做了一道题，也是成为了 HJJOI 集训期间的前缀最小值。
-
[Codeforces 1967D] Long Way to be Non-decreasing
就当是学习基环树了。
赛时看出来这题与基环树有关，可是居然没看出来是二分（打脸）。
二分答案
x ，转化为判定性问题，我们需要对a 中每个元素操作最多x 次使其单调不降。由于目标是单调不降，所以只需要使用一个变量lst 表示当前a 中的最后一个元素，那么一个新元素就需要在x 次操作以内变为一个不小于lst 的数。将lst 从小到大枚举，找到最小的lst 满足这个新元素可以在x 次操作以内变为lst ，若lst \gt m 则无解，否则有解。那么现在就转化为了计算一个数在几次操作后能变为另一个数。对于所有
i \to b_i 建图，此时会形成一个内向基环树森林，我们只需要计算基环树上两点的距离，就是一个数转化至另一个数的操作次数。对于基环树的处理，可以使用并查集维护连通性，形成环时忽略当前边，使其形成一棵树。计算两点距离时需要分讨一下两点的位置关系。
2025.7.17
这两天状态不好，所以 7.17 和 7.18 都没做什么题，日祭也是 7.19 才补的。
-
[洛谷 P5903] 【模板】树上 K 级祖先
长链剖分的主要用法就是求树上
K 级祖先和优化 DP。优化 DP 就类似于 dsu on tree，只是一个与树的大小有关，一个与树的深度有关。求树上
K 级祖先的方法如下：树剖时对于长度为len 的链，需要预处理出链顶的1 \sim len 级祖先与1 \sim len 级儿子（即链中元素）。另外还需要预处理出2^x 级祖先。对于每组询问，先向上跳2^{\log K} ，此时当前点所在长链的长度至少为2^{\log K} 。接下来再跳到当前链链顶，再向下或向上把剩下的跳了。
2025.7.18
-
[P4719] 【模板】动态 DP & [P4751] 【模板】动态 DP（加强版） & [P5024] [NOIP 2018 提高组] 保卫王国
三倍经验是个好东西。
并不想记具体的过程，所以就大概记一下。
对于 P4719，可以先写一个朴素的 DP。对于每一次修改，就需要更新从当前点到根路径上的每个点。因为是路径更改，所有考虑
熟练剖粪树链剖分。尝试把原来的 DP 方程写成一种神秘的矩乘形式，然后对于每一次修改就变成了修改路径上轻边的转移方程（矩阵），答案就是整棵树重链上的矩阵的乘积。对于 P4751，我们只需要使用动态开点线段树，对于每一条重链单独开线段树，这样可以减少线段树的查询次数，可以优化至少
\frac 2 3 的常数。对于 P5024，容易注意到最小覆盖集 = 全集 - 最大独立集，那么就可以直接做了。对于修改操作，若要强制选则将权值设为极小值，否则将权值设为极大值。注意算出来的答案是改变权值后的答案，所以输出时还要稍微处理一下。
2025.7.21
-
[洛谷 P8352] [SDOI/SXOI2022] 小 N 的独立集
DP 套 DP 板子。设
dp_{u, i, j} 表示考虑到点u ，强制不选的答案为i ，不强制不选的答案为i + j ，直接转移即可。（其实是我不想写。） -
[洛谷 P5904] [POI 2014] HOT-Hotels 加强版
长链剖分优化 DP 板子。
对于原题，容易写出一个
O(n^2) 的 DP，发现 DP 数组的大小与深度有关，所以进行长链剖分即可。
2025.8
这个月的日祭直接写一起了，基本都在补题。
注意到 7 月份后来状态不好。
-
[洛谷 P4198] 楼房重建
考虑用一棵普通线段树维护，每个节点维护区间的最大值与区间内好的序列的长度，push up 的时候需要写一个类似于线段树二分的东西，时间复杂度
O(n \log^2 n) 。 -
[洛谷 P9824] [ICPC 2020 Shanghai R] Fountains
复杂度好神秘的一道题。
自己写写不清楚，所以干脆看题解吧。 -
[洛谷 P6189] [NOI Online #1 入门组] 跑步
显然可以 oeis。本题就是正整数拆分问题。考虑正整数拆分的做法。一种 DP 是设
dp_{i, j} 表示用了1 \sim i ，当前和为j 的方案数，转移是dp_{i, j} = dp_{i - 1, j} + dp_{i, j - i} 。另一种 DP 是设dp_{i, j} 表示选了i 个数，当前和为j 的方案数，转移是dp_{i, j} = dp_{i - 1, j - 1} + dp_{i, j - i} 。发现第一种 DP 与拆分的数的值域有关，第二种与拆分的数的数量有关。所以考虑根号分治，对于\le \sqrt n 的数进行第一种 DP，其它的进行第二种 DP。 -
[CWOI 0819 B组] C - 盲盒流水线
注意到这场因为 B 屎一样的题面搞乱了节奏？（不要给自己找借口了。）不过要是 JDS 不提醒我 A 可能要挂完。
题意是区间背包。因为是区间，容易想到用数据结构维护。注意到背包可以
O(m) 合并，那么写一个普通线段树的时间复杂度是O(n \log n + q m \log n) ，空间复杂度是O(n \log n) 。慢的原因是合并次数太多，所以考虑减少合并次数。发现这个过程是静态的，所以选择猫树。可是发现直接猫树的空间复杂度是O(n^2 \log n) ，所以需要把询问离线下来，每个区间单独处理即可。 -
P13736 [JOIGST 2025] 日本浮现 / Japan Emerges
气死我了怎么绿题都场切不了。（注意到可能是做提高组模拟赛有点膨胀导致的。）
看到连通立马想到并查集（为啥我没立马想到），看到最小立马想到二分答案转化为判定性问题，判定的时候按题意模拟即可，如果两个块会相连就合并起来。
-
[洛谷 P13680] [IAMOI R2] 未送出的花
注意到祖先的盛开度一定比孩子大，因为如果交换两个点的盛开度会导致答案不增。所以对于每个点，它的美丽度取的点的位置是固定的，所以可以统计对于每个点，它的盛开度会被作为多少个点的美丽度（记作
cnt_u ）。若我们选择k 朵花送出，相当于要选若干个点使得\sum_{u \in S} cnt_u \ge k ，最大化\min_{u \in S} w_u ，发现S 一定是一个包含根的连通块，所以直接树上背包即可。 -
[CWOI 0822 B组] B - 美丽值
题意略。容易想到拆贡献，考虑
[i, i + 1] 一段会被计算多少次。设n 中有j 个数\le i ，剩下的n - j 个数\gt i + 1 ，那么[i, i + 1] 会被计算\min(j, n - j) 次。接下来考虑有多少个序列满足上述条件。首先从n 个数中选j 个数钦定为\le i ，那么j 个数就可以任意在[1, i] 中生成，剩下n - j 个数同理。所以总答案是\sum_{i = 1}^{v - 1} \sum_{j = 0}^n \min(j, n - j) \cdot \binom n j \cdot j^i \cdot (n - j)^{v - i} 。 -
[Atcoder ARC101C] Ribbons on Tree
考虑容斥（？，注意到我不会容斥，是怎么考虑到的），答案为
\sum_S (-1)^{|S|} \cdot f(S) ，其中f(S) 表示强制断开的边集为S 的方案数。注意到断开若干条边后，形成了若干个独立的连通块，那么每个连通块的方案数就是\prod_{i = 1}^{\frac n 2} (2i - 1) （当n 是偶数时）。所以直接树上背包即可。 -
[Atcoder ARC153D] Sum of Sum of Digits
好神秘的 DP。
发现难点主要在于进位。设
dp_{i, j} 表示考虑到第i 位，上一位有j 个数向这一位进了位，目前答案的最小值（不包含当前这一位）。对于每一位，先对a 按当前这一位从大到小排序，那么进位的数字一定是a 的一个前缀。接下来就是直接转移，枚举进位个数、x 当前这一位的值，然后统计当前数位的和与进位个数，再转移到下一位即可。 -
[CWOI 0824 B组] A - town
题意是将树分为若干个连通块，要求每个连通块的权值的异或和为
x ，求方案数。显然容易想到做树上背包，并且记录当前未闭合连通块的异或和。发现未闭合的连通块的异或和一定是
xorsum 或xorsum \oplus x ，所以只用设两个状态。需要特判x = 0 （赛时被这个 Corner Case 创飞了。） -
[CWOI 0824 B组] B - str
很显然的 DP，处理 LCP 即可。但是赛时写的什么 KMP 处理 LCP？什么东西？
-
[CWOI 0824 B组] C - perm
什么惊人的注意力。
显然与置换环有关。把每个置换环拿出来，设大小为
sz_i ，那么答案就是\frac{n!}{\prod sz_i !} \cdot \prod f(sz_i) ，其中f(x) 表示大小为x 的置换环的解数，然后出题人注意到f(x) = x^{x - 2} ，特别地，f(1) = 1 。
Codeforces Round 1044 (Div. 2)
Link
-
D - Chicken Jockey
Solution.
-
E - I Yearned For The Mines
发现当树是一条链时是容易的（废话），所以考虑先使用最多
\lceil \frac n 4 \rceil 次2 类操作把树分为若干条链，再用n 次操作检查每一条链。考虑如何在限定次数内将树分为链。我们尝试对树上的点分为以下三类：- 链的端点；
- 链的中间点；
- 执行
2 类操作的点。
我们可以通过一次 dfs 来确定点的类型。具体地，对于点
u ：- 若
u 的儿子中存在一个中间点，或存在至少3 个端点，那么u 是操作点； - 否则，若
u 的儿子中恰好存在两个端点（且不存在中间点），那么u 是中间点； - 否则，
u 是端点。
于是我们就找出了需要执行
2 类操作的点集。 -
F - Flint and Steel
令
l_i = i - e_i + 1, r_i = i + e_i - 1 。容易想到一个朴素 DP：设dp_i 表示炸死[1, r_i] 的苦力怕最少需要引燃多少只苦力怕，有转移dp_i = \min_{j \lt l_i \lt r_j \lor l_j \lt l_i \lt j \lt i} dp_j + 1 ，时间复杂度O(n^2) 。考虑优化，设seg_i 表示炸死[1, i] 的苦力怕最少需要引燃多少只苦力怕，那么 DP 转移就可以通过线段树来优化，实际复杂度O(n \log n) 。
Codeforces Round 1045 (Div. 2)
Link
-
D - Sliding Tree
在 CF Div. 2 D 放极弱的样例的出题人，愿你们的母亲在天堂相遇。
根据直觉容易想到与直径有关，然后就会自然地想到移动直径上的每一棵子树，然而这样是错误的。正确的做法应该是把直径的一端移到子树上，那么操作次数就应该是
n - len ，其中len 为直径的长度。至于为什么这样是最优的应该口胡一下可以怔出来，但是不想怔了。 -
E - Power Boxes
实则并不难，只是赛时死磕 D 去了。赛后自己补出来了，虽然用时有点久。
设从
i 开始的弹跳次数为c_i ，那么显然有c_i = c_{i + a_i} + 1 ，初始值是c_{n + 1} = c_{n + 2} = 0 。显然会倒着询问。对于i ，若c_{i + 1} \neq c_{i + 2} ，那么我们询问c_i 即可得到a_i 的值。否则，我们可以直接推出c_i = c_{i + 1} + 1 ，但并不知道a_i 的值。注意到，若i \gt 1 ，因为c_i = c_{i + 1} + 1 \neq c_{i + 1} ，我们一定可以通过一次询问直接确定a_{i - 1} 。接下来，我们只需要交换i - 1 与i ，原来的第i 个盒子现在成为了第i - 1 个盒子，又有c_i' \neq c_{i + 1}' ，所以我们可以通过一次询问直接确定a_{i - 1}' 。若i = 1 ，交换1 与2 即可。根据上述过程易证需要\lceil \frac {3n} 2 \rceil 次询问。
Codeforces Round 1046 (Div. 1, Div. 2)
Link
-
B - For the Champion
被随机区分导致掉大分了呜呜呜。
注意到赛时就想到了移到角落，然后就不会了，男蹦。
移到两个角落就可以得到
X + Y 与X - Y 了，然后就做完了。 -
C - By the Assignment
发现一个图是好的的充要条件是，每个环上所有点的点权都应该相同，这等价于每个边双中的点的点权应该相同。特别地，奇环上所有点的点权都应该是
0 。所以我们只用找出每个边双联通分量，判断其中已确定点的点权是否全部相同，并且是否存在奇环即可。 -
D1 & D2 - From the Unknown
注意到我赛时基本会 D1 了，然后饭堂了以为自己是错的？然后开始考虑优化，想到了 D2 正解的
70\% ？然后最后 D1 & D2 都没做出来？啊？设
N = 10^5 。对于 D1，容易想到的是第一次询问N 个1 ，得到W 的大致范围[l, r] ，满足2l \gt r （好像赛时就是l, r 推错了，导致没推出2l \gt r ？）。接下来要确定W 的具体值，于是考虑询问l 1 l 2 l 3 ... l (r - l)，有W = 2(r - l) - res + l 。对于 D2，考虑优化。（以下是赛时想法）发现我们没有把
res = 0 利用起来。于是考虑利用根号分治与数论分块的思想，第一次询问\sqrt N 个\sqrt N ，若res = 0 则说明W \lt \sqrt N ，否则W \ge \sqrt N 。若W \lt \sqrt N ，则考虑询问N 个1 ，此时每个W 都对应一个互不相同的res ；否则，沿用 D1 的思想即可。但是发现这样的询问次数依然可以达到N ……（以下是正解）发现以上有些数值取到\sqrt N 时不一定最优，于是重新设常量N, B 表示：第一次询问N 个B ，若W \lt B 则第二次询问B 个B 。通过暴力可以求出，当N = 11343, B = 116 时询问次数可以控制在2.5 \times 10^4 以内。若精细实现，询问次数还可以再少一点。
2025.9
:::info[鲜花 (2025.9.1)]
注意到我停课了。
另外注意到我今天上午做了三道题，下午也许是在尝试改上一场 CF 的 Div. 1 E，顺便学习了一下反射容斥。学了之后发现改不出来，于是放弃了，并开始补日祭。总之就是下午一道题都没做？啊？什么效率？但是我不是挺认真的吗？啊？
:::
MX NOIP 3
Link
-
A - Novelist
略。
-
B - Bicycle Tour
根据部分分容易想到从小到大一条条加边，并在形成环时做一个链上的 to min。于是先建出原图的最小生成树，然后树剖即可。
-
C - 数列色ぬり
题解。
-
D - DequeQL
改不动。
多校杂题选讲 20250905
Link
-
A - [NOISG 2025 Prelim] Itinerary
考虑直接把
s 的路径描到树上，计算每一条边会被经过几次，这一步可以用树上差分解决。接下来，若i 是起点，我们只用关注i 到s_1 的路径，如果在s 的基础上加上这一条路径，每条边的经过次数依然\le 2 则合法。实现上，从s_1 开始 dfs，记录s_1 到每个点的路径上的每条边的经过次数的最大值即可。 -
B - [USACO24DEC] 2D Conveyer Belt S
考虑哪些位置是不合法的，显然是环形传送带及其内部。环形传送带是容易找的，但是内部并不好找。于是正难则反，考虑从边缘开始洪水填充，能走到的位置就是合法的位置，剩下的就是不合法的位置。不过对于每个询问都搜索一遍显然会挂，所以考虑倒着处理询问，每次删掉一个传送带，若当前位置原本不合法但四连通有合法的位置，那么从当前位置再次开始洪水填充即可。
-
C - [NOISG 2025 Finals] 机器人
首先有结论，若机器人
l 与机器人r 最终停在第x 行，那么区间[l, r] 的机器人一定都可以停在第x 行，因为机器人l 到第x 行的过程中一定会经过第l + 1 到第x - 1 行，r 同理。所以可以停在第x 行的机器人一定是连续的一个区间。于是考虑对于每个i ，求出可以到达第i 行的机器人的区间，于是问题就转化为了用最少的给定区间覆盖询问区间，这个问题可以用 ST 表实现。具体地，设st_{i, j} 表示从i 开始，使用2^j 个区间，能达到的最右侧的位置。 -
D - [NOISG 2023 Finals] Curtains
将询问
[L, R] 转化为，判断是否有[L, R] = \bigcup_{L \le l_i \le r_i \le R} [l_i, r_i] 。考虑先离线下来并且按r_i 排序，这样就少了一个限制。考虑使用线段树维护从每个位置i 能够完整覆盖到的最右侧的位置pos_i ，那么回答询问就变为了单点查询，增加幕布[L, R] 是对于[1, L] 区间修改。具体地，对于所有pos_i \ge L - 1 的位置i ，执行pos_i \leftarrow R 。发现这个操作难以实现，但是发现多个这样的操作可以合并（具体过程略），所以使用一棵维护 lz tag 的线段树即可。 -
E - From the Unknown (Hard Version)
略。
-
G - [HEOI2013] SAO
好神秘的树形 DP。设
dp_{u, i} 表示考虑到u 子树，且u 在子树中的拓扑序为i 时的方案数。转移时根据u, v 关系分讨，再推推式子就可以得到一个O(n^3) 的 DP，然后发现可以前缀和优化，就变成O(n^2) 的了。 -
H - Range Reachability Query
发现问题类似于传递闭包，并且似乎也只能用类似于传递闭包的做法解决。不过先考虑暴力，显然是从
u 开始 bfs，发现这样反复 bfs 太浪费了，于是考虑用一次 bfs 解决所有问题。设dp_{i, j} 表示对于点i ，u_j 能否通过[l_j, r_j] 的边到达它，这显然可以用 bitset 维护，考虑转移，发现还需要定义辅助数组f_{i, j} 表示边i 是否属于[l_j, r_j] ，它同样可以用 bitset 维护，并且可以通过差分预处理。此时对于边\displaystyle u \mathop{\to}^{id} v 就有dp_v \mid = dp_{u} \& f_{id} 。时间复杂度O(\frac{(n + m)q}{w}) ，空间复杂度O(\frac{(n + m)q}{w}) ，后者无法接受。于是考虑把q 个询问分T 次处理（或每次固定处理k 个询问），理论上时间复杂度不变，只是增加了一些常数，并且空间复杂度变为了原来的\frac 1 T 。T 取一个小常数即可。
MX NOIP 4
Link
炼屎计划。
-
A - xorseg
被 Ad-hoc 了一会儿，原因是认为满足第二个条件的区间数量是
O(n^2) 级别的，后来才反应过来应该是O(n) 或者O(n \log n) 级别的，具体的也没证。 -
B - heap
什么屎题，手写堆。
-
C - toptrees
什么唐题（虽然我更唐，赛时没写出来），直接回退背包即可。
-
D - lca
什么不可做题，不会。
多校联考 20250906
Link
-
A - string
唐题。
-
B - ball
我好唐。发现计算答案时
a_i 需要升序，但是乱序时严格更劣，所以考虑 DP，设dp_{i, st} 表示考虑了[1, i] ，当前已选的数组成的集合是st 的最大美观度，转移是容易的，但是需要高精度。 -
C - tree
我好唐，65 分部分分都不会写。显然合法的连通块需要满足大小是偶数并且每种权值出现次数不超过一半，后者转化一下就是众数出现次数不超过一半。设权值
i 出现了cnt_i 次。考虑枚举众数x ，并将众数的权值设为1 ，其余的数的权值设为-1 ，那么上述条件就又转化为了连通块的权值和应该为非正偶数，这容易用树形 DP 做出来。可是发现直接这样统计是没有正确性的，因为当枚举的众数并不是实际的众数时，连通块的权值也可能是非正偶数。于是考虑反过来，先计算大小是偶数的连通块个数，再减去其中众数出现次数超过一半的连通块个数，即权值和为正偶数的连通块个数，这样才有了正确性。又发现树形 DP 的第二维只用取到[-cnt_x, cnt_x] ，所以时间复杂度是O(n^2) 的。
:::info[鲜花 (2025.9.7)]
虽然前几天看着还有那么多日祭没写，但其实一写起来还是挺快的。（这句话好人机，好唐，但是不管了。）
另外把一个月的日祭写在一起不就不叫日祭了么，应该叫月祭（？）。
:::
Atcoder Regular Contest 205 (Div. 2)
Link
-
D - Non-Ancestor Matching
Solution。
-
E - Subset Product Problem
好妙的一道题。如果直接用桶统计有着优秀的
O(nV) 的时间复杂度。考虑优化。首先把a_i 写成p_i \ll 10 \mid q_i 的形式，使得p_i, q_i 都是 10 位整数。接下来，设cnt_{x, y} ，其中x, y 都是 10 位整数，表示\sum_{i = 1}^k [p_i \subseteq x \land q_i = y] ，那么答案就是\sum_{y = 1}^{2^{10} - 1} [y \subseteq q_k] \cdot cnt_{p_k, y} 。代码极其好写，时间复杂度O(n \sqrt V) 。
Atcoder Beginner Contest 422
Link
-
F - Eat and Ride
我好唐，只想出了一个伪的做法。容易想到拆贡献，那么设
dp_{i, j} 表示从1 走到了i ，还剩j 步没走的最小花费，转移显然，答案是dp_{i, 0} 。 -
G - Balls and Boxes
问题一原来就是背包啊，有点难绷，自己只想到了扩欧。
你说得对，问题二是生成函数，但是根号分治是个好东西。
考虑暴力，枚举
x, y ，计算\sum \frac{n!}{x!y!z!} ，时间复杂度O(\frac{n^2}{xy}) ，支持xy \ge \sqrt n 。于是现在需要一种O(nxy) 的暴力。设dp_{i, j, k} 表示x + y + z = i, x \equiv j \pmod a, y \equiv k \pmod b 的方案数，直接转移即可，支持xy \le \sqrt n 。
Codeforces Round 1047 (Div. 3)
Link
-
G - Cry Me a River
设
n, m, q 同阶。首先容易写出O(n) 的简单 DP。容易发现，如果 A 或 B 从某个点开始游戏，最终会来到一个红色点，那么我们可以认为当前点在 A 或 B 操作的时候也是红色的。将一个点染红之后，我们并不用全部重新 DP，只需要考虑它对入边的影响，如果有新的点被染红，那么再递归考虑它的影响即可。发现每个点在每种状态下只会被染红一次，所以时间复杂度O(n) 。
多校杂题选讲 20250912
Link
-
A - Towers
容易想到把最高的节点作为根，那么有权值的位置一定是叶子，且有两个叶子的权值恰好等于高度的最大值。对于每个子树，一定存在一个权值为最大值的节点不在这个子树内，所以我们只需要这个子树内存在一个叶子节点的权值大于等于这个子树内高度的最大值即可。选择权值大于等于这个子树内高度的叶子节点时，贪心地选择当前权值最大的叶子节点即可。对于根也类似，只需要选择前两大的叶子节点，将它们的权值设为高度最大值即可。
-
B - Fairy
见 電圧。
-
C - Flip Row or Col 2
才做完就升紫了。因为这题自己写得完全没有题解清楚，并且也达不到总结的目的，所以就不记了。
-
D - 01 on Tree
神秘贪心。容易发现，如果我们选了一个点，那么会贪心地把它孩子中所有的
0 选完，这样一定不劣。那么就可以理解为这些孩子与父亲“捆绑”在一起，形成了一个连通块。那么同理，我们可以用并查集维护当前的连通块，并且把所有连通块放进优先队列中，如果交换两项顺序之后逆序对个数更少则贪心地交换，这么做是有正确性的。每次取出最靠前的连通块并与父亲合并，边合并边计算贡献，直到只剩一个连通块。做完后答案就算出来了。 -
E - Wine Thief
发现直接拆贡献不好做，考虑其他做法。发现链上的独立集没什么有用的性质，然而如果是在环上，每个点的贡献次数都是相同的。于是先假定此时是在环上，但是发现会算漏
a_1 与a_n 都被选的情况。为了补上这种情况，钦定a_1, a_n 被选，那么此时要在[3, n - 2] 里面选k - 2 个，加上对应的贡献，再递归解决子问题即可。 -
F - Interesting Problem (Hard Version)
困难的题目。同样感觉记起来没什么用，也写不清楚，所以就不记了。
-
G - Family Photos
不想记。
Codeforces Round 1048 (Div. 2)
Link
第一次 Div. 2 打进第一页，虽然是 VP，而且这场 unrated。
-
C - Cake Assignment
想到了 SGU 126。这道题正难则反。
-
D - Antiamuny Wants to Learn Swap
似乎有线性做法，但是不管了，线段树和 ST 表一样草过去。发现一个序列是好的的充要条件是不存在长度为
3 的下降子序列，那么记dp_{i, j} (j \in \{1, 2, 3\}) 表示以a_i 结尾，长度为j 的子序列中，子序列的第一个数的下标的最大值，这个显然可以用线段树维护。然后再用 ST 表维护一下dp_{i, 3} 的区间最大值即可。 -
E1 & E2 - Maple and Tree Beauty
我好菜，花了 80min+。首先想到答案不会超过所有叶子深度的最小值
mn ，然后考虑如何让答案达到mn 。赛时一开始认为答案总是取每个叶子的名字的一段前缀与一段后缀，后来手模\inf 组样例又吃了一发罚时之后才发现只取前缀。那么，我们只需要考虑深度\le mn 的节点，并把其中深度相同的节点涂成一种颜色即可，其余节点可以任意涂色。正确性显然，因为如果匹配的位置越深，需要涂色的节点数严格不降。最后，还要判断能否将mn 层分为黑白两色，这一步可以通过 bitset 优化背包 DP 实现。时间复杂度O(\frac{n^2}{w}) 。如果用根号分治可以再优化到O(\frac{n \sqrt n}{w}) 。
MX NOIP 5
Link
这场是我考成屎了，甚至还垫底了。
-
A - 阿蛮
在 NOIP T1 放样例极弱的概期 DP 的出题人，愿你们的母亲的天堂相遇。
赛时爆零了。因为赛后没有立即发题解，所以甚至还是 GPT-5 给我讲的。
首先发现题目里面给的带权随机数其实是诈骗，因为当确定了新来的人数
i 与舞娘获得的总票数j ，是容易求出这种情况的概率的（用其他n - 1 个舞者分得i - j + 1 个观众的方案数除以n 个舞者分得i 个观众的方案数）。设f_{i, j} 表示新来的人数为i ，舞娘获得了j 票时的加分，g_{i, j} 表示概率，那么现在只需要求出\sum_{i, j}^{\text{cond}} f_{i, j} \cdot g_{i, j} 即可。直接计算是O(n^2) 的，但是通过一些组合恒等式就可以将其优化到O(n) 。 -
B - 菟园 & [HNOI2010] 弹飞绵羊
自从之前有一次把 LCP 当成 KMP 写之后就感觉终于完全理解了 KMP 与 fail 指针等内容。
容易想到建出 fail 树，那么问题就转化为了在树上支持某点到根路径修改与单点查询，类似与弹飞绵羊，所以下文介绍弹飞绵羊的做法。
看起来平衡树与 LCT 这些数据结构的学习成本都挺高的，确实像牢祝说的那样，这些问题都可以用线段树或者暴力数据结构解决。
对于弹飞绵羊，暴力的做法是
O(1) 修改O(n) 查询。考虑均摊一下，将n 个数分为B 个块，记to_i 表示从i 开始跳父亲，跳到的第一个块外的节点，dis_i 表示跳的次数。这样，对于修改，我们只需要对块内节点进行更新，时间复杂度O(\frac n B) ；对于查询，我们只需要一个块一个块地跳，时间复杂度O(B) 。显然当B 取O(\sqrt n) 时最优。时间复杂度O(n \sqrt n)
Codeforces Round 1049 (Div. 2)
Link
-
D - A Cruel Segment's Thesis
考虑
n 是偶数的情况。拆一下贡献，答案就是\sum_{i \in A} r_i - \sum_{i \in B} l_i ，其中|A| = |B| = \frac{n}{2}, |A \cup B| = n ，再拆一下贡献就变成了\sum_{i = 1}^n r_i - \sum_{i \in B} (l_i + r_i) 。于是按l_i + r_i 排序取较小的一半即可。若n 是奇数，那么枚举那个区间不选即可。 -
E - Prime Gaming
好题，但是难绷。考虑
m = 2 的 ez version，发现是容易做的。然后考虑重新定义状态，钦定一个阈值i ，让状态中的0 表示\lt i 的数，1 表示\ge i 的数。这样，对于一个状态st ，它可以表示的序列数量就是(i - 1)^{n - \mathrm{popcount}(st)} \cdot (m + 1 - i)^{\mathrm{popcount}(st)} ，那么答案\ge i 的序列的个数f_i 就应该是\sum_{st} (i - 1)^{n - \mathrm{popcount}(st)} \cdot (m + 1 - i)^{\mathrm{popcount}(st)} \cdot dp_{st} 。可以把st 按照\mathrm{popcount}(st) 归类，即设sm_i = \sum_{\mathrm{popcount}(st) = i} dp_{st} ，这样就可以O(nm) 计算f_i 了。答案即为\sum_{i = 1}^m f_i 。时间复杂度O(nk2^n + nm) ，前半部分有小常数。
MX NOIP 6
Link
-
A - 句法分析
唐题。
-
B - 树上前 k 大菊花
目前见过的题中，极多个物品中选前
k 大 / 小的题其实做法挺单一的。容易想到把每个点作为中心，先让菊花的权值取到最大值，并放到优先队列中，然后再将权值调小，把新的菊花放进放进优先队列中，直到取了k 个即可。 -
C - 相关聚类
根据特殊性质并观察样例发现是偏结论类型的题，并且如果是树形（基环树）DP 显然不可能做到
O(n) 。手模几个样例就发现只需要计算出环的大小与环上- 的数量，根据- 的数量分讨一下即可。
多校联考 20250915
Link
明明就是没什么辨识度好不好，考了个 CW rk 2 还被表扬了。
-
C - 发喷山火（CF2119F 加强版）
对于原题：容易观察到路径结构如下：从
st 出发，先经过若干个1 -1到达一个1 1，在获得了足够的生命之后再前往某一个终点。赛时没写出 50pts 是因为没有发现：在全程中就算存在多个1 1，都只会在第一个1 1获取到足够的生命。（话说要是发现了这个点，赛时还写出了 50pts，那场切黑也是很难绷了。）根据这几点，我们可以先处理出每个点经过若干个1 -1能够到达的最近的1 1，这可以用多源 bfs。接下来，我们可以从st 开始 dfs，再传一些神秘的参数，就做完了。 -
D - 走路赚钱（JOISC2019E 弱化版）
对于弱化版：把条件转化一下可以变成当
x = i 时，若y \le 或\ge k ，可以获得w 的价值。离散化过后用扫描线维护一下即可。
Atcoder Beginner Contest 423
Link
质量场。
-
F - Loud Cicada
主打一个现学现用。Solution。
-
G - Small Multiple 2
Solution。
Edu Codeforces Round 182 (Rated for Div. 2)
Link
被降智了呜呜呜。/dk /dk /dk
-
D - Price Tags
一眼极其数论分块，然后无脑写了之后被卡了。后来才发现是想复杂了，根本不用对于
a_i 去更新\lceil \frac{a_i}{x} \rceil ，直接拿\lceil \frac{a_i}{x} \rceil 找对应的a_i 即可。这题显然是不难的，主要是有些诈骗。 -
E - Looking at Towers
思维为零的数据结构题。容易写出一个
O(n^2) DP，然后发现可以用加乘线段树优化，然后就做完了。
MX NOIP 7
Link
-
A - 地球往事（[Gym105170E] Connected Components）
唐题。
-
B - 纪元（[Gym104976E] Period of a String）
挺有趣的一道题。考虑
s_i 与s_{i + 1} 两个串，发现s_{i + 1} 对s_i 有一些限制，每个限制形如：s_i 的前j 位形成的可重字符集是U 。那么同理，s_{i + 1} 本身也有一些限制，发现s_{i + 1} 的限制是可以与s_{i + 1} 对s_i 的限制，合并形成对s_i 的限制的。所以倒序维护当前的每一条限制，根据限制判断是否有解；若有解，再根据限制构造出s_1 ，便可以推出所有s_i 的值。 -
C - 黑暗森林（[Gym105170A] Eminor Array）
赛时找规律过了？（
实则是很没素质地用了 oeis。）发现答案是：\frac{\sum_{i = 1}^n (2^{2^i} - 1)}{3} -
D - 死神永生
原来我在 7 月 10 日并没有意识到我在那一天算是学会了虚树。
题目要求是「到每个点距离的最大值最小的点」，发现离一个点最远的点一定是直径的一个端点，而满足条件的点就一定是直径上的一个点。
于是这道题就做完了。用线段树动态维护虚树的直径即可。时间复杂度
O(n \log n) 。
Codeforces Round 1051 (Div. 2)
Link
难绷主要难绷在我每次在晚上打 CF 都要慌，而太慌了导致 D 没切出来，放弃 D 去看 E 的时候也许 20min 就秒了？具体时长记不到了。
-
D1 & D2 - Inversion Graph Coloring
实则挺唐的。设
dp_{i, j, k} 表示选了[1, i] ，其中的最大值是j ，最大的满足p \lt q \le i 且a_p \gt a_q 的a_q 是k 的方案数。转移显然，时间复杂度O(n^3) 。用树状数组维护dp_{i, j, ?} 与dp_{i, ?, k} 即可优化到O(n^2 \log n) 。赛后补题的时候因为初始化漏了一点导致调了 inf 久。/dk -
E - Make Good
比较一眼的题，与这道题类似的题还有 [ARC203B] Swap If Equal Sum。对于一些通过若干次可逆的操作将初始状态变为目标状态的题，容易想到先将初始状态变为一个相对规则的状态，再变为目标状态。对于本题，容易想到尽量把
)都变成(，但是如果只是将))变为((，那么还会留下一些单独的)。观察操作的性质，发现我们可以交换s_{i} 与s_{i + 2} ，而这样交换是不会改变下标的奇偶性的。于是考虑把奇数位置上的)与偶数位置上的)匹配并变成((，此时剩下的)的下标的奇偶性一定相同。接下来，给每个剩下的)匹配一个(。此时还剩一些(，再翻转一半的(变成)并与另一半的(匹配即可。边做边判断无解即可。一个 Corner Case 是，如果剩下的)全部在奇数位上，且奇数位上全是)，此时无解。
:::info[鲜花 (2025.9.18)]
前几天还有十几个 To-Do 现在居然补完了。
虽然动用了一些特殊手段。（好唐）
虽然今天晚一点又新增了两个 To-Do。
:::
MX NOIP 8
Link
-
B - 计树
赛时写了一个完全没有正确性的 DP。
发现最后一个节点一定是叶子，那么我们就可以推出倒数第二个节点的几种状态。依此类推，考虑倒着 DP，设
dp_{i, j, k} 表示考虑了[i, n] 的节点，还缺j 个父亲与k 个儿子的方案数，大力分讨转移即可。答案是dp_{1, 1, 0} 。
Atcoder Beginner Contest 424
Link
-
G - Set list
Solution。
Codeforces Global Round 29 (Div. 1 + Div. 2)
Link
-
E - Maximum OR Popcount
显然先把问题转化为达到每个答案至少需要多少次操作。贪心地，我们每次让或和中最后一个
0 变成1 。具体地，选择n 个数中的某一个，使得将这一位变成1 的代价最小。可是这时，可能低位不再是1 。所以对于下一位进行同样的操作，直到后缀变成全1 即可。 -
F - Exchange Queries
考虑先按
a_i 排序，那么交换a_i 也可以转化为交换b_i 。接下来，我们只需要对b_i \to b_i + 1 建边，并用线段树维护 SCC 即可。
Codeforces Round 1052 (Div. 2)
Link
-
D1 & D2 - Max Sum OR
对于 D1，考虑
n = 2^k - 1 ，此时恰好可以两两匹配。那么当n \lt 2^k - 1 时，就有一段前缀无法匹配。对于这段前缀解决子问题即可。对于 D2 也类似，两两匹配后解决子问题即可。 -
E - Yet Another MEX Problem
考虑钦定
\mathrm{mex} ，那么就可以用一棵线段树来维护对于每个钦定的\mathrm{mex} ，子数组的最大长度，查询就是全局\max 。发现钦定的\mathrm{mex} 不是实际\mathrm{mex} 时一定不优，所以并不影响。
多校杂题选讲 20250926
Link
-
A - Bit Counting Sequence
发现
a_i + 1 - a_{i + 1} 即当前的进位位数，根据这一点构造即可。挂了几发一是因为__builtin_popcount(unsigned int)，二是因为左右移负数位是 UB，洛谷评测机上会 TLE。 -
B - 一安在？ / Gdzie jest jedynka? 2
发现
1 的性质不算特殊，最特殊的是0 ，于是考虑把0 找出来。考虑对于一个数，询问它与其它每个数的\gcd ，其中的最大值就是它本身，并且能取到最大值的要么是0 要么是它的倍数。所以我们把0 和它的倍数再单独拿出来，解决子问题，最后最多会剩下两个数，其中一定有一个是0 。再拿这两个数去找到1 即可。精细实现即可达到题目要求。 -
C - 健身房 / Siłownia
有点难绷的贪心。首先容易想到一个天真的 DP，类似于最小点覆盖。然后你发现这样是错的，因为当存在
i, j 使得l_i \le l_j, r_i = r_j, p_i = p_j 时，这样会挂掉。发现我们肯定不能延后选，只能提前选，所以令r_i \leftarrow r_i - 1 即可。 -
D - Letter Stamper
也许算是第一道独立做出的紫？虽然得知这是 DP 好像是从讨论区得出的，并且调不出来的时候还看了题解，但是最后没看懂，还是自己调出来了？不管了。Solution。
-
I - Decoration
题面好唬人的样子，但是其实对这个东西建一个图就是一个基环内向树森林，要求的就是长度为
k 的简单路径的长度的最小值。倍增即可。
Codeforces Round 1053 (Div. 2)
Link
-
B - Incremental Path
不是有点难绷赛时只要不着急，认真手摸一下，几下就做出来了。
-
E - Limited Edition Shop
我写了一个很难写的做法，显然是有更好写的做法的，但是不管了。对物品按 A 的喜好排序，设
dp_{i, j} 表示选了物品[1, i] ，B 选到了物品j 的最大价值，转移是dp_{i, j} = \max(dp_{i - 1, j}, dp_{i, j - 1}) (j \ge rnk_i), dp_{i, j} = \max(dp_{i - 1, j} + v_i, dp_{i, j - 1}) (j \lt rnk_i) 。要用线段树维护，即区间（并且是前缀）加，并取前缀\max 。对于后者，可以用线段树二分与区间覆盖实现。好写的做法的状态定义是一样的，转移略有些不同，但是不管了。写这种数据结构优化 DP 都写烦了。 -
F - Attraction Theory
不错的题。手模一下样例可以发现，如果我们关注位置
i 上最终留下来的人数f_i ，那么f_i 一定是连续的一段有值，并且除两端之外都应该是奇数。直接计算是不好做的，于是我们用与 Wine Thief 类似的 trick，先把尝试问题转化为对称的。考虑枚举区间长度与端点的奇偶性，于是此时就可以钦定端点为奇数，最后再加上常数项即可。通过一些简单的计算可以得到f_i 的期望与不同的f 序列的数量，再利用a 的前缀和与二阶前缀和即可计算出答案。 -
G1 & G2 - Hidden Single
G1 Soluiton，G2 Solution。
Atcoder Beginner Contest 425
Link
-
E - Count Sequences 2
发现这个东西其实有两种算法。记
s = \sum_{i = 1}^n c_i ，一种是\frac{s!}{\prod_{i = 1}^n c_i!} ，另一种是\binom{s}{c_1} \cdot \binom{s - c_1}{c_2} \cdot \ldots \cdot \binom{s - c_1 - c_2 - \dots - c_{n - 1}}{c_n} 。你会发现把第二个化简之后就是第一个，但是第二个显然更好算。其实第一个也能算，但是赛时我饭堂了，只单独处理了每个数的质因数分解，而没处理每个数的阶乘的质因数分解。 -
G - Sum of Min of XOR
好简单的 G，赛时没切出来是因为回寝室了，话说这应该是我第一次独立做完一套 ABC。一种暴力是建 01trie 暴力，时间复杂度
O(V \log V) 。考虑反过来，对于每个a_i ，有哪些数与a_i 异或能取到最小值，再简单拆贡献计算答案即可。时间复杂度O(n \log^2 V) ，精细实现可以做到O(n \log V) 。（感觉做法好抽象，讲不清楚。）
2025.10
Codeforces Round 1055 (Div. 1 + Div. 2)
Link
我好菜。
-
D - Division Versus Addition
赛时比较早就想到了大概的做法，但是没写（？）。首先发现
\mathrm{popcount} = 1 的数显然没有贡献（操作它则严格不优），而其它数是可以有贡献的。但是观察样例发现3 可以没有贡献，即满足x = 2^k + 1 的x ，若 A 先操作一次，那么这个数就没有贡献了；而对于其它数，就算 A 操作了也依然可以有贡献。对于上述这类数，A 可以让其中的一半（向上取整）取消贡献。所以答案就应该是原本的操作次数 + 有贡献的数的数量 - 特殊数的数量的一半向上取整。 -
E - Monotone Subsequence
好难绷的题。第一次考虑对于全局询问，如果答案序列的长度
\ge n + 1 直接返回。然后你发现要是再询问答案序列中的元素好像没什么用，所以下一次就询问除它们以外的元素。于是这样询问n 次，如果中途答案序列长度\ge n + 1 就直接返回。如果n 次之后依然没有答案，那么现在一定还剩下一个元素。考虑构造一个下降子序列。发现对于一个在第i + 1 轮中被询问的元素，在它左侧一定存在一个在第i 轮中被询问的元素，且这个元素一定比它小。所以从剩下的元素中的一个开始，每次向左找第一个上一轮被询问的元素，即可构造出答案。
多校联考 20251007
Link
-
B - 中心极限定理
我唐。发现难点在于把马吃了怎么处理，于是考虑状压一下当前位置前几步即可。
-
C - 散步
将题面稍作转化，变成：给定一个无向联通图与偶数个关键点，要求将关键点两两匹配并选择一条路径，使得任意两条路径（边）不交，构造方案。发现这个问题在树上就可以做。对于一棵子树，它最多有一个点未被匹配。于是对于一个节点，先将它子树中剩下的点与它本身（若有）两两匹配，最后最多剩下一个点，将这个点传递给父亲即可。
多校联考 20251008
Link
-
B - 围棋
赛时死磕导致根本没看 T3 和 T4。以后再死磕我是狗。
发现难点在于翻转一个白棋，因为翻转后可能会新增一些死的白棋。发现这个东西差不多是割点，于是跑塔尖即可。另外集中情况分讨一下即可。
-
C - 相互抵消
化简发现原式至于
\sum i a_i 与\sum a_i 有关，维护即可。
多校杂题选讲 20251010
Link
-
A - 帐篷
凭啥我只会
O(n^3) 。设dp_{i, j} 表示格子大小为i \times j 时的方案数，考虑横着一组占用一行两列，竖着一组占用两行一列，单独一个占用一行一列，直接转移即可。
后面的不想写了。
多校联考 20251011
Link
美好的一天从饭堂开始。
-
A - 询问
发现 5 次询问之后就是
a \leftarrow 2 \times (a - i) ，b \leftarrow 2 \times (b - i) 了，矩阵快速幂即可。话说我赛时写了个什么神秘O(\sqrt{MOD}) 的分块做法？ -
B - k-绍兴序列
-
C - 二次根式
什么猎奇打表题。发现
F(n)^2 G(n) = n! 所以只用计算F(n) 。对于F(n) ，枚举\sqrt n 以内的质数计算贡献即可。发现需要快速阶乘但是又发现模数固定，于是打表即可。
Codeforces Round 1058 (Div. 1, Div. 2)
Link
Div. 2 Rank 8，紫名祭。
只能说是前一天晚上睡太好了，这天晚上状态好。要是我每次晚上状态都这么好 2200 也不是不可能。
-
F - Twin Polynomials
赛时做这题的时候有点飘了，要是我认认真真手模一下样例说不定真能场切。
容易想到对于
i \to a_i 连边并考虑图的性质。发现对于每个点（除0 号点外），要么向0 号点连边，要么形成自环，要么属于一个二元环。特别地，n 号点不能向0 号点连边。容易举反例证明这一点。于是考虑先把图建出来，判断一下是否合法。接下来，只需要考虑剩下的点，并进行一个 DP。设有i 个点时有dp_i 种分配方案，那么dp_i = 2dp_{i - 1} + (i - 1)dp_{i - 2} ，初始状态是dp_0 = 1 。如果是n 号点那么需要特判一下。于是就做完了。赛时先是认为图是由若干个环组成的（不一定是二元环或自环）于是耽误了好久。后来想到了这一点，可是又没想到可以向
0 连边，又没有静下心来手模样例，于是 5 题 rk 8遗憾离场了。 -
G1 & G2 - Inverse Minimum Partition
好神的题。Solution。
值得一提的是，BINYU 自己把这道题改出来了，然后他又给 Zi_Gao 讲了，然后我又参考了他们的代码。直到我写题解的时候，才发现这个做法是假的，然后把我们三个 hack 了。
多校联考 20251014
Link
除了之前没有区分度的那场之外考得最好的一场。
并且获得了 1.25 瓶冰红茶。
只能说还在稳定开挂吧，之前
-
A - Happy · Lovely · Everyday!
每次选择相邻的两个异或听起来比较困难，所以考虑转化一下，将原序列分成若干个子段，让每个子段变成这个子段的异或和。依然感觉不是特别能发现性质，于是考虑如果已知最终状态，如何判断合法，发现是贪心判断，那么这道题的做法就比较显然了。初始状态为
dp_0 = 1 ，每次dp_i 可以转移到dp_{i + 1} ；若存在k 使得k 是i 右侧第一个满足s_k = 1 的位置，那么dp_i 还可以转移到dp_k 。若a_{i + 1}, \dots, a_n 的异或和为零，那么将dp_i 累加进答案即可。其实挺唐的，主要还是没改掉赛时喜欢乱猜结论的坏习惯导致耽误了好久。 -
B - 敬启，致那时的我
虽然按理来讲这题应该评蓝（因为矩阵快速幂都是绿）但是我觉得 B < A。
发现斐波那契数列实在是一点性质都没有了，popcount 相同的数对应的斐波那契值也是一点性质都没有，于是想想关于计算斐波那契数列的第
n 项还有什么做法，于是显然只能想到矩阵加速。你发现矩阵满足结合律与分配律，于是这道题就做完了。设dp_{i, j, 0 / 1} 表示考虑到第i 位，填了j 个1 ，当前值是否等于上界 时的答案。直接转移即可。 -
C - Lead to shine more
好奇我赛时是如何切掉这题的。
先观察一下，发现能走的路只有倍增这一条。一个天真的想法是，设
dp_i, to_i 分别表示初始x = 1 ，达到x \ge 2^i 所需要的步数以及总步长。发现无法转移，需要添加j 这一维表示初始x = j 。发现还是无法转移，需要添加k 这一维表示每次更新是x \leftarrow x + \mathrm{popcount}(x) + k 。然后就可以转移了。对于每次询问，发现高位是容易处理的，然而低位不容易。所以用倍增处理出高位，留下最后6 位直接暴力地推即可。值得一提的是，赛时代码中我不小心让下标出现了
-1 ，导致 CWOI 上挂完了。幸运的是，虽然本地测试也用的 Linux，但应该是因为环境不同，本地并没有挂。赛时我其实注意到了那里会出现-1 ，但是 Windows 上没挂，我也没有意识到它会被作为下标，就忽略了这个问题。总之还是不够严谨导致的，而且在 NOI Linux 上测一下样例也是很有必要的。（这段话好人机。）
:::info[鲜花 (2025.10.14)]
今晚有点颓，但是不管了。
想了想现在的自己和之前相比有些什么进步，写的一百多 KB 的日祭（加上题解）除了即时的总结，还有没有为现在的我留下经验教训。
也许是有的吧，虽然可能自己感觉不明显。不过一个很明显的进步是，之前我总是一步一步跳着想，导致（当天没写完后来忘了）。
:::
多校联考 20251015
Link
-
B - 捐赠
两只
\log 跑得快，甚至10^6 草过了2s 。正解显然是一只
\log 的。你会发现 A 选的个数与 B 没选的个数之和恰好是 B 的个数，下文记作k （废话），那么转化一下，对 B 物品的权值取相反数，那么答案就是选权值前k 大的物品，再加上 B 物品的权值和即可。 -
C - 染色
不错的树上启发式合并题，可是我并不会。
然后写日祭的时候发现一车人的启发式合并是假的，包括我。当然如果精细实现也能过，但是我不想改了。
多校联考 20251021
Link
BINYU Zi_Gao Rong7 模拟赛，内部提前到了 20251017 考。
A 是唐，C 的
多校杂题选讲 20251017
Link
不想写。
多校联考 20251018
Link
紫紫黑黑 NOIP 模拟赛。
不想写。
并非多校联考 20251021
Link
运动会，没打。
多校联考 20251022
Link
-
A - 石头人
因为没判
s_0 导致挂分。 -
B - 炒鱿鱼
要求在一种特殊图上对图进行三分图染色。
做法是，直接 dfs 染色，但是优先遍历编号大的点。至于为什么是对的我也不知道
赛时因为有点细节问题导致挂分。话说这个构造甚至我最后 20min 想出来的。
-
C - 适格者
纯唐。
多校联考 20251025
Link
-
A - 剖分
唐氏树形 DP / 贪心。
-
B - 海啸
不带修是 ARC201B。
带修也是好做的，维护一下当前每一“层”中的元素即可。
并非多校联考 20251027
可是牢祝依然算了这场的成绩。
Link
-
A - 大骑士领一瞥
分讨题。
-
B - 流放阿卡胡拉
注意到路径一定是
(0, 0) \to (x', y') \to (x, y) ，其中x' 或y' 是质数。然后你发现，我们只需要关注以(x, y) 为右下角的一个矩形中的(x', y') ，所以在矩形中跑暴力 DP 即可，矩形长宽取到1000 就行了。虽然不知道哪里来的正确性，但是靠感觉它就是对的。
多校联考 20251028
Link
-
A - 排序
唐。
-
B - 重排
唐。
多校联考 20251029
Link
-
A - 初恋
唐。
-
B - 奥瑟罗
没我唐。随便乱维护一下即可。
CSP-S 2020 并非 VP
-
A - 儒略日
屎。
-
B - 动物园
屎。
-
C - 函数调用
好。没一眼秒的原因是没有注意到加乘可以转化成加和全局标记乘，也没想到正难则反。我咋这么唐。
后来一直写挂的原因是，拓扑时理所应当地只加了
0 号点，也是糖丸了。包括记忆化搜索的时候，应当令初值为-1 ，因为乘数可能为0 。
CSP-S 2021 并非 VP
-
A - 廊桥分配
唐。
-
B - 括号序列
唐。
-
C - 回文
屎。
CSP-S 2022 并非 VP
-
A - 假期计划
好。你发现如果我们确定了
B 和C ，那么就可以贪心地选择A 和D ，其中A 需要满足从1 与B 均可达，D 同理。于是我们可以O(n^2) 预处理出可达关系，与对于一个确定点，有哪些点可从1 与它可达。接下来，枚举B 和C ，贪心地选择最优的A 和D 。发现A 和D 可能会和其它点重复，于是考虑放缩一下。容易发现我们只关注前3 大的A 和D ，于是预处理的时候求出前三大的即可。 -
B - 策略游戏
唐。
CSP-S 2023 并非 VP
-
A - 密码锁
唐。
-
B - 消消乐
唐。难点在于证明时间复杂度。
-
C - 结构体
屎。
CSP-S 2024 并非 VP
-
A - 决斗
唐。
-
B - 超速检测
屎。
-
C - 染色
唐。这题咋跟 Chicken Jocky 一模一样啊，虽然自己还是瞪了好久，还因为饭堂调了好久。
2025.11
CSP-S 2025
-
A - 社团招新
原来这就是反悔贪心啊。
-
B - 道路修复
我是唐。发现一个图在加入若干条边后，原来不在 MST 的边现在还是不在 MST。随便搞搞即可。
-
C - 谐音替换
赛时想到一个树套树做法但是没写出来。
感觉转成二维数点的做法不是很优，于是严肃决定恶补一下串串。
首先把
(s_1, s_2) 写成(ABD, ACD) 的形式，然后把两个串合在一起变成A|BC|D ，然后原题就变成求有多少个模式串是文本串的子串了。时间复杂度O(L |\Sigma|) 。 -
D - 员工招聘
不想写了。
多校联考 20251104
Link
-
A - 图
甚至是搜索题。搜一下每个点到
1 的最短路距离，边搜边算贡献即可。
多校联考 20251105
Link
这场是啥啊。
多校联考 20251108
Link
下分场。
-
A - 国王的试炼
拆拆贡献，发现只用关注当前数与比当前数小的数，所以随便 DP 一下即可。
多校联考 20251111
Link
上分场。
-
A - 青蛙
唐。
-
B - 表达式
我唐。注意到
0+x+x-0正着是+2x 倒着是0 ，于是直接构造即可。 -
C - 淘汰赛
首先容易写出
O(n^2) 。然后你会发现我们只用关注以
(a, b) 为右下角、长宽为\log V 的矩形中的位置，于是就做完了，时间复杂度O(T \log^2 V) ，用数位 DP 实现可以做到O(T \log V) 。
多校联考 20251112
Link
原神 Round. 1
-
A - 异或
唐。
-
B - 伊甸
奶龙大战暴暴龙，但是输在了原题没有的 corner case。
-
C - 炼丹炉（[CF1979F] Li Hua and Path）
板，但是不会。首先人工容斥一下，变成求同时满足两个条件的点对个数。考虑从小到大与从大到小各加一遍点，令新加的点成为当前连通块的根，那么限制就转化为了祖孙关系。用类似阿狸的打字机的做法即可。
多校联考 20251113
Link
原神 Round. 2
-
A - 传统题
大样例题。
-
B - 非传统题
你没蛋还在发力。
-
C - 历遍的树
考虑找出哪些点可以用来掉头，发现这样的点需要有三条以它为起点的路径，使得每条路径的长度都大于等于蛇的长度。称满足条件的点为关键点。可以证明，只要蛇可以到达一个关键点，它就可以到达任意一个关键点。所以任取一个关键点为根，模拟蛇移动的过程，判断蛇能不能移动到根即可。
多校联考 20251118
Link
原神 Round. 3
-
A - box
唐氏 DP 题。
-
B - graph
侦探 JYY 还在发力。
-
C - chess
赛时通过手模大样例猜出了斜列黑白交替的结论，然而因为时间原因，没发现第一行相邻的一对格子颜色相同（实则是因为赛时做完前两题开始发呆耽误了很久）。Solution。
多校联考 20251119
Link
-
A - 下一个天亮
乱构造一下即可。
-
B - 希巴拉克的道路
发现需要维护一堆线段的斜率，上李超树即可（但是赛时写了个神秘做法）。
-
C - 超纲
似乎挺板，但是不会。
多校联考 20251121
Link
-
A - 『木叶创立』
唐。
-
B - 『须佐能乎』
容易写出一个暴力的矩阵快速幂优化 DP。可以发现，若令直径的中点作为根，那么对于一棵子树，其内部点的 DP 转移是完全相同的。进一步发现，若称两棵子树本质相同，当且仅当其内部的直径端点数量相同，那么对于两棵本质相同的子树，其内部点的 DP 转移都是相同的。所以对于本质不同的子树进行 DP 即可，时间复杂度
O(n^{\frac 3 2} \log T) 。
多校联考 20251122
Link
-
A - 破乱的诗歌
随便乱做做即可。
-
B - 增殖的病菌
塔尖缩一下点就昨晚了，细节有点多。
-
C - 可爱的猫猫
难绷搜索。
多校联考 20251124
Link
-
A - 创生矩阵
难绷构造题。考虑构造两个长度为
n 的序列a, b ，其中a 满足\forall i \in [1, n], \exists x \in \mathbb{Z}^+, x^2 = \sum \limits_{j = 1}^i a_j^2 ，b 同理。那么对于原矩阵c ，只需要构造c_{i, j} = a_i \cdot b_j 即可。对于a, b ，随便构造一下即可。 -
B - 都因为你
签到题。
多校联考 20251125
Link
A 原，其他不会。
多校联考 20251127
Link
-
A - 幸运数字
分讨题，被 corner case 创飞了。
-
B - 树的遍历
屎。随便推一推发现需要维护一堆东西的和，然后维护即可，
op = 0 还需要写个扫描线。 -
D - 季风
签，随便推推式子即可。
NOIP 2025
-
A - 糖果店
按照
x_i 排序，取最小的若干个x_i ，再取若干个最小的x_i + y_i 即可。 -
B - 清仓甩卖
父母是一块还是两块。
记
x(y) 表示第y 个物品打折后为x 费。发现统计不合法的方案数应该更容易。发现一个方案不合法，当且仅当考虑物品的顺序为\dots, 1(j), \dots, 2(i), \dots ，且考虑2(i) 时恰好只剩1 费。特别地，若考虑2(i) 后考虑了1(k) ，应当满足a_j + a_k \lt a_i 。于是考虑对
a 排序，并枚举i, j ，使得a_i \gt a_j \gt \frac {a_i} 2 。通过双指针求出k 的最大值。对于每个物品，若下标属于[1, k] ，那么取一费或二费均可；若属于(k, j) ，那么只能取二费；若属于(j, i) \cup (i, n] ，那么取一费或二费均可。另一个限制是在考虑
2(i) 之前恰好花掉了m - 1 费，除去j 花掉的1 费，还剩下m - 2 费。对于下标属于(j, i) 的物品，若取一费，那么它会在考虑i 之前被取，贡献为1 ；若取二费，那么它会在考虑i 之后被取，贡献为0 。对于下标属于(i, n] 的物品，无论取一费还是二费，它都会在考虑i 之前被取，所以贡献为1 或2 。现在要求从这些物品中选m - 2 费的方案数，发现两段本质相同，我们可以认为第一段是0 (+ 1) ，第二段是1 (+ 1) ，于是直接组合意义即可。当然也可以枚举一段求另一段，再用一个神秘恒等式化简。
2025.12
最新内容见 此处。