NOI2025游记 - 洛谷保存站

## 3.31

学了一个月 whk 后感觉脑子变傻了，AT 和 CF 都打得奇烂无比。

今天到了 MX 线下，XZQ 大哥哥走了后，我现在一个熟人都没有了。PengAo 在 XYD，WTR2007 和 Lopzith 在 TYZ。

刚来第一天刚好就有模拟赛，不过听对面老哥说不用打。看了看题，怎么感觉 100+100+eps 并不困难。赛后看榜发现 JX 红太阳 hz 老师 100+100+40，太强大。T3 我随手画了画图就感觉很难做。

部分人打模拟赛时我在干什么，我在学习 Z 函数和 AC 自动机。是的有人都快要国赛了还不会这俩东西。怎么感觉 ACAM 其实并不比 SAM 简单。

过完板子打算拿 P2292 和 CF590E 当例题练手，正好我没写祭祀那题，写完 CF590E 就不用单独写一遍祭祀了。（不过有点想直接贺一发题解交上去，不然我洛谷月过题量太惨淡了。）做 P2292 时并没有想到压位，感觉要废掉了。如此状态，何以国赛？

此外换了新笔记本，还把 vscode 的 latex 配好了，学 whk 在教室里睡觉睡多了，第一次发现一个上午原来能干这么多事，还是学 OI 充实。

写了下上午模拟赛的 A 题，没想象中那么顺利，这东西竟然卡常。写写调调鏖战 1h30min。看了榜发现大家好像差不多都是这个时间。还算能接受吧。

B 题没想到也写半天。。。、

C 题完全不会啊，看题解感觉很不 OI 啊。猛然发现它的所有 subtask 分值加起来为 90，还有 10 分去哪了？

每日一语：越是锁门，越有猫腻。——徐度建。

## 4.1

贺了祭祀，写完了 CF590E。一开始 Tle on test6 以为是被卡常了，卡常途中发现自己路径压缩少压缩一段，复杂度甲烷了，改掉后就过了。

补昨天模拟赛 T3，一共 107 个点死在第 103 个上，很崩溃。本来已经找老师要数据了，结果数据还没发过来先肉眼调出来了。暴力求组合数的时候 $1e9\times 3e10$ 直接炸了。

试图学习 border 理论，失败。

学习串串太痛苦了，不学了。

突然发现我还有马拉车可以学，这个简单。没错，我连这个也不会。

学完了，怎么和 Z 函数几乎一模一样。。。

又学了 CRT，想不到吧，这个我也不会。模板题一开始没开 __int128，过不去 hack 数据。

试图学习杜教筛，不过转念一想我学这个有什么用，遂放弃。

每日一语：哦~哦！哦——错了！错了吼！——徐度建。

## 4.2
早上以为有模拟赛，结果怎么没有。。。

把 excrt 板子写了，交上去 0pts。本来以为是哪里少开了 __int128，最后把数据下载下来发现我合并两个方程的部分打错了好几个变量名，我请问这是怎么通过样例的？？？

把 Z 函数板子写了，交上去 16pts。原来是我把两个字符串拼在一起空间却没开 2 倍。

把 SA 板子写了，交上去 100pts，学的是 OI-wiki 的写法，但是我发现它给的 Code 是存在数组溢出的情况的，疑似该开 2 倍的数组没开 2 倍，不该开 2 倍的数组开了 2 倍（）。

做了一个决定，最近做的串串题全都先拿 SA 写一遍再拿 SAM 写一遍。

PAM 目前无复建打算，实在想象不出现在的 NOI 里怎么才能出出来 PAM 题。

网易云播放列表里不知怎得出现了时代少年团翻唱的《打开》，受到了比较强烈的听觉冲击，听几遍原唱都缓不过来的那种。

每日一语：你们不要取笑我吼。——徐度建。

## 4.3

今天怎么又有一场模拟赛。

开了一场之前的模拟赛，怎么发现 T1 复杂度爆炸了。。。然而这题 hz 老师 13min 秒了。

差不多打完了，汇报一下：

T1 是个没什么思维含量的恶心 DP。对排列的普通 DP 成功写出了连续段 DP 的码量。

T2 是个我不太会的 DS。

T3 是个我只能输出 -1 获得 3 分的不可做构造。

经过反复催促，我终于进了 vjudge Group。

经过反复催促，我终于要到了题解。

经过反复催促，模拟赛频率终于提高了。

来集训四天，还没见到教练一面。

今晚有 EDU Round，决定打一下，看看小号能不能上 M。

愚人节比赛，启动！

忘记打 EDU了！！！

和 Cxjj、lrz 在群里激情讨论一道我乱胡的随机游走问题，没注意时间。Cxjj说这是板子题，建议我多做做随机游走的题。（但我目前觉得他假了，不过他手机没电了，讨论尚未结束）

后面我会做了，一开始以为该做法涉及动态高消，最终发现其实整个过程中矩阵并没有发生改变，只是旁边挂着的列向量变了，所以其实可以简单地解决。

感觉这题比较巧妙啊，打算出出来以纪念之。

每日一语：我的往届学生高一的时候可能不怎么理解我，但是到高二高三的时候都能发现我的良苦用心。——许静。

## 4.4
今天又没有模拟赛！！！

把昨晚[那题](https://www.luogu.com.cn/problem/U550679)出出来了，没造数据。

今天依旧没有模拟赛~

感觉想依靠网上现存的资料学习动态高消比较困难，想写一篇讲解动态高消的博客，不过犯懒了又不想写了。

开谷谷迷，感觉 1、3、5 和 2、4 的难度差异太大了。

今天好摆啊好摆啊好摆啊好摆啊好摆啊好摆啊好摆啊。

每日一语：哎，我也是有父母的吼！——徐度建（2025/4/1 所说）。

## 4.5
完成了前晚的[那题](https://www.luogu.com.cn/problem/U550679)的[题解](https://www.luogu.com.cn/article/txtw1tlj)。

目前我写的字符串专栏内容还比较少，暂不公开，等题目数量达到 10+ 再放出来吧。

想了想还是直接放出来吧，可以先把框架写好，题解内容后面再补。

今晚同时有 AT 和 CF，可以水游记字数了！

大败而归。

AT 成功做到了通过的每一题都有罚时，实在过于逆天。

CF 不会 E 题，然后 C 题一个 `n` 打成了 `n/2` 调半天，不好评价。

每日一语：呃，别急！别急！别急！——徐度建。

## 4.6
打了场失败的 ARC。

只能说 B 题是我非常不擅长的一类题目。

每日一语：沃~沃！我没急！我没急！我没急！——徐度建。

## 4.7

模拟赛出现了个 [P6076 [JSOI2015] 染色问题](https://www.luogu.com.cn/problem/P6076) 加强版，结果全程没往二项式反演上想，感觉非常的失败。

学习了[背包科技](https://www.cnblogs.com/LiuRunky/p/Knapsack_Problems_with_Bounded_Weights.html)。

学习了[有源汇上下界最小费用可行流](https://www.cnblogs.com/leason-lyx/p/11144527.html)。

模拟赛 T3 是个[逆天 slope tirck 题](https://codeforces.com/contest/1229/problem/F)，因为没怎么写过相关题目，所以打算补一下。

学习了模拟费用流。

被模拟赛 T3 硬控了 5h /tuu。

我的[华语歌单](https://music.163.com/#/playlist?id=13324666925)基本修缮完了，网易云太多歌没版权了/fn。

继续做串串，有好多东西没做怎么办怎么办怎么办。

每日一语：宝贝~想你了吼！——徐度建。

## 4.8
感谢洛谷的一篇帖子，他求助 wqs 论文中的例题的凸性证明，让我精进了对其的理解(本来想给他发证明的结果发现自己假了，感谢他发这个贴子，要不然我都不知道我假了)。

今天还是没模拟赛，做做之前剩的题目吧。

对字符串专栏加了很多内容，本地写好了，后面再传到洛谷上吧。

做 CF1037H 的时候看到了一位 AFO 去学 MO 的前同学在讨论区的黑历史（那时候他似乎还在小升初）。

再次吐槽学 OI 以来读 xht 的题解目前还没有半点收获。

每日一语：做不出来，要打屁股吼。——徐度建。

## 4.9
今天终于有模拟赛了，一周多没打过正式模拟赛了。

但打得稀烂。

T1 是个 线性基三进制诈骗题，调了半天。

T2 ds，不会啊。

T3 看着就是分讨 + 推性质，应该相当苦难。

tby 承诺昨天要讲课来着的，但是没讲。

在 U 群问了个串串题，结果大佬口中的简单分块我不会。

每日一语：我发起火来，你们是，承受不了的吼。——徐度建。

## 4.10
题单惊现析合树，MX 真是太有实力了。

学习了矩阵树定理。

昨天的分块引来了 myee、cxy、lxl 等大佬的回复，最后发现并不是那么简单。

myee 老师看错题了，并决定把看错的版本放模拟赛里。

每日一语：师大的女生最美，不接受反驳。——徐度建。

## 4.11
在 lxl 的帮助下彻底解决了[分块题](https://www.luogu.com.cn/problem/U552570)。

准备拿来当祖传防 AK 题了。

今天北京大风，提前离校了。

怎么游记开始水起来了，明天开始想办法充实下。

每日一语：一定会考的吼。——徐度建。

## 4.12
然而事实上并没怎么刮风。

破防了，打 ABC，G 题本地精度不够但交上去过了。。。

每日一语：本节课分为两个部分，前半部分是重点，后半部分是难点吼。——徐度建。

## 4.13
今天开始刮风了。

看了眼 UR 的题，果然很难，不看了。

每日一语：我还是有点水平的吼。——徐度建。

## 4.14
口胡秒了 [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770)，很开心。

换了头像，起因是 ljm 觉得这个表情包长得和我本人很像。然后 JX 群里的人好像都比较认可 ~~（包括我）~~。徽章就拿这个订了。

每日一语：我知道大家其实还是很喜欢我的吼。——徐度建。

## 4.15
浑浑噩噩噩噩浑浑，处于非常没脑子的一个状态。

每日一语：回答不出来要被关学吼。——徐度建。

## 4.16
今天难得又有模拟赛。

可以看出脑子还是一坨，T1 简单的题目来来回回拍来拍去调了 3h+，最后被卡常了。重构代码后调不出来。。。（不过重构后的版本分比原来高，梦熊数据是这样的）

每日一语：化竞的同学记得带 evans 书吼。——徐度建。

## 4.17
听到有人大附中的学生喊了两声刘教(?)

突然在想出题人会不会发病在今年再考一次 lgv 引理。

学习了广义串并联图相关。

学习了烧边相关。

学习了区间历史和相关，然后才发现自己曾经会过。。。

每日一语：就是资溪面包那个路口吼。——徐度建。

## 4.18
以下内容被标记为 **[重口]**，请谨慎观看。

---

>>>>>>>>>>>>>>>>>>>>> 上厕所时听到了人大附中小朋友的猎奇发言：“哎，我蹲错地儿了，你低头看看，我拉哪儿了。我拉错地儿了，一条巨蟒。”

---

做出了重要计划，没模拟赛的时候按日期决定训练内容，奇数练板子，偶数练思维。

每日一语：答对了给五块钱吼。——徐度建。

## 4.19
许愿今晚 AT、CF 双上分。

双下分了。。。

AT E、F 调半天。

CF C 假了两次，D 6min 秒了，所以我为什么不先做 D。。。

说下 D 吧，感觉是经典灯泡套路了，观察下奇偶性的不变量就行了。

E 题一开始认为觉得不是贪心，于是开始分析前缀和的性质，然而并没有什么好性质。等我开始编贪心的时候已经编不出对的了。

每日一语：你没有说出为什么，所以只能给你两块五吼。——徐度建。

## 4.20
周日啊，那很爽了。

每日一语：我要去赶高铁了吼。——徐度建。

## 4.21
今天是板子训练。

[[パ研合宿コンペティション 2日目] グランド・グラフ](https://www.luogu.com.cn/problem/AT_pakencamp_2018_day2_g)

简单广义串并联图方法板子题。

当我一份 dfs 逻辑完全错误，搜得又重又漏的，并且下降幂用错的代码，通过了绝大部分测试点时，我不禁怀疑起出题人是拿身体的什么部位造的数据。

洛谷几篇广义串并联图方法题解讲得似乎都不太好啊，很容易让初学者一头问号。其实就是两个问题：

1. 状态的含义是一条边对应的子图内部的方案数（不包括边的两个端点），对于一开始原图的边，对应着一个空子图，方案数视为 $1$。

2. 为什么要定义两端同色和两端异色这一 $0/1$ 状态？你会发现不定义这一维附加状态也能转移，但在删一度点和最后暴搜的时候无法统计答案。

[P6790 [SNOI2020] 生成树](https://www.luogu.com.cn/problem/P6790)

出题人甚至连一档矩阵树定理的部分分都不愿意给，恶毒啊。

kls 题解感觉有点招笑，他的状态定义实际上是：仅考虑边和边的两端构成的子图时，边对应的子图中所有点都与边的两端连通（即所有点之间两两连通）的方案数/边对应的子图中所有点都与且仅与边的一端连通（即形成了两个连通块）的方案数。

下午真摆啊，脑子好混乱。

### [P4292 [WC2010] 重建计划](https://www.luogu.com.cn/problem/P4292)

学弟之前问的题，点分和长剖都能做，都会练一下（我对长剖真的很不熟）。学习了一篇题解的优秀代码实现，但它的复杂度不太对，要改一改。

今晚还有 CF，这回该上分了吧。

1600 perf，那很红温了。

每日一语：我们先看个视频吼。——徐度建。

## 4.22

补了昨晚的 D 题，感觉也不难写啊，为什么就是那么多 bug 呢。。。

昨晚 CF 还出现了久违的读题问题，A 题目还没仔细看就上手写了。

[F 题](https://www.luogu.com.cn/problem/CF2103F)稍微讲下吧，有点意思。

首先考虑如何快速算出一个区间的 $\mathop{nor}$。我们发现它性质似乎很烂，连结合律都没有。不过稍微思考下就发现它其实有比结合律更优秀的性质，我们安慰考虑，每一位的取值只和该区间这一位上的后缀 $0$ 的个数有关，这个信息预处理下就行了。

我们发现这个性质实在是太美妙了，一眼有支配对啊，我们枚举区间右端点 $r$，找出所有有效的 $l$，接下来就是区间 checkmax 问题了，离线 multiset 扫一遍就行了。

E 题不太会，等出了题解再补吧。。。

上场 div1+2 的 E 感觉相当牛。不变量藏得很深，高明啊。

F 是个貌似不难的线段树题，但击杀了很多大佬，可能也是个人差吧。

G 也很牛啊，题解给的最后一个 hint 也很有启发性。

被安徽省初中组题目创死了。

把 [P4292 [WC2010] 重建计划](https://www.luogu.com.cn/problem/P4292) 调出来了，数据有点弱了。

每日一语：大相——差不多吼。——徐度建。

## 4.23
今日模拟赛非常有问题，你可以简单一点，但不能 T3 放个 CF *2300 吧。最有趣的是 这个 *2300 还是你在暑假 NOIP 课程中当中下档题讲过的。而且这题轻松做到线性，出题人还开 $n=10^5$，这么想放原题 $O(384n\log n)$ 的标算过是吧。都 NOI 模拟赛 T3 了，还懒得加强下。

B 也是个不用脑子的题，无语了。

嘿嘿，A 题是树上随机游走板子题，怎么回事呢。

算了，至少不用花时间补题了。

胡了胡长剖。

大哥哥找我 debug 一道题，结果是耳分解，那今晚就训耳分解和双极定向吧。

[P5776 [SNOI2013] Quare](https://www.luogu.com.cn/problem/P5776)

这题感觉题解写的都不太好啊。决定自己写[一篇](https://www.luogu.com.cn/article/yn5r9h1s)。重边是真恶心吧。

开数组开出了个 `dp[][][][1]`，调了半天。

每日一语：普莱设（pressure）、嗦里的（solid）。——徐度建。

## 4.24
上场 CF 的 E 题，比较看脑子。我们逮着一对和为 $k$ 的对薅，通过两次操作能交换一数的和它俩其中一个的位置。所以我们把它俩先放到 $1$ 和 $n$ 两个位置，最后一步把他俩也调整好了。每个数都要换一次要 $2n$ 步，有效的置换环最多 $\frac n2$ 个，在置换环内进出最多也只要 $n$ 步，所以一共不超过 $3n$ 步。

[P12320 [蓝桥杯 2024 国研究生组] 深度优先搜索](https://www.luogu.com.cn/problem/P12320)

做蓝题做着都费劲了(update:怎么升紫了，感觉还是蓝吧)。

考虑序列合法的充要条件：

1. $a_1=0$。
2. $a_i \in [1,a_{i-1}+1]$。

发现每段连续的 $-1$ 间贡献是独立的，直接单独计算。

每段的计数转格路计数即可，比较一眼，但有点细节。

每日一语：有多大？比你想的还要大。——徐度建。

## 4.25
决定离开梦熊了。

[P6192 【模板】最小斯坦纳树](https://www.luogu.com.cn/problem/P6192)

自己胡了个 $O(n^22^n)$ 的做法，知道肯定假了，但是没 hack 掉，WA 了一发后终于造出了简单的 hack。在我假算的转移基础上加上枚举子集的转移就对了。

[CF2096F Wonderful Impostors](https://codeforces.com/contest/2096/problem/F)

在 $*3100$ 里不算太难，但我犯了所有写线段树可能会犯的错误。

学习了 djq 分治，但感觉很多题根号就够用了。

每日一语:西六三除以二吼。——徐度建。

## 4.26
### [P8327 [COCI 2021/2022 #5] Radio](https://www.luogu.com.cn/problem/P8327)

简单题目，把一个数替换成它的所有质因子，问题就变成了单点修改，查询区间内的数是否两两不同。

### [P7026 [NWRRC 2017] Hidden Supervisors](https://www.luogu.com.cn/problem/P7026)

经典贪心，先在每棵树内部贪一贪，树和树的合并部分再贪一贪。

今天 CF 被 B 题搞了，没想清楚就开始写了。感谢 PA，学会了个巧妙双射：左部点度数不大于 $2$ 的二分图最大匹配相当于给边定向使得所有点度数不大于 $1$。

每日一语：这个羧的写法是很多同学一定会搞错的吼。左边是羊的一半，右边是羧的羧吼。——徐度建。

## 4.27
在飞机上睡爽了。

晚上打 ABC，嘟嘟嘟，逆天手速场，难以言说，$200$ 多人 AK。只能说终于在手速场里赢了一次。

每日一语：安琦，我喜欢你。——陈思洲。

## 4.28
上场 CF 的题。。。怎么感觉没一道正常的。不过还是补了。。。

[CF2097D Homework](https://www.luogu.com.cn/problem/CF2097D)

无语诈骗题。

令 $n=2^kB$，将序列划分为 $2^k$ 个长为 $B$ 的段。事实上通过操作，我们能对任意两段进行异或。所以只要高消出线性基即可。

[CF2097E Clearing the Snowdrift](https://www.luogu.com.cn/problem/CF2097E)

有一个显然的贪心：优先做全局最大值。

贪心过程用平衡树有交合并的方式取维护，复杂度不知道为什么是对的，没想到怎么证明。感觉官方题解说能摊到一只老哥还挺神奇的。

每日一语：era~(孔雀叫)不要说徐老师。——陈思洲。

## 4.29
[CF2097F Lost Luggage](https://www.luogu.com.cn/problem/CF2097F)

首先题面写得是真烂啊。发现是个最大流，跑不过去，考虑状压求最小割，就过了。

[P12251 [科大国创杯初中组 2025] 抽卡](https://www.luogu.com.cn/problem/P12251)

很困难，而且这题洛谷现有题解写得都不好，学习起来更困难了。

参考 [[ARC128F] Game against Robot](https://www.luogu.com.cn/problem/AT_arc128_f)，转化成 0/1 问题，此时能设计出一个 $O(n^2m)$ 的简单 DP。

接下来的优化部分，可以参考第一篇题解（这已经是相对来讲最清晰的了）。注意第一篇题解存在各种命名冲突的问题，如：

1. 实际上每个 $f_{i,j}$ 都是一个多项式，而不是如题解所说 $f_i$ 为多项式。

2. 实际上题解中 $\sum\limits_{j=1}^n f_{i,i+j-1}$ 这一部分需要预处理前缀和进行 $O(1)$ 计算。请注意，题解这部分写得极其混乱，最好自行进行推导。

[P4426 [HNOI/AHOI2018] 毒瘤](https://www.luogu.com.cn/problem/P4426)

曾经的神仙题，可惜现在已经退环境了。

翻译：$|E|=|V|+eps$ 图的独立集计数。

$dp_{i,0/1,0/1}$ 表示 $i$ 号边对应子图的独立集方案数，两个 $0/1$ 状态分别表示与边的两端 $u,v$ 相连的点是否能选($0$ 为能)。$f_{i,0}$ 表示 $i$ 号点和它对应子图的独立集方案数，$0/1$ 状态表示 $i$ 号点是否选($0$ 为不选)。

初始状态值全部为除 $dp_{e,1,1}=0$,其他值均为 $0$。

合一度点：

$$f_{v,0}=f_{v,0}\times (dp_{e,0,0}\times f_{u,0}+dp_{e,1,0}\times f_{u,1})$$

$$f_{v,1}=f_{v,1}\times (dp_{e,0,1}\times f_{u,0}+dp_{e,1,1}\times f_{u,1})$$

缩二度点：

$$dp_{nw,0,0}=dp_{e1,0,0}\times f_{u,0}\times dp_{e2,0,0}+dp_{e1,1,0}\times f_{u,1}\times dp_{e2,1,0}$$

$$dp_{nw,0,1}=dp_{e1,0,0}\times f_{u,0}\times dp_{e2,0,1}+dp_{e1,1,0}\times f_{u,1}\times dp_{e2,1,1}$$

$$dp_{nw,1,0}=dp_{e1,0,1}\times f_{u,0}\times dp_{e2,0,0}+dp_{e1,1,1}\times f_{u,1}\times dp_{e2,1,0}$$

$$dp_{nw,1,1}=dp_{e1,0,1}\times f_{u,0}\times dp_{e2,0,1}+dp_{e1,1,1}\times f_{u,1}\times dp_{e2,1,1}$$

叠合重边直接对应乘起来就行。

每日一语：薅薅吼，你好猥琐。——陈思洲。

## 4.30

今天有模拟赛。

T1、T2 两个博弈，T3 时限 10s,一眼就是惹不起的 DS 题，有点像逆天树分块。

T1 玩半天没玩会，不过拼一拼部分分能拿 72。

T2 秒了，观察到两端相同是普及组 T1 难度，两端相异时直接把极长连通块缩起来，只有对从两端开始的操作是有意义的，可以直接区间 DP。感觉榜比较歪啊，T1 过的比 T2 多。

T3 有白给的 50，最大的难点可能在于二维差分。

看了别人的代码，原来 T1 是有固定策略的吗，这么牛。

[[R9F]硬币问题](https://bs.daimayuan.top/p/54?tid=6802503fc1828d18df896ed9)

多项式显然可做，但存在很妙的根号分治，以前 51nod 的题。

有个很浅显的结论是每种硬币最多用 $\sqrt n$ 次，似乎没什么用。但做题经验告诉我们，越是存在自然根号越不能偷懒，应想想根号分治。我们对于面值为 $1\sim B$ 的硬币，我们直接做 $O(nB)$ 的多重背包。对于面值为 $(B+1)\sim n$ 的硬币，可以视作没有数量限制。我们有两种常见的想法，一种是换维做 DP，一种是考虑不重不漏生成序列的经典做法。前者不好做，我们选择对后者 DP，令 $f_{i,j}$ 为选了 $i$ 个数，和为 $j$ 的方案数。状态数是 $O(\frac {n^2} B)$ 的，有对所有数 $+1$ 和添加一个 $B+1$ 两种转移，都是 $O(1) 的$。最后 $O(n)$ 拼接结果就行了。

我们发现这题对面值为 $(B+1)\sim n$ 的硬币的处理有一个巧妙的点，在于有效状态所有数的和不会超过 $n$，保证了不会有数执行了超过 $n-k$ 次 $+1$ 操作，使得我们的 DP 省去了当前最大值这一维。

每日一语：薅薅吼，我好难受。——陈思洲。

## 5.1
[CF1100F Ivan and Burgers](https://www.luogu.com.cn/problem/CF1100F)

原来正解这么简单，那谁还写猫树啊。

晚上打 CF 感觉自己糖糖的，D 题要做这么久。

每日一语：宝贝，我给你做好了早饭你都不吃。——陈思洲。

## 5.2
打 MX 星航计划，搬了三道小米杯的题，都不难。剩下那道不太会啊。

赛后让 AI 给我化简式子，结果它给我秒了。原来可以套用经典组合恒等式：
$$\sum \limits _{i=0} ^M \binom{u+i}{r}\binom{v+M-i}{s}=\binom{u+v+M+1}{r+s+1}$$

这个都不会是不是要完了。

每日一语：这个，饮料，不能当水喝吧。——胡特。

## 5.3

休假。

每日一语：你不写作业，怎么，做得出来题哩。——胡特。

## 5.4

昨天 ABC 看错题打得很遗憾。

今天 ARC D 题在愚蠢的地方写错依旧很遗憾。

不过其实昨晚我对自己的做法并不是很有自信，看到没过样例就觉得是自己写假了。

每日一语：我已经十年没喝过饮料了。——胡特。

## 5.5

[CF2104G Modulo 3](https://www.luogu.com.cn/problem/CF2104G)

简单题——吗？发现自己不会带权并查集了。

CF 打得很唐。可以说使用了最差的规划开题。。。

主要是 F1 转移少写个 min 调不出来换题还是太不理智了。

每日一语：你看《鹿鼎记》，不要想入非非呐？和韦小宝一样好几个老婆啊？——胡特。

## 5.6

昨晚 E 题什么纯种 ad-hoc。

昨晚 F2 我觉得官方题解对关键结论的证明有问题啊。

[CF2108F Fallen Towers](https://www.luogu.com.cn/problem/CF2108F)

非常神秘的题目。

我们非常神秘地观察到这个问题可以二分答案，再非常神秘地编一个非常神秘的贪心就能非常神秘地通过本题。

![学弟返图](https://cdn.luogu.com.cn/upload/image_hosting/bgeldsvc.png)

学弟返图。。。

每日一语：又在看武侠呐？你们高中就把我们那时候大学干的事干完了嘞。——胡特。

## 5.7

休眠期。

每日一语：呃，这个《校本作业》的题目啊，选得特别好，尤其是这个第二章。——徐度建。

## 5.8

上午补了一堆乱七八糟的题目。。。怎么哪儿的题都有，只能说欠的题太多了。

上午看到了 lxl 的模拟赛，想了一半结果比赛被撤下了。好像这不是 lxl 第一次出这种锅了。。。

下午打了洛谷的 COTS 2025 镜像赛。T2、T3 都挺简单的，T1 没细想，感觉有点难度。

每日一语：你们就不能在打铃前回到座位上嚒。——徐度建。

## 5.9
从今天起每日一语停更。

有昨天 T1 的题解了，感觉相当妙啊，记录一下。

[P12447 [COTS 2025] 砍树 / Stablo](https://www.luogu.com.cn/problem/P12447)

发现题目保证了树的每个节点度数不超过 $3$。

既然它都帮你三度化好了，何不边分治呢？

于是对于每个点增量构造即可，构造过程利用边分治的性质，一个点只会查 $O(\log n)$ 次。

小战 JOI，犯下了不排序就二分的离奇错误。

## 5.10
[CF2107F2 Cycling (Hard Version)](https://www.luogu.com.cn/problem/CF2107F2)

这回用另一种方式理解了官方题解的结论，套个斜率优化就行了。考虑到李超树比二分栈好写，所以选择了李超树。

发现克罗地亚国家队选手竟然都不会 $O(nm)$ 树形背包。

感觉昨晚 ABC 的 G 题出题人精神不太正常，莫队+分块的 $O(n\sqrt n)$ 开 $n=2.5\times 10^5$，时限 $2s$。

## 5.11
[P12446 [COTS 2025] 答好位 / Vrsta](https://www.luogu.com.cn/problem/P12446)

有两篇题解均讲述了笛卡尔树做法，该做法操作次数的正确性基于以下结论：排列中每个数的前驱后继在笛卡尔树上的距离和是 $O(n)$ 的。

打了场 CF，很困，被自己恶心到了。

看 A，是不是一层一层加正方形就对了，怎么 WA on 1？哦哦哦，要把 $0$ 放中间。欸，蚊香型数组要怎么输出来着，随便编了一个还算好写的做法，但有些细节没想明白，调了一会儿。

看 B，奇数位置偶数位置分开排序，最后四个数判一判是不是就很对了。那先找找不变量吧，然后我在各种位移距离相关的想法上思考了 20 min 无果，期间想过要不要直接平衡树/链表模拟排序过程算了。最后终于是想起来逆序对了。排序相关问题找不变量不找逆序对个数相关不知道在想什么。

看 C，转化成选区间问题，发现如果存在两个区间无交那么一定不优，所以肯定存在一种最优解最大的左端点小于最小的右端点。~~秒了啊，那不是随便做了吗？~~ 然后我成功没切。

我们预处理出每个前缀最多能选出多少个左端点为 $pre_i$，每个后缀最多能选出多少个右端点为 $bck_i$。找到最大的 $i$ 使得 $pre_i \leq bck_{i+1}$，然后在前 $i$ 个里选左端点就行了。

赛时我并没有意识到 $pre_i$ 和 $bck_i$ 是好预处理的，所以选择了二分出这个最大的 $i$，问题不大。但是哪怕二分了后仍没能写对计算如何计算单个的 $pre_i$ 的部分，问题很大。

PA 还有一个很厉害的结论，对于线段 $[i,i+1]$，它在最优解里覆盖的次数为 $min(pre_i,bck_{i+1})$。这中结论都能注意到感觉 PA 也太强大了。

看别人代码发现 WZH 写的也是 PA 这个做法，怎么都这么有注意力。

## 5.12
被 [P12445 [COTS 2025] 数好图 / Promet](https://www.luogu.com.cn/problem/P12445) 干碎了，太困难了。已经建议升黑了。

## 5.13
VP 去年的 APIO，但因为去年受到了一定程度的剧透（尤其是有人跟我说过 T3 有个做法和 excrt 相关），所以三题都嘴巴秒了（）。

[P3648 [APIO2014] 序列分割](https://www.luogu.com.cn/problem/P3648)

学弟问的题，感觉挺不错的。

观察到切割顺序不影响答案大小，所以可以 $O(nk)$ 斜率优化通过本题。

不过这东西一眼是凸的，直接 wqs 二分，就变成 $O(n\log n)$ 了。

[P10169 [DTCPC 2024] mex,min,max](https://www.luogu.com.cn/problem/P10169)

观察到经典的 min 与 mex 的两者必有一个为 $0$，对两种情况分别去做。

min 可以枚举最大值，然后左右二分出左右边界，进行计算。

mex 也可以枚举最大值，然后启发式分裂。在短的那段提取出 $O(siz_{short})$ 个关键点，在长的那段二分出关键点第一次出现的位置，能做到 $n\log^2 n$。

考虑优化，mex 有经典支配对（然而我此前不会），取出后枚举 mex 即可，能做到 $n\log n$。

## 5.14
[CF2101D Mani and Segments](https://www.luogu.com.cn/problem/CF2101D)

线性做法还挺有价值的。

首先矩形面积并并不用线段树，观察下发现这题矩形间的位置相当好啊，各种坐标全是单调的。

更重要的是处理出左右能延伸的边界这步，也并不需要在值域上维扫，直接按原序列顺序扫就行了。也并不需要单调栈，开两个变量就行。做这步需要比较详细的分析一下这东西的性质。

## 5.15~5.19

APIO

## 5.20
VP 了 JXCPC，感觉可做题数量在 10~11 左右，还行。剩下两题感觉也没什么营养。

## 5.21
发现 [P3648 [APIO2014] 序列分割](https://www.luogu.com.cn/problem/P3648) 之前胡的 wqs 是假的，构造不了方案。

[P3600 随机数生成器](https://www.luogu.com.cn/problem/P3600)

简单题。考虑 Min-Max 容斥，直接设计出三方 DP。观察到一个区间如果包含了其他区间那么它一定没用，容易优化成平方 DP。

事实上直接做也不难。直接贺了一发直接做的代码。

[P12426 [BalticOI 2025] BOI acronym](https://www.luogu.com.cn/problem/P12426)

智力测试。容易找到第一个和最后一个 B 的位置，借助它们就能确定剩下每一位是不是 B。

[P12427 [BalticOI 2025] Tour](https://www.luogu.com.cn/problem/P12427)

厉害题目。想了半天优化建图没什么思路，打开题解，是二进制拆位？？？怎么这么妙啊。

还有线性做法，观察到一个点只要记录它的两个不同色前驱就够了。能做到 $O(n)$。

## 5.22

[P12428 [BalticOI 2025] Tower](https://www.luogu.com.cn/problem/P12428)

比较正常的题目。考虑归并排序，我们们有很大概率能划分出出较均匀的两部分。而且我们的交互操作恰好能检验出我们的划分是否均匀。

不过据说比较卡，需要精细实现。那还是不写了。

[P12429 [BalticOI 2025] Developer](https://www.luogu.com.cn/problem/P12429)

逆天结论题。首先容易猜想 $b_i \in a$，不过容易发现这是错的。那么再猜 $b_i \in \{a_j-1,a_j,a_j+1，1\leq j\leq n\}$，这回对了，得到 $O(n^2)$ 做法。

继续猜，也许 $b_i \in \{a_j-1,a_j,a_j+1，i-O(1)\leq j\leq i+O(1)\}$ 呢？恭喜啊，又猜对了，这下变 $O(n)$ 了。

[P11536 [NOISG 2023 Finals] Curtains](https://www.luogu.com.cn/problem/P11536)

似乎大家的转化思路都一样，但转化后的 DS 问题就有不同的做法了。

## 5.23

[P4331 [BalticOI 2004] Sequence 数字序列](https://www.luogu.com.cn/problem/P4331)

远古疑难杂症，从前年不会到今年。终于战胜之。

打了牛客，AI 参赛的竟然不直接 ban，只 skip 用了 AI 的题目，感觉太离谱。这种东西哪怕是初犯不也应该直接 skip 掉整场成绩吗。

[P12431 [BalticOI 2025] Gingerbread](https://www.luogu.com.cn/problem/P12431)

分析分析能分析出暴搜能过，然后就暴搜，然后就过了。不过洛谷题解都没证明暴搜能过，还得看官方题解。

## 5.24
[P12450 [INOI Team Selection 2021] Maximal Tree Coloring](https://www.luogu.com.cn/problem/P12450)

真不是绿吗，怎么是紫的。

## 5.25
打 ARC。

秒 A，写一发，过了。

秒 B，写一发，WA 了。发现少打了一个 if，加上，过了。

猜 C，猜测模拟到最后如果两个数交换不过来就无解，不过看榜前的人罚了很多发，不敢写，应该这个做法没什么道理。

秒 D，写一发，WA 了，不想调，感觉可能做法是假的，下班。

掉分了，好欸！！！

## 5.26

和场切了昨晚 D 题的一位学弟交流了下这题的做法，没问题，于是开调。调不出来，于是拿学弟的代码对拍，破案了：`has[u]=has[fa]*bas+b[u]%mod;`。

C 题的结论果然是错的，最后两个数可以交换。明明交换操作这么简单怎么没发现呢。发现了可以交换两个数后这题就乱做了。那感觉 C 题还是比 D 题简单的。至于 C 的 Bonus 感觉是阴间题目。

听 251Sec 讲课，内容是各种奇形怪状的背包。有几个是之前就会的，有几个是现在还不会的。

[P12451 [INOI Team Selection 2021] Labelless Graph](https://www.luogu.com.cn/problem/P12451)

感觉和 [P12426 [BalticOI 2025] BOI acronym](https://www.luogu.com.cn/problem/P12426) 是同一类题目，不过这题在 $n=2$ 时不可做，就离谱。

[P4151 [WC2011] 最大XOR和路径](https://www.luogu.com.cn/problem/P4151)

古早性质题。性质：无向图的所有环都能通过 dfs 找出的环异或出来。

## 5.27
[P12452 [INOI Team Selection 2021] Color Colony](https://www.luogu.com.cn/problem/P12452)

难点在于观察到所有这颗树会被划分成若干个同色连通块，每种颜色的连通块只会有一个。我一开始想的构造甚至是每种颜色相距越远越好。

[P12453 [INOI Team Selection 2021] Lisdeque](https://www.luogu.com.cn/problem/P12453)

简单题，但我没什么脑子，想了很久。洛谷还没题解，打算写一篇。

## 5.28

时隔一个月，终于打了次模拟赛。题挺好的，但我人挺不好的。

## 5.29

上午是 lqy 讲课。讲课内容惊现数好图。

## 5.30
[P12454 [INOI Team Selection 2021] String](https://www.luogu.com.cn/problem/P12454)

简单题，可以做到 $O(kS_n)$ 或 $O(\frac{kS_n\log\Sigma}{\omega})$。后者应该比前者快好几倍。

[CF1062F Upgrading Cities](https://www.luogu.com.cn/problem/CF1062F)/[P11073 Game King](https://www.luogu.com.cn/problem/P11073)

几乎一模一样的两题，比较简单。卡常/tuu。

[AT_agc071_c [AGC071C] Orientable as Desired](https://www.luogu.com.cn/problem/AT_agc071_c)

谢谢出题人，可以用来检查我还会不会写点双。

检查完毕，果然不会。

## 5.31

一天打了三场比赛，吃了三大口。

## 6.1

又有模拟赛，T1 是个树上博弈。观察出两人的策略后需要处理出每个子树内直径和子树外直径。子树外直径我选择了换根这种最难写的写法，怎么回事呢？

晚上打 ARC，T1 不会，下班。

## 6.2
怎么没写游记，算了不补了。

## 6.3
[CF342E Xenia and Tree](https://www.luogu.com.cn/problem/CF342E)

虽然怎么做都行，但最重要的还是操作分块做法。

[P3214 [HNOI2011] 卡农](https://www.luogu.com.cn/problem/P3214)

绷不住了，xy 的题单里怎么放了这题。我还真没写过，写一下。

[CF1750F Majority](https://www.luogu.com.cn/problem/CF1750F)

2700 分的题，感觉已经到了我能独立做出的数数题难度上限了。

[CF1043F Make It One](https://www.luogu.com.cn/problem/CF1043F)

昨天在想判一个集合是否有互质对怎么做，想了很久都不会。突然意识到我转成这题不就行了吗，这题我会啊。

[P7450 [THUSC 2017] 巧克力](https://www.luogu.com.cn/problem/P7450)

感觉是个放现在该降紫的题。最小斯坦纳树、二分解决中位数、随机映射都是比较广为人知的东西了，整道题也比较好想（可能建模成最小斯坦纳树没那么好想？）。

卡常，而且我比较非，调参调了几发才过。

## 6.4

神奇 32 模拟赛。

NOI 模拟赛但难度不升序。

减去正确性的暴搜剪枝能助力你剪成 95pts。

一眼假的贪心能干到 50pts+。

签到成功就有 245 pts+ 了，可以登上联考 rank2 了。

[CF1558E Down Below](https://www.luogu.com.cn/problem/CF1558E)

模拟赛题削弱版，直接抄原题代码有 50pts。但这 50pts 被我用没剪枝的暴搜搜过去了。

[P9829 [ICPC 2020 Shanghai R] Traveling Merchant](https://www.luogu.com.cn/problem/P9829)

很好的题，但只记录下图论部分吧。

问题是给你一个无向图，多次询问是否存在一条简单路径，依次经过 $1$，$x$，$y$ 三点。

考虑树的情况，我们以 $1$ 为根，容易发现只要判断 $x$ 和 $y$ 是否具有祖孙关系。对于一般图的情况，建出圆方树，做类似的事情即可。

## 6.5~6.7

怎么三天没写游记啊，咕了咕了。

## 6.8

在 XYD 训练的第二天，模拟赛获得了 26pts 的好成绩。

今天的 T1 对我来说还是太深刻了。

[P6246 [IOI 2000] 邮局 加强版 加强版](https://www.luogu.com.cn/problem/P6246)

一只老哥做法还是很有教育意义的，两只老哥能过凭什么黑啊。

用了题解区代码对拍，发现题解区代码挂了一车，被数据随机放过去了。

## 6.9

[AT_arc076_d [ARC076F] Exhausted?](https://www.luogu.com.cn/problem/AT_arc076_d)

发现是个二分图最大匹配，优化建图不太能跑，考虑 Hall 定理。问题变成给你若干个区间，最大化选取区间个数和区间交集大小之和。

可以使用扫描线+线段树解决。

[CF2002F2 Court Blue (Hard Version)](https://www.luogu.com.cn/problem/CF2002F2)

发现 Easy Version 是 $n=m$，先想这个，秒了。

然后看看能不能能不能把 Hard Version 也想了，感觉加点小分讨就行了啊。不想想细节了，直接看题解。

假了，看题解，发现可以乱搞，由于神秘的数论力量，能过。

[AT_abc336_g [ABC336G] 16 Integers
](https://www.luogu.com.cn/problem/AT_abc336_g)

首先我没想到能转成欧拉路径计数。

其次我不知道欧拉路径计数怎么做。

接着我对 BEST 定理本来就理解不深。

最后这题曾经一度是道蓝题。

[P9247 [集训队互测 2018] 完美的队列](https://www.luogu.com.cn/problem/P9247)

趣味 DS，不过不太打算研究 polylog 了。

## 6.10
[CF475E Strongly Connected City 2](https://www.luogu.com.cn/problem/CF475E)

边双缩点，然后猜一个不好猜的结论，dp 一下，然后过了。

[CF1896G Pepe Racing](https://www.luogu.com.cn/problem/CF1896G)

PA 分享的交互。

PA：这题不难。RYZ：感觉确实不难。

[P4425 [HNOI/AHOI2018] 转盘](https://www.luogu.com.cn/problem/P4425)

先观察到每个点最多被经过一次。枚举起点，推出对于每个起点的式子，单边递归线段树维护即可。

[P12293 [蓝桥杯 2024 国 Java A] 合并小球](https://www.luogu.com.cn/problem/P12293)
概率 dp，但能容斥。

[P9962 [THUPC 2024 初赛] 一棵树](https://www.luogu.com.cn/problem/P9962)

有个一眼的背包。欸，怎么是绝对值；欸那它是不是凸的；欸，怎么做完了。

[P11845 [USACO25FEB] Min Max Subarrays P](https://www.luogu.com.cn/problem/P11845)

$n$ 为大于 $5$ 的奇数时，答案为区间最大值，$n$ 为大于 $8$ 的偶数时，答案为区间次大值。分治即可。

[[ARC093F] Dark Horse](https://www.luogu.com.cn/problem/AT_arc093_d)

常规数数题。感觉可以当作基本功练习题。

[CF2117H Incessant Rain](https://www.luogu.com.cn/problem/CF2117H)

简单~~崩铁~~ DS 题，用平衡树做的话可以不带什么脑子。

[P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces](https://www.luogu.com.cn/problem/P10856)

Xor Round 的题目/tuu。

只能说题出的好，给出题人点赞。

## 6.11

被模拟赛创死了。

[CF1456E XOR-ranges](https://www.luogu.com.cn/problem/CF1456E)

模拟赛 T1。看题解还是感觉脑子被干烧了，感觉最近脑子严重不够用啊。

做吐了，边界好恶心。

## 6.12

又是被模拟赛创飞的一天。

今天 T2 太有趣啦。

[QOJ2559 Endless Road](https://qoj.ac/contest/820/problem/2559)

昨天模拟赛的 T3，感觉比 T1 和 T2 都简单啊。

没想到怎么维护候选区间，所以没场切，太失败。

不过这个奇妙贪心维护候选区间真有点难度吧。

## 6.13

打 CF 被翻译创死了。AI 翻译：furthest=**最近的** 。

## 6.14

模拟赛终于放签子了。

[P12558 [UOI 2024] Heroes and Monsters](https://www.luogu.com.cn/problem/P12558)

建议升黑。

很厉害的观察，就喜欢这种代码短小的题目。

要想清楚真挺难的。

正在渲染内容...