2025 年日祭
本文将同步发表于洛谷（暂无法访问）、CSDN 与 Github 个人博客。
2025.1
2025.1.4 新的一年
今日歌曲：New Year’s Day
去年停课的时候是有记日祭的，但是有一些是手写的，一直都还没有整理好。今天看到一个简单的trick，想记下来。于是，就又开始写日祭了。
[洛谷 P2831] [NOIP2016 提高组] 愤怒的小鸟
一道远古状压题了。（一是指题目本身远古，二是指这道题是好久之前就该做的题。）看到第一篇题解的trick，想起去年暑假集训的时候也有这样一个trick，但是忘了是哪道题。这个trick挺简单的，但也挺好用：状压时，如果目标状态是全0或全1，并且转移顺序不影响结果，那么可以直接从最低位的1或0转移，因为最低位最终一定会被转移，而顺序又不影响结果，所以这样做可以优化掉
的复杂度。其他的按正常状压即可。 -
今天学了 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 - 括号序列
题目：给一个由左右括号构成的字符串
，对于每一个位置 ，输出有多少个子串，满足这个子串是一个合法的括号序列，并且 这个位置在子串中。 题解：简单维护前缀与后缀的括号数量即可。（忘写该死的模数暴扣70pts。）
C - 矩阵删除
题目：给一个
的 01 矩阵，我们想在每一行删除一个元素，得到一个 的矩阵。其中删除的元素的位置 ，满足 。请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的。由于答案很大，输出答案对 取模的值。 题解：比较板的DP，但是赛时思路没那么清晰，也没去推式子。分别维护对于每一个位置的方案数以及与旁边位置重合的方案数，推出式子后发现全都是求和，于是用前缀和维护即可。
2025.1.13 乐极生悲
今日歌曲：Wonderland
今天期末考试考完了，整体还行，语文更是考到了惊人的
下午体育课，刚好初一体锻放歌，放得全是霉霉的歌，我还去点了几首。开心。
然而下课要集合的时候，我小跑了一下，而这下就恰好被足球爆头，眼镜镜架直接断掉，箍牙的铁丝直接断掉，嘴皮直接被铁钉磨得烂掉，鼻子被眼镜压了一个印子，还在流鼻血。
真是乐极生悲。
2025.1.17 傻子游戏
今日歌曲：Foolish One
今天开始上课六天。
昨天听说 jmr 拿了清华一等约。祝贺他。
这周二（1.14）已经回到15班了。
昨天晚上玩梗发癫，还玩了离谱的傻子游戏。达成成就：在5.5h里睡够8h。
上午%你赛，T1忘了判零挂了10pts，T3是之前做过的一道原题，于是赛时死磕，最后没调出来。赛时的思路基本上是对的，但是没想到容斥；又因为我钦定的一个条件有问题，导致正确性略有问题，最后没调出来。
喜提
A - 串
题目：在虱子王国，一句话由
个词组成，其中恰好有 个词是怪的，其它的词都不是怪的。众所周知，负负得正，我们定义一句话的一个区间是怪的，当且仅当其中含有奇数个怪词。请构造一句符合条件的话，使得其中怪的区间数量最多。 题解：发现答案为奇数块乘上偶数块。构造即可。
B - 艺术家
题目：给定一个长度为 n 的颜色序列
。再给出 个区间，第 个区间为 ，保证任何两个区间都是不相交或包含的关系。在接下来的 个单位时间内，第 个时间会给定 ，表示将 变为 。请对于每一个区间求出，最早的其中所有颜色都互不相同的时间。 题解：
保证任何两个区间都是不相交或包含的关系。
所以可以把区间建成一棵树。当一个子区间合法，其父区间才有可能合法。在原数轴上维护
表示 之前第一个颜色与 相同的点，则一个区间内部颜色互不相同等价于 。使用线段树维护。对于 的更新，用 set 维护。即可。（难写死了，还没写完。） C - 黑白树 （[Atcoder ARC108F] Paint Tree）
题解：画一个直径上吊着节点的图，讨论一个节点在什么时候可以带来贡献。容斥计算即可。
晚上打了入门赛，可以加咕值了。
晚自习最后10分钟，记一些话。
我的信竞，在进步么？看起来好像是的。要是拿现在的我和一年前的我对比，那已足以
倍杀。但……补过的题还是不会做，码量大一点的又不愿意写，一到晚自习就写不动了，于是写一会儿又开始划水。我倒有一个优点，就是一般不会去刷水题（除了入门赛）。但是，难一些的题……绿题效率低，蓝题想不全于是又看题解，紫题几乎无法独立完成。 最终做了的题似乎是白做。
……
终究还是人的问题。
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
挺玄学的构造题。我们希望大概长这样的结构：
这样构造出的答案有
个，可以通过。稍微分讨一下即可。 赛后看了一下题解，发现自己好唐：
[CodeForces 2056D] Unique Median
又是一道正难则反，计算坏的序列的个数。这道题的trick挺巧妙的，但没接触过，确实想不出来。发现长度为奇数的序列一定不是坏的，所以只考虑偶数长度序列。对于一个序列的中位数
，将序列中 的数化为 ，其它的化为 。若最终区间和为 ，那么这个序列就是坏的。另外要注意去重。维护前缀和即可。 [CodeForces 2056E] Nested Segments
组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量，那么需要构造成二叉树。（这里具体不想证明。）对于某一个节点，设其儿子数量为
，则计算 （卡特兰数）即可。
下午先把E题改了，学习了一下吉司机线段树。这东西挺好理解的，写起来也很爽，但就是又臭又长又难调。
-
这道题本来是第二道模板题的，但因为第一题相当于第二题的子问题，所以直接冲着这道题来了。写板子即可。（啊啊啊终于还是讨厌上吉司机线段树了啊。）
今天整理了一些去年的日祭。还没把手写的整理上去。
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+组合数学题。赛时推式子感觉推出来了，结果赛后再一看伪了。很容易发现，
，所以DP计算非 元素的情况，再用组合数学即可。 [CodeForces 2060G] Bugged Sort
这个题就挺有意思的。这篇题解感觉讲得比官方题解还要清晰。可以观察到，当
，我们可以任意（正常）交换两组的位置。因此，我们可以将两组数进行翻转。换而言之，进行翻转的次数必须是偶数次。这里记翻转次数为 。我们把较小的数放在 ，较大的放在 。若按 排序后 有序，那么该组数据有解，当且仅当满足这三个条件之一： ，此时可以选择交换奇数组数翻转以改变 的奇偶性，处于“无敌”状态。 ，此时可以翻转全部以改变 的奇偶性。
否则无解。判断即可。
今天下午看了一个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
又是一道正难则反。我们很难将
合并，那就把 中不合法的进行拆分。用 map 维护即可。其实这道题也好证 ，只是想凑一个小标题罢了。[CodeForces 2061E] Kevin and And
这题有点……难评。为什么字典树过不了啊……
因为
很小，所以对 进行状压，再将 的变化量压进堆里选最大的 个即可。（好吧其实不是特别理解。）
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。
-
神奇搜索题，暴搜+剪枝+略微组合数学即可。
神奇卡常题目，拼尽全力，2700ms+，终于冲进3s。
-
很普通的一道DP题，可是赛时都在想组合数学。
表示到第 位模 的值为 的数中 的数量， 表示到第 位模 的值为 的数的数量，直接转移即可。 [Gym 102428F] Fabricating Sculptures
神奇DP题。最开始看题解都没看懂，一是自己确实不理解是怎么算的，二是题解写得比较简略，看了好久才看懂。
设
表示从上往下一层层放，当前一共放了 个，最下面一层放了 个的方案数。有方程 （希望没写错）。将这个式子拆开再维护前缀和即可。（开了long long见祖宗。） -
很有趣的一道题。很容易发现，两个相邻字符串长度之差（的绝对值）为
或 。暴搜即可。 赛时的想法是，将原字符串平均分，再给
或 的偏移。可是偏移少了一些，虽然没 TLE 但一直 WA，拼尽全力无法战胜。 赛后再改一改，拼尽全力终于战胜。
今天本来说再补补昨天的 F，改改昨天的 E，结果今天的第三题看半天看不懂，昨天的 E 和 F 都没做。
最终今天做了四道题。
感觉心态有点崩。（尤其是看第三题的时候。）
……
2025.2.10 放弃即可
今日歌曲：Peace
综合题2。
今天还做出了一道题。
[Gym 100861E] Extreme Programming
看了题解真的好简单。首先我们先确定这些问题的顺序。推推式子，排序即可。现在，我们不用考虑顺序，只用直接背包，找出最大的
与最小的 即可。 可是这道题不知道哪里写挂了，WA on test 15。**
放弃即可**。[Gym 100217I] Sharing the Sweets
分拆数板子题。（可是我不会。）写板子即可。
-
这题着实简单。设
表示放了 个括号，当前高度为 ，是否到过最高点（深度为 ）的方案数。直接转移即可。 可是赛时想多了，一直在想组合数学。或许先设方程再推会好一些。
赛时还因为多测不清空挂了四发。
今天还举办了 CWOI ER 2 & 1 > 2 Round，感觉对于他们还是太难了。
（今天字符数破
2025.2.11 放弃即可
今日歌曲：Pink Pony Club
模拟赛
B - 刀言刀语 （[洛谷 P6864] [RC-03] 记忆）
今天给的题解以及同学讲解的都是非矩阵做法，可是听得迷迷糊糊。一下午尝试乱搞做法，结果没搞出来，最后，一道题都没改出来，**
放弃即可**。晚上终于学习了矩阵，基本学懂了，这才发现矩阵有多好用。之后又看了这道题的矩阵+线段树做法，终于基本懂了。将这些数据打包成矩阵：
。对于操作一，等同于 。对于操作二，等同于 。对于操作三，若是恢复某个操作，则与操作一二相同；若是删除某个操作，则将这个操作设为单位矩阵（ ），不会对答案产生影响。用线段树维护每个操作对应的矩阵，区间求和（求积）即可。 这道题记得比较详细，毕竟是第一次接触矩阵。
C - 刀妙构造
题目：给定一个长度为
的排列 ，通过尽可能少的操作，使得 。判断是否有解。若有解，输出具体的操作。操作的定义：选择 满足 ，交换 与 。 题解：原本就满足
的位置将原数组分割成若干个块。对于每个块，若是目标的一种排列则有解。设当前块为 ，则依次把数 移到位置 。要注意的是，在移动的过程中，可能会使得其它的 成立。所以我们将这些即将成立的位置先进行偏移，再将当前的数移到目标位置即可。 扩展：尝试在
的时间复杂度内求出有解的排列个数，对 取模。
这几天强度还是比较高，因为跟进度跟得有点吃力了。今天晚上眼睛疼，难受。
2025.2.12 罚时吃饱
今日歌曲：two years
今天上午VP Codeforces Round 1004 (Div. 2)，下午改Codeforces Round 1004 (Div. 1)。上午C题因为少判了一个条件，罚时吃饱了。
[Codeforces 2066A & 2067D] Object Identification
神奇交互题。观察到一个性质：对象
的答案可能是 ，但对象 的答案不可能是 。 若
不是 的一个排列，一定可以找到一个不在 中的数 ，对其与另一个不同的数询问。若是对象 ，因为 没有向任何点连边，所以答案一定为 。若答案不为 ，则是对象 。 若
是 的一个排列，那么找到满足 的 。询问 与 。若是对象 ，那么两个答案应该是相等的，并且都 （因为 ）。然而如果是对象 ，那么当 ，不可能同时存在一条长度至少为 的 到 的路径与一条长度至少为 的 到 的路径（因为 ）。综上所述，若两个答案相等并且都 ，则是对象 ，否则是对象 。 按照题解模拟即可。[Codeforces 2066B & 2067E] White Magic
这题似乎挺简单的，只是赛时看了一眼但是没多想。
首先可以注意到，没有
的子序列一定是合法的，有两个及以上的 的子序列一定是非法的。所以要么选所有非零元素，要么选所有非零元素与一个 。 若是选一个
，显而易见，选最左侧的 是最优的。于是判断这么选是否合法即可。 [Codeforces 2066C & 2067F] Bitwise Slides
很有意思的 DP 题。
我们根据题意可以得出，对于时刻
，记 ，有 。于是对于某个时刻，有这三种状态： 。设 表示这三种状态的情况数，经过推导（具体过程略），可以得出 。发现可以滚动。由于值域较大，用 map 维护 DP 即可。 [Codeforces 2066D1] Club of Young Aircraft Builders (easy version)
有趣的组合数学题。
因为下面的楼层并不会影响上面的楼层，所以从下往上考虑。对于某一个高度，丢飞机的次数最多为
，假设它实际丢 个，则有 种情况。所以设 表示到了第 层楼，已经丢了 个飞机的情况数。有转移方程 。 答案为
。直接 DP 即可。 扩展：求证答案为
。
今天晚上略水……没做题。但是今天一天综合下来……还将就吧。
2025.2.13 笑点解析
今日歌曲：evermore
今天 jmr 终于回来了。
今天学习了李超线段树。
[洛谷 P4097] 【模板】李超线段树 & [HEOI2013] Segment
刚开始学李超线段树，觉得挺简单的。其实它跟吉司机线段树有点像，只是维护的东西要少一些，并且代码更好写。
对于每个节点，考虑维护在它中点处的最高线段编号，那么用类似于吉司机线段树区间取
：若当前线段完全优于原有线段，那么直接替换；若当前线段完全劣于原有线段，那么直接舍弃；若当前线段与原有线段有交点，那么递归更新当前线段较大的那一段。对于查询，直接把路径上所有的线段取 即可。时间复杂度 -
纯堆码量的题。首先这题一眼树链剖分，一眼李超线段树。这题算是很基础的树剖，只是套的是李超线段树。
于是 LCA + 树剖 + 李超线段树 就算是码量炸弹了。也许树剖都这样，只是我没怎么写过。所以……先把模板题写了再说。
-
第一道真正意义上的树剖。之前倒是写过一个有点树剖思想的贪心（但那个好像是长链剖分）。
一共交了四发，笑点解析：前三发线段树没 pushup。由于当时另外没找到问题，于是我严重怀疑是线段树的问题。然后用那个线段树，写了一个线段树的板子，一测挂了，才发现是没写 pushup，糖丸了。
第一次写树剖，稍微参考了一下题解代码，但整体还是自己在写。树剖其实挺好理解的。
写完模板题，该写这道题了。这道题从下午就开始写，一直调到晚上都没调出来，只有明天再补了。
-
今天
今天晚上
2025.2.14 绝世好题
今日歌曲：Red Wine Supernova
今天%你赛，
B - permutation （[Codeforces 1827B2] [加强版] Range Sorting (Hard Version)）
绝世好题之神秘计数（？）题。
又是一道正难则反。容易发现，答案为：
考虑枚举
满足 ，那么 。显而易见， 是 右侧第一个比它大的数，那么 ，其中 满足 是 左侧第一个比它大的数， 是 右侧第一个比 小的数。维护即可。 这题……题解给的用 set 维护，可惜常数太大，被
卡掉了。他又给了个链表的实现，不想看，于是自己开始研究。 由于要求的值都是最近的最大/最小值，所以考虑使用单调栈维护。
与 都非常好求，可是如何求 是个问题。 当时做这道题的时候自己没想出来，后来看原题题解区才懂。做法是，对于前文所提到的
，维护 个集合 ，满足 。接下来倒序遍历 ，对于每个 ，顺序枚举 ，将单调栈中 的数弹出，栈顶元素即为 。在将每个 操作完后，将 加入单调栈。正确性证明如下（部分摘自原题题解）： 记
表示查询 右侧第一个比 小的数。（ 含义同上。）若这个询问弹出了 ，那么 的答案显然不为 。现在需要证明 的答案不为 。 若
，因为 ，所以 可以作为答案，答案不可能是 。 若
，因为 ，所以答案不可能是 。 若
，那么 ，否则 右侧第一个比它的的数不可能是 ，所以 ，答案不可能是 。
终于证完了。按上述步骤维护即可。
这题本来就有一定的思维难度。如果用单调栈，这道题的思维难度就更高了。如果用有的数据结构（比如 set），倒是好想好写，可是
卡常。
因为今天一下午加晚上一直苦攻 T2，所以昨天的题还没来得及补。
今天写得很晚了，准确来说已经第二天凌晨了。今天就到这里。
2025.2.18 无处不在
今日歌曲：I Forgot You Existed
“我无处不在。”——
今天在改游戏那道题，最终决定重构！
2025.2.20 笑点解析
今日歌曲：The Archer
今天还是在改游戏，最后终于还是改出来了。笑点解析又来了。
在
里计算了 。 在线段树中的编号与实际编号混淆了。 另外还有一些很糖的低级错误，比如右儿子写成
之类的。
2025.2.22 显而易见
今日歌曲：wish you were gay
A - 怎么又是先增后减 （[Atcoder joisc2014_b] [JOI Day2 T2] たのしい家庭菜園）
论赛时代码只与正解相差两行，赛时是有多糖。显而易见，一个数要么放左边，要么放右边。若放左边，则需要交换当前数与左边逆序对的个数，右边同理。显而易见，取较小的一侧的答案。用数据结构维护即可。
2025.2.25 数组开小
今日歌曲：mirrorball
-
神秘又简单的差分约束。显而易见，我们只关注在
到 路径上的点，并且 到路径上每个点的距离都是唯一的。那么有 。差分约束即可。 做的时候由于数组开小了，挂了若干发，也是糖丸了。
-
模板题。
2025.2.27 联合省选
今日歌曲：It’s Nice To Have A Friend
今天写了一点联合省选 2025 游记。
-
模板题。
-
不怎么板但码量极小的题。
我们要求的是满足
的无序二元组 的个数。由于我们并不知道 中的具体数值，只知道部分大小关系，又发现我们可以把上述和式转化为差式，所以维护两个数的差的范围即可。
2025.3
2025.3.1&2 正常说话
这两天参加省选。这里用正常的说话方式补充一些有关考试题目的内容。
-
钦定中位数为
，设可重集中小于 的数的个数为 ，等于的是 ，大于的是 ，那么有 ，所以 。为了让 尽量成为中位数，那么考虑让 尽可能大，即能取 的都取 。同时可以得到 的范围，便可判断。用差分维护即可。 -
先考虑打一个暴力，随后发现是区间覆盖（覆盖成
，其中 是给定值， 是下标。）与区间查询。线段树维护即可。（可是我不会告诉你我写的双 可能要挂分。）
2025.3.4 难度偏高
今日歌曲：The Lucky One
今天补了一下 USACO25JAN，铜组难度感觉偏高啊。
[洛谷 P11667] [USACO25JAN] Astral Superposition B
思维题。先处理
B，这两颗星星一定一颗在当前位置，一颗在左上方对应的位置。接下来处理G，如果当前位置能够由已有的星星移动而来，则忽略；否则当前位置需要一个星星。即可。[洛谷 P11672] [USACO25JAN] Table Recovery S
这题一直没改，今天终于改了。先统计出每个数出现了多少次，仅出现了一次的两个数中的一个便是第一个数。又由于第一个数所在的行/列中的每个数的出现次数是不重复的，于是就可以根据第一个数推出整个表格。比较两个答案中更小的一个输出即可。
2025.3.6 正难则反
今日歌曲：Naked In Manhattan
今天中午 C 老师请吃饭，回来就出省选成绩了。省选总分
今天略水。
[洛谷 P11672] [USACO25JAN] Reachable Pairs G
有趣的正难则反。对于
操作，相当于把当前点换成一个超级原点并不参与计数。所以考虑倒推，先建边（并查集合并）再加贡献。具体地，对于一条边 ，若： ：由于两个点都是超级原点，直接合并 所在的块。 ：当枚举到 时合并 所在的块。 ：当枚举到 时合并 所在的块。
枚举到一个点再加入贡献即可。
2025.3.8 打表可得
今日歌曲：Starlight
A - 114514
题目：定义函数
，其中 是一个长度为 的序列。这个函数的值 满足： 的长度为 。 中的元素互不相同。 。 是满足上述条件的序列中，字典序最小的。
现给定
，求有多少个序列 使得 。 题解：__
打表可得_，每个位置可能的值是独立的，即对于任意一个位置， 的取值集合不会随其他值的改变而改变。设 表示值 是否出现过，那么对于 的取值范围就是 ，其中 满足 且 $vis{l - 1} = 0$。并查集维护即可。 C - 深黯「军团」
题目：给定
与一个长度为 排列 。计算从 开始的接下来 个排列的逆序对个数之和。 题解：神秘数位 DP。这题赛时还是想到了许多，但是考试时误认为
的较高位不会改变，所以挂成 分（数据好水）。 赛时想到了通过求一个排列的逆序对来算排名，也想到了要求的就是排名在一个区间内的排列的逆序对数之和，还**
通过打表**想到了全排列的逆序对个数的 DP，甚至还想到了类似于阶乘进制的东西，可是因为不会康托展开而没写出来。具体地，将
与排列 康托展开。由于康托展开的值的数位之和就是逆序对个数，所以答案为 ，其中 表示 的数位之和。对于重复的部分，直接 DP 即可。
2025.3.11 观察样例
今日歌曲：Getaway Car
要改名了。今天 VP Codeforces Round 1008 (Div. 2)，打得烂的一匹，最开始只做了 A 和 B，不过幸好在 2:28 把 E AC 了，不然今天晚上整个人都不好了。
[CodeForces 2077A & 2078C] Breach of Faith
赛时一直在求
，然后就被卡死了。 事实上，发现
更好求一些。 。显而易见，把最大值作为 即可不重复。排序即可。 [CodeForces 2077B & 2078E] Finding OR Sum
神秘交互题。以下均讨论八位整数。观察样例发现，询问
似乎比较有用，可以直接得到 。再 根据直觉，考虑询问，将得到的答案 再减去 就可以得到 的贡献。为了不让每一位的贡献重叠，我们便想到空一个位置放一个 。这样，我们就可以根据这些数位的贡献来算出这些数位的和（指 对应数位之和）。剩下未知的数位也便可以根据 与已知的数位求出。显而易见，求答案时我们并不在意当前数位具体的值，只在意数位和。所以对于 的每一位只用分讨 或 即可。 这种题确实挺直觉的，个人觉得也比较靠运气。
比如我 C 想了半天就是想不到，这题基本是看一眼就有点想法而且就对了，甚至还是一发入魂。
2025.3.15 嗨克数据
今日歌曲：This Is Why We Can’t Have Nice Things
D - 完美的答卷
题目：给定长度为
的数组 ，设 ，求 。 题解：本题数据过水，以至于赛时对拍拍出了问题但是交到 OJ 上过了。赛时这题也想到了许多，可是逻辑并不清晰，最后还是看了题解并与 dpfs 讨论才想出了以下的解法。
钦定
是一个区间的最大值， 是这个区间的最小值，且 。设 表示 左侧第一个比 大的位置，则 ，且 在 的单调（递增）栈中，单调栈 + 01trie 维护即可。可是，上述两个集合的交集不一定从 开始，所以对于 trie 树中的一个节点 ，维护 表示经过该点的数的下标的最大值，便可以解决。可是删除又成为了一个问题。考虑用 vector 暴力维护每个 的历史值，理论上时间复杂度不变，只是常数巨大。 改完之后，就开始造 hack 数据了。似乎有用但不多。
2025.3.18 极限 AC
今日歌曲：Paper Rings
今天 VP Codeforces Edu Round 176。由于准备 VP 时 CF 还在系统测试，所以并不算严格意义上的 VP。最后一共做了 4 道，而 D 是在 VP 1:54 时才 AC，此前还有 3 发罚时。也是极限 AC。
-
先将
排序。发现对于某一种颜色，能够与其搭配的颜色都是连续的一段。所以前缀和并动态维护能够搭配的区间即可。注意略特判 的情况。 [CodeForces 2075D] Equalization
注意到花费不能重复，所以考虑背包 DP。设
表示将 右移 位、将 右移 位的最小代价，转移十分显然，即可 无脑做。然而由于我赛时太有脑了，非要写 ，最后调了好久才过。 下次再也不长脑子了。
2025.3.20 疑似双休
今日歌曲：I Hate It Here
后天不用上课，这周疑似可以双休了！
今天在补好题推荐。
[CodeForces 2078D] Scammy Game Ad
很符合“时下流行”的题目了。
考虑 DP，设
表示从第 个左/右门开始，到最后一个门的最大倍率。转移也是十分显然的。对于第 对门通过加法新产生的人数 ，将答案加上 即可。注意最初还有 个人。
2025.3.22
并不是双休，在家里 VP 模拟赛。
2025.3.25
打 USACO，菜得银组一道都不会。
2025.3.27
[CodeForces 2077C] Binary Subsequence Value Sum
极其有趣的题目了。
显而易见，
，所以一个字符串的权值 。把 换 ，那么 。继续将这个式子化简即可， 这里不再赘述。[CodeForces 2082B] Floor or Ceil
从二进制角度思考，向上取整等同于先加一再右移一位，向下取整则是直接向右移一位。所以，若一个向上取整操作后还有一个向下取整操作，那么这个向上取整操作相当于是无效的。又有在
次操作之后，最大值最多比最小值大一。所以对于最小值，先向上取整再向下取整即可，最大值反之。 [CodeForces 2081A] Math Division
考虑多操作一次的期望。多操作一次，则代表在第
位上产生了进位，又因为 ，所以前 位产生了进位（第 位是最高位）。设 表示前 位进位的期望，则： 直接 DP 即可。
2025.4
2025.4.1 愚人节
今日歌曲：Forever Winter
我的日祭之前断更了一段时间，今天终于补上了。
今天改不动题，于是在出题。
2025.4.6 水讨论区
今日歌曲：Guilty Pleasure
讨论区居然真的回来了，又可以水讨论区了（。
今天 VP Codeforces Round 1015, Div. 1 + Div. 2，赛后结算时，发现机房网络得了 MVP。详见犇犇。
前四题都是沟槽构造，不再赘述。
[Atcoder ABC400F] Happy Birthday! 3
考虑正难则反。问题转化为：
一个环上有
个物品，颜色分别为 ，每次操作选择两个数 使得 ，对 进行“漂白”，即将颜色都设为 。一次操作的代价为 。求将整个环漂白的最小总代价。 先断环为链。设
表示将 漂白的最小代价，那么显然有 。 设
表示使 能够漂白的最小代价，那么显然有 。当 时，有 。 答案即为
。 [Codeforces 2086E] Zebra-like Numbers
确简单的啊，可是自己就是想不到。
考虑计算一个数的斑马值。贪心地，尽量选大的斑马数减即可。
考虑记搜，设
表示 中斑马值为 的数的个数。那么显然有 ，其中 是不大于 的最大的斑马数。具体地， 表示 中斑马值为 的数的个数， 表示 中斑马值为 的数的个数。
2025.4.8 过水了
今日歌曲：it’s time to go
过水了今天。
2025.4.10 证明略
今日歌曲：The Albatross
[Atcoder ARC196A] Adjacent Delete
唐题啊，可是和我相比还是我更唐。
假设
是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 大的数（记作“较大数”）的和减去前 小的数（记作“较小数”）的和。 容易发现，当我们只能选相邻数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。
当
是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶堆维护前后两段的答案即可。 [Atcoder パ研合宿2024 第3日 E] Roller Coaster
人类智慧啊。选高度差最大的边即可。证明略。
[Atcoder パ研合宿2024 第3日 G] Bracket Sequence
极一眼啊，大概十分钟切了吧。跟翻转括号序列的一个区间那题差不多，这题还简单一点。
注意到位置
可由 与跟 位置高度相同的位置转移而来。拿一个桶维护后者即可，遇到右括号时记得清零。
2025.4.12 写了跟写了一样
今日歌曲：august
模拟赛。
A - 倒水
题目：有三个容量分别为
的杯子与一个容量为 的一个桶，每次可以： - 把一个杯子灌满；
- 把一个杯子的水倒出去；
- 把一个杯子的水倒到另一个杯子直到这个杯子空了或另一个杯子满了；
- 把一个杯子的水倒到桶里。
对于
中的每一个 ，求要使桶装满水，最少的操作次数。 题解：
发的题解写了跟写了一样。 容易发现，经过转化，可以得到两种操作：向桶里加
单位水与从桶里舀出 单位水回到对应的杯子（后者是操作一与操作三的结合），每次操作的代价都为二。注意到，对于某一个水杯，若我们用它进行的最后一个操作是操作二，那么代价为一，因为不用把舀出来的水倒出去。设 表示桶里有 单位水的最小代价， 表示三个水杯是否最后用于操作二，那么先正着 DP 一遍，即全部使用操作一，再反着 DP 即可。统计答案时应统计 。 B - 让他们连通 （[Codeforces 1706E] Qpwoeirut and Vertices）
居然能场切
。 要让区间
连通，等价于 ， 与 连通。设 表示 与 连通的时间，则答案为 ，可以用 ST 表维护，常数又小又好写。 对于
，考虑启发式合并。在合并时，枚举较小的集合的元素，并判断它是否与另一个集合中的元素相邻即可。赛时因为没判 被硬控了半个小时。
2025.4.15 不想证明
今日歌曲：cardigan
-
无脑做啊，不想证明。
[Atcoder パ研合宿2024 第3日 H] Big XOR Game
这题评分比括号序列还要低。从高到低讨论，对于每一位，设当前位上是
的数的个数是 ，那么有： 1
2
3
4
5if(((cnt + 1) / 2) & 1 and (cnt / 2) & 1 ^ 1) Alice;
if(((cnt + 1) / 2) & 1 ^ 1 and (cnt / 2) & 1) {
if(n & 1) Bob;
else Alice;
}不想详细说明。
2025.4.19 输入挂了
今日歌曲：Sad Beautiful Tragic
TTPD 一周年了。
今天模拟赛因为输入挂了 暴涨暴跌。
A - 说唱入门教学
题目：给定一首歌的歌词（以拼音形式），每两句话一一匹配，
，求出 押的个数。 题解：题面好唐。先把韵母处理出来，然后 trie 树即可。常数极大。
B - 画画入门教学
构造题，手动推一推小样例即可。
2025.5
2025.5.5 了跟了一样
今日歌曲：Fifteen
又断更了半个月。
前几周学了一下 AC 自动机，但是学了跟学了一样。
前几天终于把那套题出完了，但是出了跟出了一样。
昨天考试，听了评讲，但是改了跟改了一样。
晚上打 ARC，但是打了跟打了一样。
[Atcoder ARC197C] Removal of Multiples
唐题啊，但是赛时一直在想整除分块之类的，结果没想出来。
但是这题也就真纯唐，用线段树维护区间内留下的数的数量即可。需要证个上界。
[Atcoder ARC197D] Ancestor Relation
好题啊好题。记
表示矩阵的第 行的内容（用 bitset 维护）。 考虑什么时候有
。因为与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。所以有 或 ，前者对应 是 的祖先，后者则对应 是 的祖先。容易证明这是一个充要条件，那么若 ，则一定不存在 与 。 接下来考虑一种特殊情况：
，此时 在一条没有任何分岔的一条“链”上，那么这条链上的节点的位置就可以互换。设一组 相同的点的数量为 ，那么这一组点可以带来 的贡献。 此外，
，显然需要有 。那么我们就总结出以下三条条件或贡献： 。 或 ，当且仅当 。（等价于： ，当且仅当 或 。） - 对于极多的
个 相同的数，可以带来 的贡献。
于是按以上三点计算即可。
2025.5.18 宇宙射线
由于宇宙射线的影响，这里遗失了一篇日祭。主播不想补日祭了。
前几天又断更了，应该是在补 CQ CCPC 的题吧。主播不想补日祭了。
（我明明写了的，可不知道这篇日祭怎么就消失了。）
2025.5.22 主播不想补日祭
今日歌曲：High Infidelity
前天又学了一下 exgcd。主播不想补日祭了。
今天考试。
A - 三重移位 （[Atcoder ARC136B] Triple Shift）
略为神秘。观察到，进行一次操作后，逆序对个数的变化量一定是偶数，所以
与 的逆序对个数的差值必须是偶数。另外，当 中存在重复的元素，那么相当于可以造一对逆序对出来，此时一定有解。 B - 最小差分和 （[Atcoder ARC147C] Min Diff Sum）
题解。
更好的做法如下：假设当前
有序，那么可以拆贡献。拆下来是 。于是让 尽量小， 尽量大。将 降序排序，将 升序排序即可。（主播不想写了，看不懂就去看原题题解吧。） C - 前缀与后缀 （[洛谷 P9180] [COCI 2022/2023 #5] Slastičarnica）
[To do]
D - 贪吃蛇 （[洛谷 P7078] [CSP-S2020] 贪吃蛇）
[To do]
2025.5.24 竟然草过去了
今日歌曲：You’re on Your Own, Kid
今天叕考试。
A - 红魔乡 （[TopCoder 15693] Fixed Point Reversals）
显然好做。把翻转区间看成交换元素即可，唯一的限制是当交换的两个元素在
的两侧时，这两个元素需要关于 对称。 B - 妖妖梦 （[洛谷 P4576] [CQOI2013] 棋盘游戏）
当且仅当黑棋和白棋出生在一起时，白棋能赢，否则赢家一定是黑棋。那么黑棋就尽量快速解决战斗，白棋就尽量多拖延，所以白棋转移状态时取最大值，黑棋选择状态时取最小值即可。
C - 永夜抄 （[TopCoder 10945] Rectangular Island）
long double还是太玄学了，竟然草过去了。发现左右移动和上下移动其实是相对独立的，所以单独处理即可。设表示在左右方向上移动了 步，还在格子里的概率， 同理，它们是可以 处理出来的。接下来枚举 表示左右方向上移动的次数，那么此时的贡献应该是 。 显然容易维护，可是发现 这东西容易炸掉，又发现在计算 和 时一共恰好迭代了 次，所以在计算 和 时每迭代一次时乘上 即可。 D - 花映冢
题目：给定一个图，点数和边数都是
级别的，可能有环、自环和重边，求是否存在一条从 出发的路径可以经过所有点至少一次。（可以重复经过边或点）。 题解：显然先把自环和重边判了，接下来 Tarjan 缩点，再拓扑排序即可。
2025.5.26
今天补题。见 5.22 与 5.24。
2025.5.29
今日歌曲：Cruel Summer
今天继续补题。见 5.22。
2025.6
2025.6.2 问我怎么挂的
今天做题。
[洛谷 P2833] 等式 & [SGU 106] The equation
板子题啊，可是改了好久。主要死在向下、向上取整时没用
double（因为有负数）。[SPOJ NWERC11A] Binomial coefficients
这道题自己想到了枚举
，二分 ，也想到了会爆 long long，可是没想到枚举。对于
，进行二分；对于 ，枚举即可。 做的时候因为各种小问题挂了
发。 -
挺简单的呀。问我怎么挂的，其实是把
写成 了。还有另外一些小错。（比如步长写错了，还有负数导致的一些奇怪的问题。） 枚举
与每一对人，解 即可。 -
没想到是打表题。打表发现满足要求的九位数有
个，十位数自然就有 个。（原有基础上在开头加一个数。）十位数以上，每多一位，答案自然就 。九位数以下答案为 。
2025.6.3
-
神秘结论题。设
。模拟一个倒推的过程，容易发现，当且仅当 时有解，其中 是奇数， 是整数。若有解，模拟即可。
2025.6.27
也是莫名其妙断更了一个月。
也是终于把别样的 whk 草过去了。
今天补日祭。
欧拉函数、欧拉定理与线性筛专题
- 欧拉函数
- 欧拉定理
- 满足
的数的个数 满足 的个数 。
利用以上结论即可完成：
[Codeforces 1149D] Abandoning Roads
CF 3000* 远古题，洛谷黑，所以也算是首黑吗。
这题复杂度鬼能想出来。
首先先把重边断掉，这样就会形成若干个连通块。将这些连通块“缩点”之后，用 dij 做新图的最小生成树即可。具体地，设
表示当前在第 个点，已经到达的连通块为 的最短路径。显然每个连通块只会被访问一次，所以复杂度是 的。注意到当一个连通块的大小 时，若先离开这个连通块再回到这个连通块，至少要经过 条重边，而走连通块内部只需要最多 条轻边，所以显然不需要考虑这个连通块，因为跑 dij 的时候显然会选择走连通块内部而不会重复经过。那么连通块数量被优化到了 ，时间复杂度 。
2025.6.30
今日歌曲：Down Bad
昨天终于也是稳 1= 了。
这高中语文老师还是非常正常，但是这高中英语老师是比我还抽象。
今天补题。
[Atcoder ARC180D] Division into 3
很久之前一场模拟赛的题了。
一件显然的事情，就是一个区间的最大值
一定会做出贡献。若 放在第二段，那么当第一段与第三段的长度为 时可以取到最小值，用 ST 表维护即可。若 放在第一段，那么当第二段长度为 可以取到最小值。设 ，那么答案即为 。将询问离线再用单调栈与线段树维护 即可。若 放在第三段，则与放在第一段类似。 -
这道题显然是之前记过的，今天终于补了。
2025.7
2025.7.1 好的标题
为什么你不写标题了呀？——@O_v_O
因为没想到好的标题。——@Getaway_Car
另外，注意到，我一月到六月的日祭数量如下：
| 月份 | 数量 | 有标题数量 |
|---|---|---|
我们的日祭正在蒸蒸日下！
[Codeforces 1610G] AmShZ Wins a Bet
CF 3300* 远古题，洛谷黑，所以也算是第二道黑吗。
赛时想到了每次删除的是一段合法的括号序列，可是竟然连最基本的 DP 都没想到，how sweet！
考虑倒序做，设
表示 的答案，那么它可以由 与 转移而来，其中 是能与 匹配的第一个位置。时间复杂度 。 发现比较字符串还是太慢了，所以考虑使用倍增与哈希实现字符串比较，具体实现类似于树上跳 LCA，一直跳直到
跳到边界或者 ，即可知道两者的大小关系。
2025.7.2
-
我还是太唐了，这样的唐题都不会。
设
表示 的子树中， 目前度为 的最大答案。直接转移即可。 -
对于任意两条相邻的边
与 ，答案不会超过 ，因此可以初步确定答案上界 。另外，看到最小值的最大值，很容易想到二分。二分答案 ，那么有对于任意在同一集合内的 ，满足 。转化一下，即对于任意 满足 ，都有 不在同一集合内。那么我们可以把所有满足 的边 建出来，当且仅当新图是一个二分图， 合法。此时时间复杂度为 。又注意到，对于新图中两个点 ，存在关系 ，由于 是原图中相邻两条边权值和的最小值，而 ，这意味着 一定在原图就已经相连。所以只需要从原图上把满足 的边拿出来建为新图即可。时间复杂度 。
2025.7.3
[Codeforces 407D] Largest Submatrix 3
一道唐题，可是竟然不会。
设
表示下界为 、左界为 、右界为 的最小上界。注意到 ，发现在这基础上，还需要满足 。维护 表示第 列中 最后一次出现的位置即可。注意要特判一下 。 -
第一眼感觉这个题好像来财啊。我们把每次操作剩下的左侧的两张牌叫做手牌。考虑什么时候能够产生贡献。
三张新牌相同。此时手牌状态不变。
有两张新牌相同，且手牌中有一张与它们相同。此时会将手牌中的相同的那张打出，并换来新牌中不同的那张。
两张手牌相同，且新牌中有一张与它们相同。此时会打出两张手牌，并换来新牌中不同的两张牌。
上面三项对应的状态更新如下。（
默认取 ） - 直接全局
。 - （假定
） - （假定
与两张手牌相同）
引入通配符
，表示 。以下是无贡献的状态更新。（ 可相互替换。） 容易发现每一轮一共只有
级别的状态更新，所以我们只需要在当前状态的基础上修改即可。另外注意，以上所有操作都是同时进行，所以需要提前存储操作信息。时间复杂度 。
2025.7.4
-
推式子即可。并不想打公式，
详见原题题解。 [Codeforces 1114F] Please, another Queries on Array?
看题的时候没看到，所以想了一会儿直接去看题解了。 要维护区间乘与区间积的欧拉函数，发现区间积可能很大，不能直接分解质因数。所以考虑维护原数的质因子，发现
的质数个数恰好是 ，可以用 long long维护。而一些数的乘积的质因子状态，即其中每个乘数的质因子状态的或和。区间修改也是类似的道理。
2025.7.6 蒸蒸日上
这已经是七月的第
2025.7.7
今天 VP Codeforces Round 1036, Div. 1 + Div. 2。
[Codeforces 2124E] Make it Zero
沟槽的构造题，并不想记严格的证明。大概就是找到一个位置
满足 ，然后分为 三段，设三段的和分别是 ，我们只需要找到一个 使得 ，接下来可以在两步内解决。再把前两步合并，就变为了第一段清空，第二段减去 ，第三段减去 ，剩下的就是第二步。
2025.7.8
模拟赛挂了
第四题不会，所以也没什么题需要改。
2025.7.9
-
要使这条边端点颜色相同，且删掉这条边后图形成二分图，那么这条边在所有奇环中，且不在任意一个偶环中。
考虑建 DFS 树。对于树边，我们可以通过树上差分维护出当前边属于的奇环与偶环数量。对于非树边，根据奇环数量来讨论：若有且仅有一个奇环，则该非树边合法；若有多个奇环，且存在一对奇环没有交集，那么没有树边合法；若有多个奇环，且这些奇环都相交，那么必定会形成更大的偶环，那么没有树边合法。综上所述，只用讨论合法的树边数量，并特判奇环是否只有恰好一个即可。
2025.7.10
B - 树
题意转化后即动态维护树的直径，具体需要支持向树中加点。
考虑当两棵树合并的时候直径会怎样。容易发现，新树直径的端点一定由原树直径的端点产生，一一判断即可。考虑使用线段树维护区间直径，支持单点修改即可。
2025.7.12
线段树合并要把我的左脑和右脑合一起了。
这篇日祭是线段树合并学习笔记，未来会有补充。
线段树合并顾名思义，就是把两棵线段树的信息按照特定的规则合并起来，一般与动态开点配合使用。
线段树合并常用于优化 DP，尤其是树形 DP（与 DAG 上的 DP），用来优化 DP 转移。（或者是一些需要在树 / DAG 上进行信息转移的东西。）
比如一个树形 DP 的转移方程如下：
$$
dp_{u, i} \mathop{\leftarrow}{v \in son(u)} dp{v, ?}
$$
我们需要将儿子的信息转移到父亲上，而每个节点存储的又是一个数组，常规的做法是一一合并，转移的时间复杂度为
而对于一些转移方程，我们会发现合并信息的操作可以用线段树合并来优化。于是我们就将转移的时间复杂度优化为了
具体的，假设现有
可这时我们会发现，开
于是你就写出了线段树合并。
-
首先可以把区间修改通过差分变成单点修改。
对于
，我们需要维护它每种救济粮的数量与最多的救济粮的种类，显然使用线段树维护。因为我们做了树上差分，所以 DFS 的时候要做一次树上前缀和，即将 和 合并起来。 于是就做完了。时间复杂度
，但常数极大。 另外记一种树链剖分的做法，其实就是离线的树剖。
先正常树剖一下，然后你就会得到
个 dfn 序连续的区间。 由于是离线，所以可以用差分标记这些区间。
所有操作结束后，用权值线段树进行一次前缀和即可。
时间复杂度
，常数极小。 【TBD】
2025.7.13
A - [UVA 12170] Easy Climb & [SPOJ CCROSS] Cross Mountain Climb
赛时基本想到了但是没做出来。显然有
的朴素 DP（单调队列优化）。 可以感知到，
。（我也不知道我赛时是怎么感知到的，总之就是感知到了。） 即，
，那么有效的值的个数就来到了 。（为什么我想到了又没做出来呢？因为我思考的时候把 取到 了，然后就不会了。） 进行一下离散化再 DP 即可。
B - [黑暗爆炸 4160] Exclusive Access 2
赛时写了一个没有正确性的乱搞做法，得了 70 pts。
我们可以把原题转化一下，看成把原图分成若干层（若干部，更严格的说法是用反链覆盖原图，即 dilworth 定理），使得每一层内两个点互不直接相连，求最小层数。发现就是求图的色数。先
预处理一个子集是否有直接相连的元素，再 做 DP 即可。
2025.7.14
-
一个做法是直接取
条鹅卵石路。 可是发现这么做没有正确性。
因为容易发现有一些鹅卵石路是必选的。
那么我们可以先做一次 kruskal，并且先选水泥路，再选鹅卵石路。第一次被选中的鹅卵石路就一定包含了必选的鹅卵石路。
所以接下来只用再做一次 kruskal，先取够
条鹅卵石路，再取水泥路。 [洛谷 P8386] [PA 2021] Od deski do deski
看了题解觉得很简单但是自己就是做不起的 DP。
首先容易发现一个合法的序列一定可以表示为若干个首尾相同的串相连。
换句话说，我们可以在一个合法的序列后面再加上一个首尾相同的串以得到一个新序列。
再换句话说，对于任意一个序列，我们可以通过在末尾增加一个特定的元素，让它与原序列中的某个相同元素匹配成一个区间，以让新序列合法。
考虑 DP，设
表示考虑了 ，当前有 个左端点（新数与它们匹配后能使新序列合法，并且它们被匹配一次后依旧可以被匹配），当前序列是否合法的方案数。那么有四种 DP 转移。 ，新加的元素与左端点匹配，原本合法的序列现在依旧合法。 ，原本合法且有 个左端点，现在增加一个无法匹配的元素使它不合法，但增加了一个左端点。 ，原本的序列不合法，现在增加了一个可以匹配的元素，使新序列合法。 ，原本不合法的序列，现在加一个无法匹配的元素，依旧不合法。
答案是
。注意到 ，所以时间复杂度是 。 HJJOI Day2 A 堆
先转化一下题意，看成先插入元素再删除元素。注意到，如果插入的元素是当前的最大元素，那么直接删除它；在这样的条件下，其它被删除的元素一定是单调不增的。所以只需要一个桶与一个指针维护当前的最大元素即可。
-
题解。
[LOJ 6029] [雅礼集训 2017 Day1] 市场
挺有趣的势能线段树。
看到取模、开根这一类运算容易想到势能线段树，除法也是。但这道题的难点就在于难以看出是哪个数据最终会趋于不变。
动用人类智慧，发现是极差。对于加法操作，并不会改变极差，而除法至少可以让极差减半，即在
次内变为 。 先写一个正常的线段树，然后单独实现除法操作。
注意到，当一个区间的极差为
即所有元素相同时，区间除法相当于区间加法，所以直接做一个区间加标记即可。 另一个可以像上面这样处理的情况是，最初极差为
，操作后极差依然为 ，此时区间除法与区间加法也是等价的。 单独讨论一下上述两种情况并直接返回，其它情况继续递归下去即可。
时间复杂度是
，不会证。 在 sjx 的讲义中，还讨论了最初极差为
，操作后极差为 的情况，此时区间除法等价于区间覆盖，所以似乎还要单独实现区间覆盖，导致代码更屎，所以干脆不讨论这种情况，直接暴力递归即可。（甚至可能会赢过两个 lazy tag 的常数。）
2025.7.15
-
终于也是洛谷首黑了。这题的转化好妙啊。
美丽的定义的转化如下：对于任意一个白点，它的子树中都是白点
对于任意一个黑点，它的父亲一定是黑点 所有的黑点构成一个连通块 黑点个数减去黑边个数等于 。当一棵树是美丽的，因为所有黑点构成一个连通块，所以白色连通块的数量等于黑白边的数量。于是我们就可以用一棵线段树维护每个时刻的黑色连通块数量（即黑点个数减去黑边数量）与白色连通块数量（即黑白边数量）。对于每一条边，容易处理出它在哪个时间段是一条黑边（可以给黑色连通块数量带来 的贡献），在哪个时间段是一条黑白边（可以给白色连通块数量带来 的贡献），当然改边也是容易处理的，实际就是撤销一条边再加一条新边。 这个时候还缺了一步。我们要求的并不是每个时刻的白色连通块数量之和，而是黑色连通块数量为
时的白色连通块数量之和。我们可以通过维护黑色连通块数量的 与当黑色连通块数量取到 时对应时刻的白色连通块数量之和 来解决这个问题。修改白色连通块数量时，我们只需要将 加上 即可。由于在第 个时刻（与第 个时刻）黑色连通块数量一定为 ，所以 一定为 。 -
这不是人类智慧是什么？
先考虑离线下来，记
表示位置 被切割的时间，那么依次处理区间 ，就可以做到实时记录 。对于一个区间，发现它在随机数据下，长度会快速减小，且最多被切割 次，所以可以每次直接找到当前区间内 的最小值，然后从最小值对应位置处切割。但是对于非随机数据，一个区间可能会被切割 次（从左往右切），显然不能沿用上面的做法。区间被切割的次数多的原因是有许多切割的位置都很靠近端点，导致长度减小缓慢。所以我们充分发扬人类智慧，对于一些靠近端点的切割操作，直接更新端点；对于一些处于区间中部的切割操作，再沿用上述做法。 可是“靠近端点”具体又应该是处于区间的什么位置呢（比如前
）？或者说“区间中部”的长度应该取到多少，才能既保证正确性又保证时间复杂度呢？ 若中间块太长，则会导致区间长度减小依然缓慢，而当中间块较短时则可保证区间长度较快减小。所以我们要尽可能最小化中间块长度。若中间块太短，在进行一系列对区间两端的切割操作后，我们并不能保证中间块一定会被保留下来；而当中间块长度大于两侧长度时，在进行一系列对区间两端的切割操作后，我们一定可以保证中间块被保留。综上所述，我们只需要将区间三分即可。
具体实现上，我们需要一棵线段树维护
，它需要支持单点修改、区间查询（查询区间中间段的最小值）、查询给定位置左 / 右侧第一个小于给定值的位置（查询两端的切割情况）。对于第二类查询，需要使用线段树二分。对于区间的迭代，只需要按题解模拟即可，先直接更新左右端点，再进行区间切割。时间复杂度 。 [Codeforces 461B] Appleman and Tree
设
表示考虑到第 个点，当前点是否与黑点在一个连通块的方案数。转移时直接考虑是否删除当前边即可。 -
直接考虑染色对答案的贡献。设
表示考虑到第 个点，以当前点位根的子树中有 个黑点的贡献。做一个树上背包，价值是以儿子为根的子树与其他节点能产生的匹配次数（即经过当前边的次数）乘以当前边的权值。注意转移时要控制好变量的上下界，否则会被卡成 。
2025.7.16
踩一脚 2025.1.17，现在比那时候还是有了一些进步。（现在很难想象之前有段时间天天都只考几十分，接近垫底，但是竟然没觉得什么。）
怎么说呢，教练和家长也都给我聊了好多次了，也是该到努力的时候了。我之前确实学习就没有真正用过全力，所以今天教练说我潜力很足，我也这么认为。只是说面临的困难也挺多的，比如我心理上的一些问题。我无法解决，所以只有尝试不想那些事情，尝试逃避问题。
今天上午考试，一道不会。下午应该是因为天气比较热，所以人有些浮躁，状态不是特别好，效率很低，听课也没怎么听进去，一天只做了一道题，也是成为了 HJJOI 集训期间的前缀最小值。
[Codeforces 1967D] Long Way to be Non-decreasing
就当是学习基环树了。
赛时看出来这题与基环树有关，可是居然没看出来是二分（打脸）。
二分答案
，转化为判定性问题，我们需要对 中每个元素操作最多 次使其单调不降。由于目标是单调不降，所以只需要使用一个变量 表示当前 中的最后一个元素，那么一个新元素就需要在 次操作以内变为一个不小于 的数。将 从小到大枚举，找到最小的 满足这个新元素可以在 次操作以内变为 ，若 则无解，否则有解。 那么现在就转化为了计算一个数在几次操作后能变为另一个数。对于所有
建图，此时会形成一个内向基环树森林，我们只需要计算基环树上两点的距离，就是一个数转化至另一个数的操作次数。 对于基环树的处理，可以使用并查集维护连通性，形成环时忽略当前边，使其形成一棵树。计算两点距离时需要分讨一下两点的位置关系。
2025.7.17
这两天状态不好，所以 7.17 和 7.18 都没做什么题，日祭也是 7.19 才补的。
-
长链剖分的主要用法就是求树上
级祖先和优化 DP。优化 DP 就类似于 dsu on tree，只是一个与树的大小有关，一个与树的深度有关。 求树上
级祖先的方法如下：树剖时对于长度为 的链，需要预处理出链顶的 级祖先与 级儿子（即链中元素）。另外还需要预处理出 级祖先。对于每组询问，先向上跳 ，此时当前点所在长链的长度至少为 。接下来再跳到当前链链顶，再向下或向上把剩下的跳了。
2025.7.18
[P4719] 【模板】动态 DP & [P4751] 【模板】动态 DP（加强版） & [P5024] [NOIP 2018 提高组] 保卫王国
三倍经验是个好东西。
并不想记具体的过程，所以就大概记一下。
对于 P4719，可以先写一个朴素的 DP。对于每一次修改，就需要更新从当前点到根路径上的每个点。因为是路径更改，所有考虑
熟练剖粪树链剖分。尝试把原来的 DP 方程写成一种神秘的矩乘形式，然后对于每一次修改就变成了修改路径上轻边的转移方程（矩阵），答案就是整棵树重链上的矩阵的乘积。对于 P4751，我们只需要使用动态开点线段树，对于每一条重链单独开线段树，这样可以减少线段树的查询次数，可以优化至少
的常数。 对于 P5024，容易注意到最小覆盖集 = 全集 - 最大独立集，那么就可以直接做了。对于修改操作，若要强制选则将权值设为极小值，否则将权值设为极大值。注意算出来的答案是改变权值后的答案，所以输出时还要稍微处理一下。
2025.7.21
[洛谷 P8352] [SDOI/SXOI2022] 小 N 的独立集
DP 套 DP 板子。设
表示考虑到点 ，强制不选的答案为 ，不强制不选的答案为 ，直接转移即可。（其实是我不想写。） [洛谷 P5904] [POI 2014] HOT-Hotels 加强版
长链剖分优化 DP 板子。
对于原题，容易写出一个
的 DP，发现 DP 数组的大小与深度有关，所以进行长链剖分即可。
2025.8
这个月的日祭直接写一起了，基本都在补题。
注意到 7 月份后来状态不好。
-
考虑用一棵普通线段树维护，每个节点维护区间的最大值与区间内好的序列的长度，push up 的时候需要写一个类似于线段树二分的东西，时间复杂度
。 [洛谷 P9824] [ICPC 2020 Shanghai R] Fountains
复杂度好神秘的一道题。
自己写写不清楚，所以干脆看题解吧。[洛谷 P6189] [NOI Online #1 入门组] 跑步
显然可以 oeis。本题就是正整数拆分问题。考虑正整数拆分的做法。一种 DP 是设
表示用了 ，当前和为 的方案数，转移是 。另一种 DP 是设 表示选了 个数，当前和为 的方案数，转移是 。发现第一种 DP 与拆分的数的值域有关，第二种与拆分的数的数量有关。所以考虑根号分治，对于 的数进行第一种 DP，其它的进行第二种 DP。 [CWOI 0819 B组] C - 盲盒流水线
注意到这场因为 B 屎一样的题面搞乱了节奏？（不要给自己找借口了。）不过要是 JDS 不提醒我 A 可能要挂完。
题意是区间背包。因为是区间，容易想到用数据结构维护。注意到背包可以
合并，那么写一个普通线段树的时间复杂度是 ，空间复杂度是 。慢的原因是合并次数太多，所以考虑减少合并次数。发现这个过程是静态的，所以选择猫树。可是发现直接猫树的空间复杂度是 ，所以需要把询问离线下来，每个区间单独处理即可。 P13736 [JOIGST 2025] 日本浮现 / Japan Emerges
气死我了怎么绿题都场切不了。（注意到可能是做提高组模拟赛有点膨胀导致的。）
看到连通立马想到并查集（为啥我没立马想到），看到最小立马想到二分答案转化为判定性问题，判定的时候按题意模拟即可，如果两个块会相连就合并起来。
-
注意到祖先的盛开度一定比孩子大，因为如果交换两个点的盛开度会导致答案不增。所以对于每个点，它的美丽度取的点的位置是固定的，所以可以统计对于每个点，它的盛开度会被作为多少个点的美丽度（记作
）。若我们选择 朵花送出，相当于要选若干个点使得 ，最大化 ，发现 一定是一个包含根的连通块，所以直接树上背包即可。 [CWOI 0822 B组] B - 美丽值
题意略。容易想到拆贡献，考虑
一段会被计算多少次。设 中有 个数 ，剩下的 个数 ，那么 会被计算 次。接下来考虑有多少个序列满足上述条件。首先从 个数中选 个数钦定为 ，那么 个数就可以任意在 中生成，剩下 个数同理。所以总答案是 。 [Atcoder ARC101C] Ribbons on Tree
考虑容斥（？，注意到我不会容斥，是怎么考虑到的），答案为
，其中 表示强制断开的边集为 的方案数。注意到断开若干条边后，形成了若干个独立的连通块，那么每个连通块的方案数就是 （当 是偶数时）。所以直接树上背包即可。 [Atcoder ARC153D] Sum of Sum of Digits
好神秘的 DP。
发现难点主要在于进位。设
表示考虑到第 位，上一位有 个数向这一位进了位，目前答案的最小值（不包含当前这一位）。对于每一位，先对 按当前这一位从大到小排序，那么进位的数字一定是 的一个前缀。接下来就是直接转移，枚举进位个数、 当前这一位的值，然后统计当前数位的和与进位个数，再转移到下一位即可。 [CWOI 0824 B组] A - town
题意是将树分为若干个连通块，要求每个连通块的权值的异或和为
，求方案数。 显然容易想到做树上背包，并且记录当前未闭合连通块的异或和。发现未闭合的连通块的异或和一定是
或 ，所以只用设两个状态。需要特判 （赛时被这个 Corner Case 创飞了。） [CWOI 0824 B组] B - str
很显然的 DP，处理 LCP 即可。但是赛时写的什么 KMP 处理 LCP？什么东西？
[CWOI 0824 B组] C - perm
什么惊人的注意力。
显然与置换环有关。把每个置换环拿出来，设大小为
，那么答案就是 ，其中 表示大小为 的置换环的解数，然后出题人注意到 ，特别地， 。
Codeforces Round 1044 (Div. 2)
D - Chicken Jockey
E - I Yearned For The Mines
发现当树是一条链时是容易的（废话），所以考虑先使用最多
次 类操作把树分为若干条链，再用 次操作检查每一条链。考虑如何在限定次数内将树分为链。我们尝试对树上的点分为以下三类： - 链的端点；
- 链的中间点；
- 执行
类操作的点。
我们可以通过一次 dfs 来确定点的类型。具体地，对于点
： - 若
的儿子中存在一个中间点，或存在至少 个端点，那么 是操作点； - 否则，若
的儿子中恰好存在两个端点（且不存在中间点），那么 是中间点； - 否则，
是端点。
于是我们就找出了需要执行
类操作的点集。 F - Flint and Steel
令
。 容易想到一个朴素 DP：设表示炸死 的苦力怕最少需要引燃多少只苦力怕，有转移 ，时间复杂度 。考虑优化，设 表示炸死 的苦力怕最少需要引燃多少只苦力怕，那么 DP 转移就可以通过线段树来优化，实际复杂度 。
Codeforces Round 1045 (Div. 2)
D - Sliding Tree
在 CF Div. 2 D 放极弱的样例的出题人，愿你们的母亲在天堂相遇。
根据直觉容易想到与直径有关，然后就会自然地想到移动直径上的每一棵子树，然而这样是错误的。正确的做法应该是把直径的一端移到子树上，那么操作次数就应该是
，其中 为直径的长度。至于为什么这样是最优的应该口胡一下可以怔出来，但是不想怔了。 E - Power Boxes
实则并不难，只是赛时死磕 D 去了。赛后自己补出来了，虽然用时有点久。
设从
开始的弹跳次数为 ，那么显然有 ，初始值是 。显然会倒着询问。对于 ，若 ，那么我们询问 即可得到 的值。否则，我们可以直接推出 ，但并不知道 的值。注意到，若 ，因为 ，我们一定可以通过一次询问直接确定 。接下来，我们只需要交换 与 ，原来的第 个盒子现在成为了第 个盒子，又有 ，所以我们可以通过一次询问直接确定 。若 ，交换 与 即可。根据上述过程易证需要 次询问。
Codeforces Round 1046 (Div. 1, Div. 2)
B - For the Champion
被随机区分导致掉大分了呜呜呜。
注意到赛时就想到了移到角落，然后就不会了，男蹦。
移到两个角落就可以得到
与 了，然后就做完了。 C - By the Assignment
发现一个图是好的的充要条件是，每个环上所有点的点权都应该相同，这等价于每个边双中的点的点权应该相同。特别地，奇环上所有点的点权都应该是
。所以我们只用找出每个边双联通分量，判断其中已确定点的点权是否全部相同，并且是否存在奇环即可。 D1 & D2 - From the Unknown
注意到我赛时基本会 D1 了，然后饭堂了以为自己是错的？然后开始考虑优化，想到了 D2 正解的
？然后最后 D1 & D2 都没做出来？啊？ 设
。对于 D1，容易想到的是第一次询问 个 ，得到 的大致范围 ，满足 （好像赛时就是 推错了，导致没推出 ？）。接下来要确定 的具体值，于是考虑询问 l 1 l 2 l 3 ... l (r - l)，有。 对于 D2，考虑优化。（以下是赛时想法）发现我们没有把
利用起来。于是考虑利用根号分治与数论分块的思想，第一次询问 个 ，若 则说明 ，否则 。若 ，则考虑询问 个 ，此时每个 都对应一个互不相同的 ；否则，沿用 D1 的思想即可。但是发现这样的询问次数依然可以达到 ……（以下是正解）发现以上有些数值取到 时不一定最优，于是重新设常量 表示：第一次询问 个 ，若 则第二次询问 个 。通过暴力可以求出，当 时询问次数可以控制在 以内。若精细实现，询问次数还可以再少一点。
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 暴力，时间复杂度
。考虑反过来，对于每个 ，有哪些数与 异或能取到最小值，再简单拆贡献计算答案即可。时间复杂度 ，精细实现可以做到 。（感觉做法好抽象，讲不清楚。）
2025.10
Codeforces Round 1055 (Div. 1 + Div. 2)
我好菜。
D - Division Versus Addition
赛时比较早就想到了大概的做法，但是没写（？）。首先发现
的数显然没有贡献（操作它则严格不优），而其它数是可以有贡献的。但是观察样例发现 可以没有贡献，即满足 的 ，若 A 先操作一次，那么这个数就没有贡献了；而对于其它数，就算 A 操作了也依然可以有贡献。对于上述这类数，A 可以让其中的一半（向上取整）取消贡献。所以答案就应该是原本的操作次数 + 有贡献的数的数量 - 特殊数的数量的一半向上取整。 E - Monotone Subsequence
好难绷的题。第一次考虑对于全局询问，如果答案序列的长度
直接返回。然后你发现要是再询问答案序列中的元素好像没什么用，所以下一次就询问除它们以外的元素。于是这样询问 次，如果中途答案序列长度 就直接返回。如果 次之后依然没有答案，那么现在一定还剩下一个元素。考虑构造一个下降子序列。发现对于一个在第 轮中被询问的元素，在它左侧一定存在一个在第 轮中被询问的元素，且这个元素一定比它小。所以从剩下的元素中的一个开始，每次向左找第一个上一轮被询问的元素，即可构造出答案。
多校联考 20251007
B - 中心极限定理
我唐。发现难点在于把马吃了怎么处理，于是考虑状压一下当前位置前几步即可。
C - 散步
将题面稍作转化，变成：给定一个无向联通图与偶数个关键点，要求将关键点两两匹配并选择一条路径，使得任意两条路径（边）不交，构造方案。发现这个问题在树上就可以做。对于一棵子树，它最多有一个点未被匹配。于是对于一个节点，先将它子树中剩下的点与它本身（若有）两两匹配，最后最多剩下一个点，将这个点传递给父亲即可。
多校联考 20251008
B - 围棋
赛时死磕导致根本没看 T3 和 T4。以后再死磕我是狗。
发现难点在于翻转一个白棋，因为翻转后可能会新增一些死的白棋。发现这个东西差不多是割点，于是跑塔尖即可。另外集中情况分讨一下即可。
C - 相互抵消
化简发现原式至于
与 有关，维护即可。
多校杂题选讲 20251010
A - 帐篷
凭啥我只会
。设 表示格子大小为 时的方案数，考虑横着一组占用一行两列，竖着一组占用两行一列，单独一个占用一行一列，直接转移即可。
因为一些原因后面的就不写了。
多校联考 20251011
美好的一天从饭堂开始。
A - 询问
发现 5 次询问之后就是
， 了，矩阵快速幂即可。话说我赛时写了个什么神秘 的分块做法？ B - k-绍兴序列
分讨一下就做完了，倒着 DP 即可。赛时为啥我要正着 DP？ C - 二次根式
什么猎奇打表题。发现
所以只用计算 。对于 ，枚举 以内的质数计算贡献即可。发现需要快速阶乘但是又发现模数固定，于是打表即可。
Codeforces Round 1058 (Div. 1, Div. 2)
Div. 2 Rank 8，紫名祭。
只能说是前一天晚上睡太好了，这天晚上状态好。要是我每次晚上状态都这么好 2200 也不是不可能。
F - Twin Polynomials
赛时做这题的时候有点飘了，要是我认认真真手模一下样例说不定真能场切。
容易想到对于
连边并考虑图的性质。发现对于每个点（除 号点外），要么向 号点连边，要么形成自环，要么属于一个二元环。特别地， 号点不能向 号点连边。容易举反例证明这一点。于是考虑先把图建出来，判断一下是否合法。接下来，只需要考虑剩下的点，并进行一个 DP。设有 个点时有 种分配方案，那么 ，初始状态是 。如果是 号点那么需要特判一下。于是就做完了。 赛时先是认为图是由若干个环组成的（不一定是二元环或自环）于是耽误了好久。后来想到了这一点，可是又没想到可以向
连边，又没有静下心来手模样例，于是 5 题 rk 8 遗憾离场了。G1 & G2 - Inverse Minimum Partition
好神的题。Solution。
值得一提的是，BINYU 自己把这道题改出来了，然后他又给 Zi_Gao 讲了，然后我又参考了他们的代码。直到我写题解的时候，才发现这个做法是假的，然后把我们三个 hack 了。
多校联考 20251014
除了之前没有区分度的那场之外考得最好的一场。
并且获得了 1.25 瓶冰红茶。
只能说还在稳定开挂吧，之前
A - Happy · Lovely · Everyday!
每次选择相邻的两个异或听起来比较困难，所以考虑转化一下，将原序列分成若干个子段，让每个子段变成这个子段的异或和。依然感觉不是特别能发现性质，于是考虑如果已知最终状态，如何判断合法，发现是贪心判断，那么这道题的做法就比较显然了。初始状态为
，每次 可以转移到 ；若存在 使得 是 右侧第一个满足 的位置，那么 还可以转移到 。若 的异或和为零，那么将 累加进答案即可。其实挺唐的，主要还是没改掉赛时喜欢乱猜结论的坏习惯导致耽误了好久。 B - 敬启，致那时的我
虽然按理来讲这题应该评蓝（因为矩阵快速幂都是绿）但是我觉得 B < A。
发现斐波那契数列实在是一点性质都没有了，popcount 相同的数对应的斐波那契值也是一点性质都没有，于是想想关于计算斐波那契数列的第
项还有什么做法，于是显然只能想到矩阵加速。你发现矩阵满足结合律与分配律，于是这道题就做完了。设 表示考虑到第 位，填了 个 ，当前值是否等于上界 时的答案。直接转移即可。 C - Lead to shine more
好奇我赛时是如何切掉这题的。
先观察一下，发现能走的路只有倍增这一条。一个天真的想法是，设
分别表示初始 ，达到 所需要的步数以及总步长。发现无法转移，需要添加 这一维表示初始 。发现还是无法转移，需要添加 这一维表示每次更新是 。然后就可以转移了。对于每次询问，发现高位是容易处理的，然而低位不容易。所以用倍增处理出高位，留下最后 位直接暴力地推即可。 值得一提的是，赛时代码中我不小心让下标出现了
，导致 CWOI 上挂完了。幸运的是，虽然本地测试也用的 Linux，但应该是因为环境不同，本地并没有挂。赛时我其实注意到了那里会出现 ，但是 Windows 上没挂，我也没有意识到它会被作为下标，就忽略了这个问题。总之还是不够严谨导致的，而且在 NOI Linux 上测一下样例也是很有必要的。（这段话好人机。）
多校联考 20251015
B - 捐赠
两只
跑得快，甚至 草过了 。 正解显然是一只
的。你会发现 A 选的个数与 B 没选的个数之和恰好是 B 的个数，下文记作 （废话），那么转化一下，对 B 物品的权值取相反数，那么答案就是选权值前 大的物品，再加上 B 物品的权值和即可。 C - 染色
不错的树上启发式合并题，可是我并不会。
然后写日祭的时候发现一车人的启发式合并是假的，包括我。当然如果精细实现也能过，但是我不想改了。
多校联考 20251021
BINYU Zi_Gao Rong7 模拟赛，内部提前到了 20251017 考。
A 是唐，C 的
多校杂题选讲 20251017
不想写。
多校联考 20251018
紫紫黑黑 NOIP 模拟赛。
不想写。
并非多校联考 20251021
运动会，没打。
多校联考 20251022
A - 石头人
因为没判
导致挂分。 B - 炒鱿鱼
要求在一种特殊图上对图进行三分图染色。
做法是，直接 dfs 染色，但是优先遍历编号大的点。至于为什么是对的我也不知道
赛时因为有点细节问题导致挂分。话说这个构造甚至我最后 20min 想出来的。
C - 适格者
纯唐。
多校联考 20251025
A - 剖分
唐氏树形 DP / 贪心。
B - 海啸
不带修是 ARC201B。
带修也是好做的，维护一下当前每一“层”中的元素即可。
并非多校联考 20251027
可是牢祝依然算了这场的成绩。
A - 大骑士领一瞥
分讨题。
B - 流放阿卡胡拉
注意到路径一定是
，其中 或 是质数。然后你发现，我们只需要关注以 为右下角的一个矩形中的 ，所以在矩形中跑暴力 DP 即可，矩形长宽取到 就行了。虽然不知道哪里来的正确性，但是靠感觉它就是对的。
多校联考 20251028
A - 排序
唐。
B - 重排
唐。
多校联考 20251029
A - 初恋
唐。
B - 奥瑟罗
没我唐。随便乱维护一下即可。
CSP-S 2020 并非 VP
A - 儒略日
屎。
B - 动物园
屎。
C - 函数调用
好。没一眼秒的原因是没有注意到加乘可以转化成加和全局标记乘，也没想到正难则反。我咋这么唐。
后来一直写挂的原因是，拓扑时理所应当地只加了
号点，也是糖丸了。包括记忆化搜索的时候，应当令初值为 ，因为乘数可能为 。
CSP-S 2021 并非 VP
CSP-S 2022 并非 VP
A - 假期计划
好。你发现如果我们确定了
和 ，那么就可以贪心地选择 和 ，其中 需要满足从 与 均可达， 同理。于是我们可以 预处理出可达关系，与对于一个确定点，有哪些点可从 与它可达。接下来，枚举 和 ，贪心地选择最优的 和 。发现 和 可能会和其它点重复，于是考虑放缩一下。容易发现我们只关注前 大的 和 ，于是预处理的时候求出前三大的即可。 B - 策略游戏
唐。
CSP-S 2023 并非 VP
CSP-S 2024 并非 VP
2025.11
CSP-S 2025
A - 社团招新
原来这就是反悔贪心啊。
B - 道路修复
我是唐。发现一个图在加入若干条边后，原来不在 MST 的边现在还是不在 MST。随便搞搞即可。
C - 谐音替换
赛时想到一个树套树做法但是没写出来。
感觉转成二维数点的做法不是很优，于是严肃决定恶补一下串串。
首先把
写成 的形式，然后把两个串合在一起变成 ，然后原题就变成求有多少个模式串是文本串的子串了。时间复杂度 。 D - 员工招聘
不想写了。
多校联考 20251104
A - 图
甚至是搜索题。搜一下每个点到
的最短路距离，边搜边算贡献即可。
多校联考 20251105
这场是啥啊。
多校联考 20251108
下分场。
A - 国王的试炼
拆拆贡献，发现只用关注当前数与比当前数小的数，所以随便 DP 一下即可。
多校联考 20251111
上分场。
A - 青蛙
唐。
B - 表达式
我唐。注意到
0+x+x-0正着是倒着是 ，于是直接构造即可。 C - 淘汰赛
首先容易写出
。 然后你会发现我们只用关注以
为右下角、长宽为 的矩形中的位置，于是就做完了，时间复杂度 ，用数位 DP 实现可以做到 。
多校联考 20251112
原神 Round. 1
A - 异或
唐。
B - 伊甸
奶龙大战暴暴龙，但是输在了原题没有的 corner case。
C - 炼丹炉（[CF1979F] Li Hua and Path）
板，但是不会。首先人工容斥一下，变成求同时满足两个条件的点对个数。考虑从小到大与从大到小各加一遍点，令新加的点成为当前连通块的根，那么限制就转化为了祖孙关系。用类似阿狸的打字机的做法即可。
多校联考 20251113
原神 Round. 2
A - 传统题
大样例题。
B - 非传统题
你没蛋还在发力。
C - 历遍的树
考虑找出哪些点可以用来掉头，发现这样的点需要有三条以它为起点的路径，使得每条路径的长度都大于等于蛇的长度。称满足条件的点为关键点。可以证明，只要蛇可以到达一个关键点，它就可以到达任意一个关键点。所以任取一个关键点为根，模拟蛇移动的过程，判断蛇能不能移动到根即可。
多校联考 20251118
原神 Round. 3
A - box
唐氏 DP 题。
B - graph
侦探 JYY 还在发力。
C - chess
赛时通过手模大样例猜出了斜列黑白交替的结论，然而因为时间原因，没发现第一行相邻的一对格子颜色相同（实则是因为赛时做完前两题开始发呆耽误了很久）。Solution。
多校联考 20251119
A - 下一个天亮
乱构造一下即可。
B - 希巴拉克的道路
发现需要维护一堆线段的斜率，上李超树即可（但是赛时写了个神秘做法）。
C - 超纲
似乎挺板，但是不会。
多校联考 20251121
A - 『木叶创立』
唐。
B - 『须佐能乎』
容易写出一个暴力的矩阵快速幂优化 DP。可以发现，若令直径的中点作为根，那么对于一棵子树，其内部点的 DP 转移是完全相同的。进一步发现，若称两棵子树本质相同，当且仅当其内部的直径端点数量相同，那么对于两棵本质相同的子树，其内部点的 DP 转移都是相同的。所以对于本质不同的子树进行 DP 即可，时间复杂度
。
多校联考 20251122
A - 破乱的诗歌
随便乱做做即可。
B - 增殖的病菌
塔尖缩一下点就昨晚了，细节有点多。
C - 可爱的猫猫
难绷搜索。
多校联考 20251124
A - 创生矩阵
难绷构造题。考虑构造两个长度为
的序列 ，其中 满足 ， 同理。那么对于原矩阵 ，只需要构造 即可。对于 ，随便构造一下即可。 B - 都因为你
签到题。
多校联考 20251125
A 原，其他不会。
多校联考 20251127
A - 幸运数字
分讨题，被 corner case 创飞了。
B - 树的遍历
屎。随便推一推发现需要维护一堆东西的和，然后维护即可，
还需要写个扫描线。 D - 季风
签，随便推推式子即可。
NOIP 2025
A - 糖果店
按照
排序，取最小的若干个 ，再取若干个最小的 即可。 B - 清仓甩卖
父母是一块还是两块。
记
表示第 个物品打折后为 费。发现统计不合法的方案数应该更容易。发现一个方案不合法，当且仅当考虑物品的顺序为 ，且考虑 时恰好只剩 费。特别地，若考虑 后考虑了 ，应当满足 。 于是考虑对
排序，并枚举 ，使得 。通过双指针求出 的最大值。对于每个物品，若下标属于 ，那么取一费或二费均可；若属于 ，那么只能取二费；若属于 ，那么取一费或二费均可。 另一个限制是在考虑
之前恰好花掉了 费，除去 花掉的 费，还剩下 费。对于下标属于 的物品，若取一费，那么它会在考虑 之前被取，贡献为 ；若取二费，那么它会在考虑 之后被取，贡献为 。对于下标属于 的物品，无论取一费还是二费，它都会在考虑 之前被取，所以贡献为 或 。现在要求从这些物品中选 费的方案数，发现两段本质相同，我们可以认为第一段是 ，第二段是 ，于是直接组合意义即可。当然也可以枚举一段求另一段，再用一个神秘恒等式化简。
- Título: 2025 年日祭
- Autor: Getaway_Car
- Creado el : 2025-12-31 23:59:59
- Actualizado el : 2025-12-17 12:04:22
- Enlace: https://getawaycar1024.github.io/article/2025-年日祭/
- Licencia: Este trabajo está licenciado bajo CC BY-NC-SA 4.0.