NOI2025游记
sdyzpf
·
2025-03-31 14:38:07
·
生活·游记
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
今天又没有模拟赛！！！
把昨晚那题出出来了，没造数据。
今天依旧没有模拟赛~
感觉想依靠网上现存的资料学习动态高消比较困难，想写一篇讲解动态高消的博客，不过犯懒了又不想写了。
开谷谷迷，感觉 1、3、5 和 2、4 的难度差异太大了。
今天好摆啊好摆啊好摆啊好摆啊好摆啊好摆啊好摆啊。
每日一语：哎，我也是有父母的吼！——徐度建（2025/4/1 所说）。
4.5
完成了前晚的那题的题解。
目前我写的字符串专栏内容还比较少，暂不公开，等题目数量达到 10+ 再放出来吧。
想了想还是直接放出来吧，可以先把框架写好，题解内容后面再补。
今晚同时有 AT 和 CF，可以水游记字数了！
大败而归。
AT 成功做到了通过的每一题都有罚时，实在过于逆天。
CF 不会 E 题，然后 C 题一个 n 打成了 n/2 调半天，不好评价。
每日一语：呃，别急！别急！别急！——徐度建。
4.6
打了场失败的 ARC。
只能说 B 题是我非常不擅长的一类题目。
每日一语：沃~沃！我没急！我没急！我没急！——徐度建。
4.7
模拟赛出现了个 P6076 [JSOI2015] 染色问题 加强版，结果全程没往二项式反演上想，感觉非常的失败。
学习了背包科技。
学习了有源汇上下界最小费用可行流。
模拟赛 T3 是个逆天 slope tirck 题，因为没怎么写过相关题目，所以打算补一下。
学习了模拟费用流。
被模拟赛 T3 硬控了 5h /tuu。
我的华语歌单基本修缮完了，网易云太多歌没版权了/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 的帮助下彻底解决了分块题。
准备拿来当祖传防 AK 题了。
今天北京大风，提前离校了。
怎么游记开始水起来了，明天开始想办法充实下。
每日一语：一定会考的吼。——徐度建。
4.12
然而事实上并没怎么刮风。
破防了，打 ABC，G 题本地精度不够但交上去过了。。。
每日一语：本节课分为两个部分，前半部分是重点，后半部分是难点吼。——徐度建。
4.13
今天开始刮风了。
看了眼 UR 的题，果然很难，不看了。
每日一语：我还是有点水平的吼。——徐度建。
4.14
口胡秒了 P4770 [NOI2018] 你的名字，很开心。
换了头像，起因是 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日目] グランド・グラフ
简单广义串并联图方法板子题。
当我一份 dfs 逻辑完全错误，搜得又重又漏的，并且下降幂用错的代码，通过了绝大部分测试点时，我不禁怀疑起出题人是拿身体的什么部位造的数据。
洛谷几篇广义串并联图方法题解讲得似乎都不太好啊，很容易让初学者一头问号。其实就是两个问题：
状态的含义是一条边对应的子图内部的方案数（不包括边的两个端点），对于一开始原图的边，对应着一个空子图，方案数视为 1 。
为什么要定义两端同色和两端异色这一 0/1 状态？你会发现不定义这一维附加状态也能转移，但在删一度点和最后暴搜的时候无法统计答案。
P6790 [SNOI2020] 生成树
出题人甚至连一档矩阵树定理的部分分都不愿意给，恶毒啊。
kls 题解感觉有点招笑，他的状态定义实际上是：仅考虑边和边的两端构成的子图时，边对应的子图中所有点都与边的两端连通（即所有点之间两两连通）的方案数/边对应的子图中所有点都与且仅与边的一端连通（即形成了两个连通块）的方案数。
下午真摆啊，脑子好混乱。
P4292 [WC2010] 重建计划
学弟之前问的题，点分和长剖都能做，都会练一下（我对长剖真的很不熟）。学习了一篇题解的优秀代码实现，但它的复杂度不太对，要改一改。
今晚还有 CF，这回该上分了吧。
1600 perf，那很红温了。
每日一语：我们先看个视频吼。——徐度建。
4.22
补了昨晚的 D 题，感觉也不难写啊，为什么就是那么多 bug 呢。。。
昨晚 CF 还出现了久违的读题问题，A 题目还没仔细看就上手写了。
F 题稍微讲下吧，有点意思。
首先考虑如何快速算出一个区间的 \mathop{nor} 。我们发现它性质似乎很烂，连结合律都没有。不过稍微思考下就发现它其实有比结合律更优秀的性质，我们安慰考虑，每一位的取值只和该区间这一位上的后缀 0 的个数有关，这个信息预处理下就行了。
我们发现这个性质实在是太美妙了，一眼有支配对啊，我们枚举区间右端点 r ，找出所有有效的 l ，接下来就是区间 checkmax 问题了，离线 multiset 扫一遍就行了。
E 题不太会，等出了题解再补吧。。。
上场 div1+2 的 E 感觉相当牛。不变量藏得很深，高明啊。
F 是个貌似不难的线段树题，但击杀了很多大佬，可能也是个人差吧。
G 也很牛啊，题解给的最后一个 hint 也很有启发性。
被安徽省初中组题目创死了。
把 P4292 [WC2010] 重建计划 调出来了，数据有点弱了。
每日一语：大相——差不多吼。——徐度建。
4.23
今日模拟赛非常有问题，你可以简单一点，但不能 T3 放个 CF 2300 吧。最有趣的是 这个 2300 还是你在暑假 NOIP 课程中当中下档题讲过的。而且这题轻松做到线性，出题人还开 n=10^5 ，这么想放原题 O(384n\log n) 的标算过是吧。都 NOI 模拟赛 T3 了，还懒得加强下。
B 也是个不用脑子的题，无语了。
嘿嘿，A 题是树上随机游走板子题，怎么回事呢。
算了，至少不用花时间补题了。
胡了胡长剖。
大哥哥找我 debug 一道题，结果是耳分解，那今晚就训耳分解和双极定向吧。
P5776 [SNOI2013] Quare
这题感觉题解写的都不太好啊。决定自己写一篇。重边是真恶心吧。
开数组开出了个 dp[][][][1]，调了半天。
每日一语：普莱设（pressure）、嗦里的（solid）。——徐度建。
4.24
上场 CF 的 E 题，比较看脑子。我们逮着一对和为 k 的对薅，通过两次操作能交换一数的和它俩其中一个的位置。所以我们把它俩先放到 1 和 n 两个位置，最后一步把他俩也调整好了。每个数都要换一次要 2n 步，有效的置换环最多 \frac n2 个，在置换环内进出最多也只要 n 步，所以一共不超过 3n 步。
P12320 [蓝桥杯 2024 国研究生组] 深度优先搜索
做蓝题做着都费劲了(update:怎么升紫了，感觉还是蓝吧)。
考虑序列合法的充要条件：
发现每段连续的 -1 间贡献是独立的，直接单独计算。
每段的计数转格路计数即可，比较一眼，但有点细节。
每日一语：有多大？比你想的还要大。——徐度建。
4.25
决定离开梦熊了。
P6192 【模板】最小斯坦纳树
自己胡了个 O(n^22^n) 的做法，知道肯定假了，但是没 hack 掉，WA 了一发后终于造出了简单的 hack。在我假算的转移基础上加上枚举子集的转移就对了。
CF2096F Wonderful Impostors
在 *3100 里不算太难，但我犯了所有写线段树可能会犯的错误。
学习了 djq 分治，但感觉很多题根号就够用了。
每日一语:西六三除以二吼。——徐度建。
4.26
P8327 [COCI 2021/2022 #5] Radio
简单题目，把一个数替换成它的所有质因子，问题就变成了单点修改，查询区间内的数是否两两不同。
P7026 [NWRRC 2017] Hidden Supervisors
经典贪心，先在每棵树内部贪一贪，树和树的合并部分再贪一贪。
今天 CF 被 B 题搞了，没想清楚就开始写了。感谢 PA，学会了个巧妙双射：左部点度数不大于 2 的二分图最大匹配相当于给边定向使得所有点度数不大于 1 。
每日一语：这个羧的写法是很多同学一定会搞错的吼。左边是羊的一半，右边是羧的羧吼。——徐度建。
4.27
在飞机上睡爽了。
晚上打 ABC，嘟嘟嘟，逆天手速场，难以言说，200 多人 AK。只能说终于在手速场里赢了一次。
每日一语：安琦，我喜欢你。——陈思洲。
4.28
上场 CF 的题。。。怎么感觉没一道正常的。不过还是补了。。。
CF2097D Homework
无语诈骗题。
令 n=2^kB ，将序列划分为 2^k 个长为 B 的段。事实上通过操作，我们能对任意两段进行异或。所以只要高消出线性基即可。
CF2097E Clearing the Snowdrift
有一个显然的贪心：优先做全局最大值。
贪心过程用平衡树有交合并的方式取维护，复杂度不知道为什么是对的，没想到怎么证明。感觉官方题解说能摊到一只老哥还挺神奇的。
每日一语：era~(孔雀叫)不要说徐老师。——陈思洲。
4.29
CF2097F Lost Luggage
首先题面写得是真烂啊。发现是个最大流，跑不过去，考虑状压求最小割，就过了。
P12251 [科大国创杯初中组 2025] 抽卡
很困难，而且这题洛谷现有题解写得都不好，学习起来更困难了。
参考 [ARC128F] Game against Robot，转化成 0/1 问题，此时能设计出一个 O(n^2m) 的简单 DP。
接下来的优化部分，可以参考第一篇题解（这已经是相对来讲最清晰的了）。注意第一篇题解存在各种命名冲突的问题，如：
实际上每个 f_{i,j} 都是一个多项式，而不是如题解所说 f_i 为多项式。
实际上题解中 \sum\limits_{j=1}^n f_{i,i+j-1} 这一部分需要预处理前缀和进行 O(1) 计算。请注意，题解这部分写得极其混乱，最好自行进行推导。
P4426 [HNOI/AHOI2018] 毒瘤
曾经的神仙题，可惜现在已经退环境了。
翻译：|E|=|V|+eps 图的独立集计数。
初始状态除 $dp_{e,1,1}=0$,其他值均为 $1$。
合一度点：
$$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)
非常神秘的题目。
我们非常神秘地观察到这个问题可以二分答案，再非常神秘地编一个非常神秘的贪心就能非常神秘地通过本题。
学弟返图。。。
每日一语：又在看武侠呐？你们高中就把我们那时候大学干的事干完了嘞。——胡特。
## 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)
建议升黑。
很厉害的观察，就喜欢这种代码短小的题目。
要想清楚真挺难的。
ABC 大失败。G 题光速想到怎么处理环，问题转换成有若干个区间，取出尽可能多的区间，使得两两之间存在包含关系。
然后就不会了。其实按一端排序后，另一端跑 LIS 就行了。但是全程都没把二维偏序的条件列出来，太蠢了。
## 6.15
喜报，模拟赛又有签。
打 ARC，成为保龄小丑。
## 6.16
看昨天 A 题题解，感觉确实是我做不出来的题。
B 题属于是能做出来的题。
C 题属于随便做就能做出来的题。建议和 A 题 swap 一下。
D 题和 A 题结婚吧。
E 题属于是想到第一步才能做出来的题。
[UOJ890 兵棋](https://uoj.ac/contest/91/problem/890)
想看看自己能不能拿下去年 UNR D2T1。
秒了一个 $O(nk^2)$ 的做法，有 92 分欸，~~要不就这么润了吧~~。
大概的想法就是我们考虑对于每个位置，计算它在多少种方案下能活到最后。考虑令 $dp_{i,j,d}$ 表示考虑了前 $i$ 个位置，$i$ 的上一个对手棋子能活到第 $j$ 轮，与 $i$ 的距离为为 $d$ 的方案数。$d>j$ 的状态显然没用，状态数是 $O(nk^2)$ 的，转移 $O(1)$。
感觉很有前途啊，考虑优化状态。第一想法是状态只记 $j-d$，但是只有差值不好统计答案，并且当 $d=1$ 的时候也无法转移。
哦，原来是假了啊。一个位置 $i$ 不一定是被初始位置中上一个对手干掉。
有点乱了，重新理一下。怎么计算位置 $i$ 的死亡时间？考虑位置 $i$ 最终是被位置 $j$ 干死的，那么在此之间所有位置都得死得比他俩早。进一步的，从小往打枚举时间 $t$，如果上一个第 $t$ 秒死的是 $j$，那么在第 $t$ 秒的时候 $j$ 所处的连续段一定会带走一个敌人，那这个人只能是新加入的 $i$，这样就能算出 $i$ 的死期了。
进一步想一下，我们并不在乎 $i$ 的死期，只在乎 $i$ 能不能活到最后，所以可以令 $dp_{i,j}$ 表示考虑了前 $i$ 个位置，每个时间点暴毙的最后一个棋子中有几个是我方的。这样状态数就是 $O(nk)$ 的，转移 $O(1)$。
这题想了 2.5h，要没救了/tuu。
[P2144 [FJOI2007] 轮状病毒](https://www.luogu.com.cn/problem/P2144)
无锡转轮，一眼矩阵树定理板子，二眼怎么没有模数。对着行列式化一化能化出递推式。
[CF2115D Gellyfish and Forget-Me-Not](https://www.luogu.com.cn/problem/CF2115D)
精巧小贪心。
## 6.17
第一题看着就很像流啊，但怎么建不出图。上了个厕所，厕所里发现这不是随便就转成二分图最大权完美匹配吗。写了个费用流板子后到洛谷上测了一发，怎么爆了。原来是 dinic 的时候没记 vis 数组。建图部分还挺难写，源点编号错了调半年。
第二题推了推，发现好像会了？测了一发发现死了。原来并查集要删点的啊，那套个线段树分治是不是就对完了。怎么过不了样例啊，调啊调，调不动。怎么没什么时间了，算了每次暴力重新并查集拿个部分分吧。
然后就 100+40+40 爆炸了。
[P6575 [BalticOI 2017] Friends](https://www.luogu.com.cn/problem/P6575)
难度炸裂的暴力 ad-hoc。做法很暴力，但想到调整真难啊。
## 6.18
[P11106 [ROI 2023] 峰值 (Day 1)](https://www.luogu.com.cn/problem/P11106)]
今天模拟赛 T1，险些签到失败。
## 6.19
来到了 cyez。
[CF1270H Number of Components](https://www.luogu.com.cn/problem/CF1270H)
妙妙思维题。转成 0/1 串后对数据结构维护小子串信息的想法很妙啊。
[P9248 [集训队互测 2018] 完美的集合](https://www.luogu.com.cn/problem/P9248)
困难题目。首先又是讨厌的连通块，不那么能感受到。然后这个 dp 有很难啊。
## 6.20
模拟赛很困，没什么思考的欲望，其实是三个可做题。
[CF1253F Cheap Robot](https://www.luogu.com.cn/problem/CF1253F)
这是 T1，很妙很好啊。最短路 + kruscal 重构树，这是什么，这是大号归程。但我签到失败。
[P12462 [Ynoi Easy Round 2018] 星野爱久爱海](https://www.luogu.com.cn/problem/P12462)
T2，这种 DS 对我来说还是太困难了。
[P5044 [IOI 2018] meetings 会议](https://www.luogu.com.cn/problem/P5044)
这是 T3，IOI 场上没人过的题。
[AT_arc070_d [ARC070F] HonestOrUnkind](https://www.luogu.com.cn/problem/AT_arc070_d)
神仙题目，类摩尔投票法。
## 6.21
模拟赛显然炸了。
深夜 CF，E 题太难写，摆烂了。
## 6.22
结论，一个数被拆成若干个 $2^i$ 相加，那么一定能分组使得每组的和为这个数对应二进制位。
[CF547D Mike and Fish](https://www.luogu.com.cn/problem/CF547D)
与豪赌和率开封场上没切的 *2600。感觉还行，不过拿欧拉回路辅助定向其实没那么多见。
[P10785 [NOI2024] 集合](https://www.luogu.com.cn/problem/P10785)
哈希秒了，但并没有意识到双指针为何物。
[P10786 [NOI2024] 百万富翁](https://www.luogu.com.cn/problem/P10786)
一开始枚举当前层划分的段数，经过了一定调参得到了 $t=8,s=1500462$ 的做法。分数不如两两匹配高。
转而枚举当前层每段的长度，直接得到了 $t=8,s=1099947$ 的做法？？？
我们根据段长 $d$ 推导出段数为 $\lfloor \frac nd \rfloor$ 似乎并不最优，再补个 $\lfloor \frac nd \rfloor+1$ 是不是更有道理？啊?怎么过了？而且这个东西跑的飞快。
事实上枚举段数，用决策单调性取代乱搞也能得出正解。
今晚 ARC 能上分吗。
上分了，可惜打得很不美满。
## 6.23
模拟赛分数一天比一天低。
最小直径生成树是什么东西，顺从了。
今晚 EDU 能上分吗。不过小号这个分很难下了。
权衡了一下还是没打。
## 6.24
模拟赛分数终于变高了，但排名变差了/ll。
[CF607E Cross Sum](https://www.luogu.com.cn/problem/CF607E)
模拟赛 T1，有个差不多的题：
[AT_abc263_h [ABC263Ex] Intersection 2](https://www.luogu.com.cn/problem/AT_abc263_h)
感觉不难啊，但是我发扬人类智慧拿到了 90pts，所以也没想正解。
## 6.25
觉得去年 D2T2 不能只拿 $O(n^2)$ 的分，明天认真做一做这题。
## 6.26
一开始看错题了，以为 $l_i=r_i$ 和 $p_i=i-1$ 都是棒棒糖题，$$h_i=0$$ 是最有难度的。把 $p_i=i-1$ 的做法搬到树上就是正解了！非常惊讶，不敢相信，果然再读一遍题发现出问题了。
然后就是原来的“正解”没完全死，可以做 $h_i=0$ 的部分分，这下原本最难的部分分成最简单的了。
$l_i=r_i$ 依旧是简单的，$p_i=i-1$ 投降了。感觉几乎正解了。
VP NOI2023 Day1。
15:20 开考。
15:44 在本地调完了 T1 95pts 代码，在洛谷一交，0pts。盯了半天代码没觉得有什么问题，去 QOJ 交，0pts。但洛谷是 TLE，QOJ 是 RE？突然间意识到可能发生了什么，去代码里检查每个函数的返回值，果然出现了 `int pushup(p)`。linmobi省选就是被这个东西害退役的，唉。
16:45 T2 没什么想法，打算先把 Test 8/9 的 $O(m^3)$ 写了。想了一会儿马上变线性了，但感觉线性就没什么其启发性了。一开始还没注意到 $1$ 必须为根。
17:00 休战。
18:40 搞不懂为什么过不去 Test 8-10，原来是有多测啊。
18:55 发现这个做法能做所有 $k=0$，已经有 70pts 了，感觉这题大有做头啊，先不拼前面的暴力了。
19：16 发现 T3 B 性质似乎很白给啊，交了一发输出 $2^m$，才发现 $1$ 不一定是关键点。
19：30 T3 的 AB 性质都不会，送了 36 分的指数级暴力，这是一定要收下的，不如现在写，一会儿冲 T2 高分。
20：02 调完了，因为调试改的东西忘改回去了，多调了 15 min。
20:26 T2 拿 $k=0$ 的做法改了改，会了一个状态数 $O(m \mathop {Bell}(k))$ 的做法，似乎没什么分。
20：44 等等，为什么我偏要把前面的点一起挂到当前节点上呢？拉一个后面的点把当前点挂上去不好吗？是不是直接就是 $O(mk2^k)$ 的？不过这个做法好像和树结构没任何关系啊，真对吗？但好像记得之前听说过哪道题的树结构是诈骗，是不是就是这道来着，先写了再说。
21：30 休战。
22：30 重新开战。
22：34 写完了，但是只过了 $m\leq 2$ 的点，答案偏小，看来数漏了。
22：50 认命了，想不到做法有什么问题，但看了题解没一个人做法和我一样，可能确实假了，回头仔细研究一下吧。
## 6.27
不知道为什么这么困，模拟赛爆炸了。午休睡满了，还是困。醒来学会了如何拉伸猫头鹰。
$\newcommand\owl[1]{\widehat{\underline{\left(\begin{matrix}\odot_\vee\odot\\[#1px]"\ \wr\ "\end{matrix}\right)}}}
\owl{10}\owl{20}\owl{30}\owl{40}\owl{50}
桂花树调出来了，没假，转移把 popcount 漏了竟然没发现，昨天还是偷懒了，没有输出 dp 数组，今天输出后马上就调出来了。算是第一道我独立切的计数黑题。
感觉我的做法常数有点厉害啊，题解区中提到的卡常我完全没经历。又翻了翻题解区，发现最后面有三篇题解做法其实是和我一样的，那为什么在前面的题解都要引入 “空白点” 这种东西呢？
6.28
模拟赛做破防了，T1 想半天还是没会。没有拼包的欲望了，0+0+0 就 0+0+0 吧。
T1 差个 P3295 [SCOI2016] 萌萌哒，怎么被这种经典题杀了。
6.29
休息日。
6.30
寻逍遥的模拟赛，果然见到了转置原理。
7.1
状态最差的一天。查运势发现今天宜左艾。左艾是什么，sdy 不知道哦。
7.2
发现大问题，我对无向图四元环计数的理解有问题，它不能像三元环计数一样乱定向。
在 lopzith 的帮助下搞到了 K4 计数的板子。
被绿题击杀了。
7.3
AT1202Contest_f K-Medians Clustering
模拟赛 T1，懒得想组合意义，似了。
7.4~7.5
好累。
7.6
回家了。
7.7
UNR，被创死了，喜欢不下发 checker 是吧。
赛后对着数据调很快就调过了。
看明天能不能翻成铜吧，感觉银希望不大。
感觉 UNR 打铁还是太抽象了。
7.8
UNR Day2，T2 和 T3 加起来会不到十分，T1 也不会正解。直接摆了，T1 一开始交了发 9 pts，靠着这 9 pts 竟然还铜了。最终得分 9+0+0。
7.9~7.16
接下来就是正式 NOI 的部分了。、
室友是 PengAo、 sparkle_zh 和 kaixinguo。先见到了 sparkle_zh 的母亲，一眼就认出来了，因为和 sparkle_zh 长得太像了。
食堂有碳酸饮料好评。而且感觉绍兴一中学校各方面硬件都比较好啊，志愿者也很热情。
Day0
开幕式感觉比 APIO 强太多，无论是 dzd 的讲话还是节目。
笔试满了，本来想在试机的时候做一做 NOIP T3 的，结果没带纸笔，猪脑过载了。
发现自己没带徽章，绝望了。不是很想白嫖，但 BJ 的 Cindy_Li 人美心善送我了一个。
当天打了打板子，很早就睡了。
Day1
进场前完全不紧张，甚至异常兴奋。开场前上了个厕所，发现没有水压，冲不动，很无语。
开题，三道传统。看了眼 T1，最短路，感觉应该是可做题啊。思考了五分钟，期间怀疑了多次自己有没有看错题，得到了个点边互换 + 前缀优化建图的做法。记得 linmobi 有场 noip 模拟赛给我们放了类似的东西。又犹豫了一会儿觉得这个做法实在是假不了，所以决定开写了。期间又去了一次厕所，想完了所有的代码细节。写写调调在开场 1h 左右通过了 T1。
观察了下 selfeval，怎么只有 30 次，可能需要精打细算一下。
看 T2 和 T3，感觉 T2 需要投入比较多的时间，T3 貌似也不是完全没分能拿的题。
T2 的操作感觉没少见，但我好像从来没总结过这种操作有什么性质，很后悔。发现通过 >>><<< 的分段能设计出一个三方的 dp，能比较简单的做第一问。想了想做第二问的不重不漏只要处理下连续的 0 段 就行了。
写完第一问过了 selfeval 就去写第二问。发现过不去样例。手玩半天发现怎么还是算重了，于是修啊修啊修。不知不觉就过去了 2h 左右的时间，终于修对了。已经不是铁牌分了。修的过程中发现转移是个二维数点的形式，容易优化。我选择了排序+二分的做法。先拿第二问下手，写完发现最大点跑了 3.5s 左右，此时已经感到有点不妙了。补上第一问之后最大点果然 T 飞了，有 90pts。把最大点的第一问舍弃掉不做就能获得,96 pts。
此时还剩 1h 多一点，上了个厕所定下了先给 T2 卡常再写 T3 暴力的策略。卡常思路比较简单，发现第一问和第二问的排序改一改就可以只做一次。改着改着发现怎么我的 T2 代码备份备的是只做了第二问并且没进行优化的代码。冷静了下打算改变策略，还是保住 96pts 要紧。于是把卡常卡了一半的代码备份了下，疯狂 Ctrl+Z，试图还原 96pts 代码。还原的差不多了交了一发 selfeval，怎么只有 50pts 不到？很多点都寄了。发现我把多测的清空去掉了，补上后松了一口气，再交 selfeval，怎么还是不对？有很多点的第一问挂了。这个时候已经慌得不行了，疯狂对着第三个样例 debug，最后发现 lower_bound 出了些小问题。经历了一些 CE 后在最后 15min 惊险的拿回了 96pts。感觉没时间打 T3 暴力了，100+96+0 认命了。
这告诉我们 Ctrl+Z 的时候不要按太快，不然不一定给你撤销到哪一步。
出场后发现 T1 有一万种简单做法，我还做麻烦了，不过影响不打。遇到了 hz，小心翼翼地问了他成绩，他是 280。我觉得他 Au 稳了。TJ 的 fnoihzhyan，HB 的 wsinb，AH 的 r_shuffle 和我省的 lopzith 好像考得都不太好。wtr2007 有 189，他 T2 差两行就过了。sparkle_zh 241，他倒在 T3 56->80 的路上了。PengAo 173，他的 T2 会了三方后没进行优化。
观察到全国有一车 280、256、236、208 的，但感觉我的分应该还是在银牌线上面的，day2 稳着打就行。
Day1.5
社会实践，在科技馆上了个厕所后掉队了。无奈只能和 HN 的队伍一起走。走到一半终于和 JX 的队伍撞上了，成功归队。lopzith 和 sparkle_zh 在 speedrun，总能提前赶到一些有座椅的地方，等着大部队过来。
下午看电影，有些比较好笑的事故。电影是 《人生大事》，不做评价。感觉看完有助于晚上更好的睡眠，同时也能防止有些选手 Day2 考炸了直接跳了。
晚上看了看 SA，睡了。
Day2
比 Day1 紧张太多了，我也不知道为什么。开场仍然上厕所，这回不是没水压，而是彻底没水了。在极度紧张中点开了题面。发现并没有自己想要的串串题，那就看看 T1 可不可做吧。看了眼感觉是推个简单的判断条件然后拿数据结构维护的题。因为如果不会判断条件连 50pts 都拿不到，所以感觉难点肯定在 DS 部分。初步判断感觉是一定能切的题，D2T1 位置的 DS 能有多难？手玩玩到 0.5h 玩出了充要条件，感觉维护没什么难度啊，需要注意的常数问题。写写调调在 1h30min 时在 selfeval 上拿到了 100pts，最大点跑了 1s 出头，感觉比较稳。
然后就看是紧张了，梦游了 1h 没思考出任何有意义的东西。然后又梦游了 1h 写了半天写完了 T3 的 10pts 暴力。然后又梦游写了个在 T2 能获得 0pts 的暴力。优化了一下优化成了 O(3^{2^n}) ，获得了 8pts。
这个时候不知道为什么终于醒了。发现 T2 直接普及组 dp 就能 O(8^n) ，获得了 16pts。
感觉这东西非常能容斥啊，可以简单做到 O(6^n) ，我感觉能通过 n=10 ，期望得分 24pts。
写完交到 selfeval，怎么还是 16pts，很崩溃。ps:赛后得知其实精细实现试下这个做法就能优化到 O(5^n) 。讲题时还得知了简单的借用高维前缀和思想的 O(n4^n) 做法。
不想管 T2 了，看看 T3 能不能再多拿一点分吧，感觉 T3 复杂度消个 n 能多 25pts 很赚啊。想了想马上会了，dp 下当前最多能用几次技能，这样就不用存到状态里了。然后再求一个技能使用次数下界感觉就没问题了。最后对着第二个样例调啊调，调了 3 个 bug 出来。调完第 2 个 bug 还不对的时候以为做法假了，心都要凉了。最后拿下 35pts，没觉得还能拿什么分，就这么静候结束了。
出来遇到 kaixinguo，得知他 100+100+35,祝贺他守住了 Au。在遇到 sparkle_zh 得知他 95+36+40，那感觉不用焦虑什么了，稳 Ag 但又稳没 Au 的分。从他口中得知了原来 T3 35pts 卡一卡常就能卡到 40pts,担心会不会成为伏笔。赛后开始疑惑自己为什么赛时再梦游以至于 T2 一点分都没推。
pengao 126 非常危险，lopzith 143 没翻成 Ag，wtr2007 126 应该有 Ag。
查分没挂，最终成绩 100+100+96+0+100+16+35=447，rank 154。没有拿到该拿的分数，不过结果是一样的。本来实力就和 Au 想去甚远，可能要再学个两三年吧。虽然过程并不美满，不过结果是好的，毕竟我连稳 Ag 的实力都没有。
pengao 差 6 分 Ag，过于可惜了。其实他大部分方面都比我强的，这回的题目有点克他了。
kaixinguo 615 拿下 Au，没想到在役期间能见证 JX 出 Au。
fnoihzhyan、r_shuffle、wsinb 成绩都不理想，祝他们明年和 whk 加油吧。
小学六年级参加第一次 OI 比赛，拿到了压线 J 组一等。初中三年一点 OI 没学有点后悔，但对我来说也许是件好事？毕竟多训初中三年我也很可能拿不到 Au，收获初中三年的美好 whk 生活也很不错？
感谢我的家长在这两年对我的竭力支持。
祝学弟们明年顺利。感觉明年 JX 的成绩会更好。
怎么上面在随机说话，该去学 whk 了，感觉我对高考还是有点信心的。