NOIP2024游记

结果

写了100+100+76+48

没挂

感受

毫无斗志，像个人机，长时间坐牢想不出有意义的东西，有点绝望

感觉略低于大众分，又是一年逆风局

停课

停了和没停差不多，去上了大部分文化课，模拟赛题难度不大，除模拟赛题外基本没怎么训练。

感觉像打卡上班一样，模拟赛，补题，文化课，没什么激情

NOIP

开T1，看起来像是按t_i=0的位置断开每段贪心->一个一个位置贪是不是差不多->把一段的0/1个数贡献在段的开头，然后从前往后一个一个位置贪

不会证，但感觉挺对，快速写完过大样例，用时18min

开T2，一眼秒，用时20min，不太记得为啥用时略有点长了

开T3，看起来是观察结论，然后推一些nb式子，再dp或直接数

然后就开始手玩样例，猜结论，大概用了15\sim 25min发现生成的是二叉树，但没想到有啥用。又用了15\sim 25min发现每个点的所有边肯定是排列成一个链，可以得到k=1的时候就是一堆和读书有关的阶乘，写出来验证了一下。之后往k>1拓展推+写20\sim 35min的O(nk)。

猜测之后是什么换根一类的优化，可能会比较麻烦，先去看T4。

开T4，读完题先想到区间lca是区间dfn最小最大点的lca，但好像没啥用（很蠢的没想到相邻两项lca深度最浅点）

又想了一会没什么思路，看部分分，用刚开始的想法可以做k=r-l+1，想了一会链，转化成长度为k的区间min的max，只会二分+主席树维护连续段。感觉很蠢，但多想了一会也不会别的。

想了半天T3，T4不会什么别的东西

写T3的链和菊花以及T4的O(n^2logn)，链O(nlog^2n)，k=r-l+1,O(nlogn)

发现链跑不过去5e5，但不会卡常

继续想T3和T4，还是没什么进展

造数据验了一下T4 k=r-l+1，写了T1的对拍

此时大概还剩1h，一直都在想T3，T4但没什么想法，纯坐牢

后续

经典赛后上debuff，这次除了以往的头晕还多了嗓子疼