本文将同步发表于洛谷（暂无法访问）、CSDN 与 Github 个人博客（暂未发布）
本蒟自2025.2.8开始半停课。
以下是题目格式：
-
[题目OJ 题号] [来源（选填）] 名称
……
-
题号 - 名称
题目：……
题解：……
-
题号 - 名称 （[题目OJ 题号] [来源（选填）] 名称）
……
任务计划（站外题与专题）
数了一下，通过人数比较高的题，也就是我准备补的题，刚好差不多100道题。于是……
摆烂百题计划开始！（糖丸了）
（2025.2.8）
-
Network
-
Network of Schools
-
DP优化——矩阵
-
数论——容斥、二项式反演
-
DP优化——斜率优化
-
数据结构——左偏树
-
数据结构——吉司机线段树
-
数据结构——李超线段树
2025.1.4 新的一年
今日歌曲：New Year’s Day
去年停课的时候是有记日祭的，但是有一些是手写的，一直都还没有整理好。今天看到一个简单的trick，想记下来。于是，就又开始写日祭了。
-
[洛谷 P2831] [NOIP2016 提高组] 愤怒的小鸟
一道远古状压题了。（一是指题目本身远古，二是指这道题是好久之前就该做的题。）看到第一篇题解的trick，想起去年暑假集训的时候也有这样一个trick，但是忘了是哪道题。这个trick挺简单的，但也挺好用：状压时，如果目标状态是全0或全1，并且转移顺序不影响结果，那么可以直接从最低位的1或0转移，因为最低位最终一定会被转移，而顺序又不影响结果，所以这样做可以优化掉 O ( n ) O(n) O(n) 的复杂度。其他的按正常状压即可。
-
[Atcoder ARC100E] Or Plus Max
今天学了sosdp，挺神奇的一种dp。这个题算是板子题吧。只用维护子集的最大值与次大值即可。
今天下午给初二机房的办了一场比赛，整体比较顺利。（所以没做什么题。）比赛链接：CWOI-N ER & NYR 1。
今天感觉要掉橙了，但是Rated的比赛还要等一周。想着把之前那篇被打回的题解改了交了，但是晚上写给初二机房的的题解了，没空。看明天改吧。
2025.1.10 新的开始
今日歌曲：Castles Crumbling
今天考完期末，回来一看，天塌了，掉橙了。明天打一场比赛。
现在终于确定15班后续的各种事项了。又是一个新的开始。
另外，我就莫名奇妙地进省选了（尽管是体验名额）。还有一个有趣的事实：
我没有提高组一等奖，然而我进了NOIP（体验名额）；我没有NOIP一等奖，但我进了省选（体验名额）。
期待人生中的第一场SCOI（希望不要爆零）。
2025.1.12 言而无信
今日歌曲：Back To December （好吧其实是存货）
我果然是一个言而无信的人。踩一脚前天的日祭，昨天还是没打比赛。
今天%你赛，除了暴力的B和C，其它全挂了分。至于A，调试的时候把模数写掉了。被暴扣70分呜呜呜。
最终荣获 30 + 10 + 30 + 0 = 70 30 + 10 + 30 + 0 = 70 30+10+30+0=70 的高分。
-
A - 括号序列
题目：给一个由左右括号构成的字符串 s s s，对于每一个位置 i i i，输出有多少个子串，满足这个子串是一个合法的括号序列，并且 i i i 这个位置在子串中。
题解：简单维护前缀与后缀的括号数量即可。（忘写该死的模数暴扣70pts。）
-
C - 矩阵删除
题目：给一个 n × m n \times m n×m 的 01 矩阵，我们想在每一行删除一个元素，得到一个 n × ( m − 1 ) n \times (m - 1) n×(m−1) 的矩阵。其中删除的元素的位置 ( i , a i ) ( 1 ≤ i ≤ n ) (i, a_i)(1 \le i \le n) (i,ai)(1≤i≤n)，满足 ∣ a i − a i + 1 ∣ ≤ k ( 1 ≤ i < n ) \vert a_{i} - a_{i + 1} \vert \le k(1 \le i \lt n) ∣ai−ai+1∣≤k(1≤i<n)。请问最后能得到多少种不同的矩阵。两个矩阵如果删除的元素位置不同，但最后得到的结果相同，我们认为是相同的。由于答案很大，输出答案对 1 0 9 + 7 10^9+7 109+7 取模的值。
题解：比较板的DP，但是赛时思路没那么清晰，也没去推式子。分别维护对于每一个位置的方案数以及与旁边位置重合的方案数，推出式子后发现全都是求和，于是用前缀和维护即可。
2025.1.13 乐极生悲
今日歌曲：Wonderland
今天期末考试考完了，整体还行，语文更是考到了惊人的 127.5 127.5 127.5，要知道我之前最高的一次也就 122 122 122 左右，而且还经常上不了 120 120 120，这次简直是超常发挥。听到成绩的时候直接喜极而泣了。
下午体育课，刚好初一体锻放歌，放得全是霉霉的歌，我还去点了几首。开心。
然而下课要集合的时候，我小跑了一下，而这下就恰好被足球爆头，眼镜镜架直接断掉，箍牙的铁丝直接断掉，嘴皮直接被铁钉磨得烂掉，鼻子被眼镜压了一个印子，还在流鼻血。
真是乐极生悲。
2025.1.17 傻子游戏
今日歌曲：Foolish One
今天开始上课六天。
昨天听说 jmr 拿了清华一等约。祝贺他。
这周二（1.14）已经回到15班了。
昨天晚上玩梗发癫，还玩了离谱的傻子游戏。达成成就：在5.5h里睡够8h。
上午%你赛，T1忘了判零挂了10pts，T3是之前做过的一道原题，于是赛时死磕，最后没调出来。赛时的思路基本上是对的，但是没想到容斥；又因为我钦定的一个条件有问题，导致正确性略有问题，最后没调出来。
喜提 90 90 90 分。
-
A - 串
题目：在虱子王国，一句话由 n n n 个词组成，其中恰好有 k k k 个词是怪的，其它的词都不是怪的。众所周知，负负得正，我们定义一句话的一个区间是怪的，当且仅当其中含有奇数个怪词。请构造一句符合条件的话，使得其中怪的区间数量最多。
题解：发现答案为奇数块乘上偶数块。构造即可。
-
B - 艺术家
题目：给定一个长度为 n 的颜色序列 c c c。再给出 m m m 个区间，第 i i i 个区间为 [ l i , r i ] [li, ri] [li,ri]，保证任何两个区间都是不相交或包含的关系。在接下来的 q q q 个单位时间内，第 i i i 个时间会给定 x , y x, y x,y，表示将 c x c_x cx 变为 y y y。请对于每一个区间求出，最早的其中所有颜色都互不相同的时间。
题解：
保证任何两个区间都是不相交或包含的关系。
所以可以把区间建成一棵树。当一个子区间合法，其父区间才有可能合法。在原数轴上维护 l s t i lst_i lsti 表示 i i i 之前第一个颜色与 i i i 相同的点，则一个区间内部颜色互不相同等价于 max { l s t i , l ≤ i ≤ r } \max\{lst_i, l \le i \le r\} max{lsti,l≤i≤r}。使用线段树维护。对于 l s t lst lst 的更新，用 set 维护。即可。（难写死了，还没写完。）
-
C - 黑白树 （[Atcoder ARC108F] Paint Tree）
题解：画一个直径上吊着节点的图，讨论一个节点在什么时候可以带来贡献。容斥计算即可。
晚上打了入门赛，可以加咕值了。
晚自习最后10分钟，记一些话。
我的信竞，在进步么？看起来好像是的。要是拿现在的我和一年前的我对比，那已足以 k k 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 a(a + 2) + 1 = a^2 a(a+2)+1=a2 个，可以通过。稍微分讨一下即可。
赛后看了一下题解，发现自己好唐：
1 , 2 , 3 , … , n − 2 , 1 , 2 1,\ 2,\ 3,\ \dots,\ n-2, \ 1,\ 2 1, 2, 3, …, n−2, 1, 2
-
[CodeForces 2056D] Unique Median
又是一道正难则反，计算坏的序列的个数。这道题的trick挺巧妙的，但没接触过，确实想不出来。发现长度为奇数的序列一定不是坏的，所以只考虑偶数长度序列。对于一个序列的中位数 x x x，将序列中 ≤ x \le x ≤x 的数化为 − 1 -1 −1，其它的化为 1 1 1。若最终区间和为 0 0 0，那么这个序列就是坏的。另外要注意去重。维护前缀和即可。
-
[CodeForces 2056E] Nested Segments
组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量，那么需要构造成二叉树。（这里具体不想证明。）对于某一个节点，设其儿子数量为 c n t u cnt_u cntu，则计算 ∏ C c n t u − 1 \prod C_{cnt_u - 1} ∏Ccntu−1（卡特兰数）即可。
下午先把E题改了，学习了一下吉司机线段树。这东西挺好理解的，写起来也很爽，但就是又臭又长又难调。
-
[洛谷 P10639] [BZOJ4695] 最佳女选手
这道题本来是第二道模板题的，但因为第一题相当于第二题的子问题，所以直接冲着这道题来了。写板子即可。（啊啊啊终于还是讨厌上吉司机线段树了啊。）
今天整理了一些去年的日祭。还没把手写的整理上去。
2024.1.19 简直糖丸
今日歌曲：All You Have To Do Was Stay
今天上午%你赛，T1爆零了，简直糖丸。一共得了 60 60 60 分的高分。
下午给初二讲题，讲得……简直糖丸。
烦球，今天最后几乎啥都没干。
啊不是为什么T1爆炸啊。
2024.1.20 简直乐丸
今日歌曲：Daylight
昨晚又是在5.5h内睡满8h的一晚。
今天上午VP CodeForces Round 998 (Div. 3)。才做四道，糖丸了。
-
[CodeForces 2060E] Graph Composition
赛时就很唐。并查集查联通并算连通块即可。
-
[CodeForces 2060F] Multiplicative Arrays
一道很好的DP+组合数学题。赛时推式子感觉推出来了，结果赛后再一看伪了。很容易发现， ∑ i = 1 l e n [ a i ≠ 1 ] ≤ 16 \sum_{i=1}^{len}[a_i \neq 1] \le 16 ∑i=1len[ai=1]≤16，所以DP计算非 1 1 1 元素的情况，再用组合数学即可。
-
[CodeForces 2060G] Bugged Sort
这个题就很 “tricky”。（bushi，自己随便造的词。）这篇题解感觉讲得比官方题解还要清晰。可以观察到，当 n ≥ 3 n \ge 3 n≥3，我们可以任意（正常）交换两组的位置。因此，我们可以将两组数进行翻转。换而言之，进行翻转的次数必须是偶数次。这里记翻转次数为 c n t cnt cnt。我们把较小的数放在 a a a，较大的放在 b b b。若按 a a a 排序后 b b b 有序，那么该组数据有解，当且仅当满足这三个条件之一：
- 2 ∣ c n t 2 \mid cnt 2∣cnt
- ∃ b i − 1 < a i , 2 ∣ n , 2 ∣ i \exists b_{i - 1} \lt a_i,\ 2 \mid n,\ 2 \mid i ∃bi−1<ai, 2∣n, 2∣i，此时可以选择交换奇数组数翻转以改变 c n t cnt cnt 的奇偶性，处于“无敌”状态。
- 2 ∤ n 2 \nmid n 2∤n，此时可以翻转全部以改变 c n t cnt 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 a a 合并，那就把 b b b 中不合法的进行拆分。用 map 维护即可。其实这道题也好证
，只是想凑一个小标题罢了。 -
[CodeForces 2061E] Kevin and And
这题有点……难评。为什么字典树过不了啊……
因为 m m m 很小，所以对 b b b 进行状压，再将 a a a 的变化量压进堆里选最大的 k k k 个即可。（好吧其实不是特别理解。）
F 听不懂。
附一张梗图。
（这里声明一下，不是 jmr 讲得不好，而是实在听不懂。）
2025.1.22 比特塞特
今日歌曲：Maroon
年前最后一天了。
上午%你赛 100 + 10 + 60 + 0 = 170 , r a n k 4 100+10+60+0=170,\ rank\ 4 100+10+60+0=170, rank 4。T3没用 bitset 优化暴扣了 40 40 40 分。可恶。
-
A - bins （[洛谷 P6807] [BalticOI 2010 Day2] Matching Bins）
差分即可。
-
C - candies（[洛谷 P6808] [BalticOI 2010 Day2] Candies）
题解。
2025.2.8 水讨论区
今日歌曲：Bigger Than The Whole Sky
今天洛谷讨论区关闭了。（以后不能水讨论区了。）
这个寒假，什么也没干。一看进度，已经和初二的差不多。但是他们第一遍拉得挺快，估计效果不大。
我如果现在回去，在那边又吃不饱。于是，就只有多肝一肝，把之前的进度补上来。
晚上打ABC392。
-
[Atcoder ABC392E] Cables and Servers
略考细节的题。先找连通块，之后再找每个连通块中的返祖边（即无用的边），再把连通块连通即可。
（可是这题我赛时AC，后来突然想到一个hack。还没改，烦死了。）
-
[Atcoder ABC392F] Insert
先写一个 O ( n 2 ) O(n ^ 2) O(n2) 的做法，发现可以分块。所以分块即可。（赛时想到分块但没写，烦死了。）
2025.2.9 终于战胜
今日歌曲：Holyground
综合题1。
-
[Gym 103466I] Space Station
神奇搜索题，暴搜+剪枝+略微组合数学即可。
神奇卡常题目，拼尽全力，2700ms+，终于冲进3s。
-
[Gym 101982D] Count The Bits
很普通的一道DP题，可是赛时都在想组合数学。
d p i , j dp_{i, j} dpi,j 表示到第 i i i 位模 k k k 的值为 j j j 的数中 1 1 1 的数量， c n t i , j cnt_{i, j} cnti,j 表示到第 i i i 位模 k k k 的值为 j j j 的数的数量，直接转移即可。
-
[Gym 102428F] Fabricating Sculptures
神奇DP题。最开始看题解都没看懂，一是自己确实不理解是怎么算的，二是题解写得比较简略，看了好久才看懂。
设 d p i , j dp_{i, j} dpi,j 表示从上往下一层层放，当前一共放了 i i i 个，最下面一层放了 j j j 个的方案数。有方程 d p i , j = ∑ k = 1 j d p i − j , k ∗ ( j + 1 − k ) dp_{i, j} = \sum_{k = 1}^j dp_{i - j, k} * (j + 1 - k) dpi,j=∑k=1jdpi−j,k∗(j+1−k)（希望没写错）。将这个式子拆开再维护前缀和即可。（开了long long见祖宗。）
-
[Gym 104172F] Sum of Numbers
很有趣的一道题。很容易发现，两个相邻字符串长度之差（的绝对值）为 0 0 0 或 1 1 1。暴搜即可。
赛时的想法是，将原字符串平均分，再给 0 0 0 或 1 1 1 的偏移。可是偏移少了一些，虽然没 TLE 但一直 WA，拼尽全力无法战胜。
赛后再改一改，拼尽全力终于战胜。
今天本来说再补补昨天的 F，改改昨天的 E，结果今天的第三题看半天看不懂，昨天的 E 和 F 都没做。
最终今天做了四道题。
感觉心态有点崩。（尤其是看第三题的时候。）
……
2025.2.10 放弃即可
今日歌曲：Peace
综合题2。
今天还做出了一道题。
-
[Gym 100861E] Extreme Programming
看了题解真的好简单。首先我们先确定这些问题的顺序。推推式子，排序即可。现在，我们不用考虑顺序，只用直接背包，找出最大的 E V EV EV 与最小的 E T ET ET 即可。
可是这道题不知道哪里写挂了，WA on test 15。
放弃即可。 -
[Gym 100217I] Sharing the Sweets
分拆数板子题。（可是我不会。）写板子即可。
分拆数 OI Wiki。
-
[Gym 100202A] Little Brackets
这题着实简单。设 d p i , j , 0 / 1 dp_{i, j, 0/1} dpi,j,0/1 表示放了 i i i 个括号，当前高度为 j j j，是否到过最高点（深度为 k k k）的方案数。直接转移即可。
可是赛时想多了，一直在想组合数学。或许先设方程再推会好一些。
赛时还因为多测不清空挂了四发。
今天还举办了 CWOI-N RER 1 > 2，感觉对于他们还是太难了。
（今天字符数破 1 e 4 1e4 1e4 了。）
2025.2.11 放弃即可
今日歌曲：Pink Pony Club
模拟赛 40 + 40 + 100 = 180 , r a n k 2 40 + 40 + 100 = 180,\ rank\ 2 40+40+100=180, rank 2。
-
B - 刀言刀语 （[洛谷 P6864] [RC-03] 记忆）
今天给的题解以及同学讲解的都是非矩阵做法，可是听得迷迷糊糊。一下午尝试乱搞做法，结果没搞出来，最后，一道题都没改出来，
放弃即可。晚上终于学习了矩阵，基本学懂了，这才发现矩阵有多好用。之后又看了这道题的矩阵+线段树做法，终于基本懂了。将这些数据打包成矩阵： [ a n s c n t 1 ] \begin{bmatrix} ans & cnt & 1 \end{bmatrix} [anscnt1]。对于操作一，等同于 [ a n s c n t 1 ] × [ 1 0 0 1 1 0 1 1 1 ] \begin{bmatrix} ans & cnt & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} [anscnt1]× 111011001 。对于操作二，等同于 [ a n s c n t 1 ] × [ 1 0 0 0 0 0 1 1 1 ] \begin{bmatrix} ans & cnt & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix} [anscnt1]× 101001001 。对于操作三，若是恢复某个操作，则与操作一二相同；若是删除某个操作，则将这个操作设为单位矩阵（ [ 1 0 0 0 1 0 0 0 1 ] \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} 100010001 ），不会对答案产生影响。用线段树维护每个操作对应的矩阵，区间求和（求积）即可。
这道题记得比较详细，毕竟是第一次接触矩阵。
-
C - 刀妙构造
题目：给定一个长度为 n n n 的排列 a a a，通过尽可能少的操作，使得 ∀ a i = i \forall a_i = i ∀ai=i。判断是否有解。若有解，输出具体的操作。操作的定义：选择 x , y x, y x,y 满足 1 ≤ x , y ≤ n , ∣ x − y ∣ = 1 , a x ≠ x , a y ≠ y 1 \le x, y \le n, \left | x - y \right | = 1, a_x \ne x, a_y \ne y 1≤x,y≤n,∣x−y∣=1,ax=x,ay=y，交换 a x a_x ax 与 a y a_y ay。
题解：原本就满足 a i = i a_i = i ai=i 的位置将原数组分割成若干个块。对于每个块，若是目标的一种排列则有解。设当前块为 [ l , r ] [l, r] [l,r]，则依次把数 l ∼ r l \sim r l∼r 移到位置 l ∼ r l \sim r l∼r。要注意的是，在移动的过程中，可能会使得其它的 a i = i a_i = i ai=i 成立。所以我们将这些即将成立的位置先进行偏移，再将当前的数移到目标位置即可。
扩展：尝试在 O ( n log n ) O(n \log n) O(nlogn) 的时间复杂度内求出有解的排列个数，对 998244353 998244353 998244353 取模。
这几天强度还是比较高，因为跟进度跟得有点吃力了。今天晚上眼睛疼，难受。
