NOIP2024 游记

别挂分了吧哥哥。

注意：这篇游记中没有 Day0。

Day -1 指考前一天，即 11 月 29 日，Day 1 指 11 月 30 日。

Day -3

这一天是最后一场正式的模拟赛。

早上 7 点半开始看题，先看了一下题目类型，前两题是构造，感觉优势在我，后两题一个串串一个计数。

先看 T1，想了一会，发现自己不会，怎么办怎么办怎么办。

想到一个好主意，我们来倒开吧！

看完 T4 发现有一个容斥做法，然后发现 n 是 5000，然后直接跑树上背包就好了，半个小时拿下。

秉承着倒开的信念，接着看 T3。

T3 是串串题，但是看起来只需要一些简单的字符串算法就能过掉。

想了好久怎么枚举然后胡出来一个 Z 函数做法，然后又写了好久发现过了大样例，只用了不到两个小时。

剩下两个小时做 T1T2 两个构造，优势在我！

然后没有悬念的，我做了两个小时之后 T1T2 都没做出来（什么鬼？）

最后发现我还是 rk1 因为大家都在正开，虽然 T1 过了一车人但是没人发现 T3T4 傻逼题。

下午在补题，发现上午没做出来 T1T2 很脑瘫。

晚上发现 LA 群里有人在玩你画我猜，于是加入一起玩。

Day -2

上午教练又给拉了一场考前信心赛，说是每一题都是模拟赛 T1（所以是哪次的 T1）难度。

开题发现拉了 4 个往年的 CSP-J T4，我就没打（逃

下午他们一车人说要 vp cf 的 gym。

（一摩托车人也是一车人，一印度摩托车人也是一摩托车人）

然后大部分人在过了两题之后因为各种神秘脑瘫原因卡题了。

依然坚挺的 可乐猫 通过了 4 题！

其实过了没多久大家都不想打了，然后下午就全去玩你画我猜了（？）

晚上好像也一直是你画我猜。

Day -1

我好像啥也没干。

今天没有晚自习！

晚上在家玩 Celeste 一个叫 Oblivion 的图

过了三面之后 room4 打不过，遂跑比。

Day 1

提前 45min 到达考场，然后发现大家都进去了。

哎不是提前 45min 到吗怎么变成一个小时了。

进去之后把我的快读板子打好，然后等他发题面。

下发题面之后后面三个题都扫一遍，T2 没看懂，T3 没看懂，T4 好像题意很简洁。

然后看 T1，本来以为是超水题，然后准备写了发现，输入居然不是 t 而是 t_1,t_2。

想了一会，发现好像还是水，似乎只需要一个像是双指针的东西。

写了一下过了小样例，测了一下大样例发现挂飞了。

这个时候大概是 8:50，已经开始慌了。

仔细想了一下，发现似乎有一车情况，而且我写的东西似乎没法改，更慌了。

又想了一会，发现我的做法加一个 min 就很对了（

改了改，发现过了大样例。

然后想了好久，确认了好几遍，感觉我的做法非常正确。

这个时候大概是 8:55。

看 T2，看了一会发现似乎比 T1 水一点。

首先能发现段与段是独立的，所以只需要分别算出方案数然后乘起来。

假如上一个位置是 i，下一个位置是 j，令 x=j-i。

那么中间那一坨方案数应该是 v^{2x}-v^{x-1}(v-1)。直接快速幂搞定。

注意了 v\times v 要取模的情况，赢！

发现通过了大样例，这个时候大概 9:20。

然后看 T3，看了一小会终于看懂求的是啥。

首先能看出来，一个点连接的所有边，最后应该 dfs 树上串成了一条链，并且，起点那个方向的那条边应该是必须是链的一头。

推出了 k=1 的方案数是 \prod (deg_i-1)!，赢！好吧这好像没什么可以开心的

秉着从部分分看起的想法，我成功想出了链和菊花。

然后歪歪出来一个做法，我们首先拿一个关键边旁边的两个点当根。

然后按深度从小到大的顺序加入每一条边，并且加入的时候统计新出现的方案数。

我实在是太聪明了！（你聪明个蛋啊喂）

准备开始写的时候发现有蹊跷，因为我这个玩意他可能确实错完了。

然后我去想了一会T4，具体描写在下面。

（这里中间应当有一次上厕所但我忘了我啥时候去的了）

想了一会我自己觉得没什么问题（？），然后就开始写。

写完之后小样例过了，然后 k=2 没过去，去测链，发现链也过不去。

愤怒的接着调，调了 n 年以后调过了 k\le 2 和菊花和链，56 分看起来比较赢，这个时候是 11:00 左右。

然后自己随便瞎弄出来一个会挂的 k=4，然后发现我少写了一车情况，而且这玩意不像是我的做法能改掉的。

此时我感觉到了深深的无助，回想起了今年 NOI Day2 场上高贵的 95+0+0，当时似乎也是这么个情况，觉得自己可能这下真得退役了。

然后我把这份代码存了起来（毕竟这也有 56 分），打算重新想 T3。

首先看见一个 k\le 8 的点，所以去想容斥。

发现如果一个方案可以以多条关键边作为起点，那么他们一定在一条路径上。

然后这个路径的方案数似乎是好算的？

然后我感觉我突然会了，仔细思考感觉很对。

写完之后调了一阵容斥系数就过了大样例，此时 11:30，兴奋到爆炸，感觉不用退役了。

然后是 T4，下面这部分是我在想出 T3 之前想到的东西：

T3 感觉有点问题，先看一眼 T4。

首先 k=1 就是找区间内深度最浅的点，k=r-l+1 就是区间所有点的 lca，这个也好算。

然后看链，发现并没有太多思路。

考虑一个点什么条件下可能能作为一个询问的答案。

假设这个点是 u，那么关注这个点 u 与他的子树内点形成的连续段。

在链上的时候，此时总共能找出来 n 个关键的区间。

那么询问相当于在所有找出的区间里面，找和他交 \ge k 的区间里面，点深度最大的那个。

好像拆拆拆成 4 个情况以后分别跑三维偏序就好了。

这样得到了一个链上的 O(n\log ^2n) 做法。

放到树上，上面找区间的过程使用启发式合并代替，这样区间个数是 O(n\log n) 个。

所以最后得到了一个 O(n\log^3n) 做法。屁用没有啊哥哥

然后我发现这是一道 DS 题。是不是发现的有点晚

但是感觉我离正解似乎有点远，所以又回去看 T3 了。

过了 T3 之后：

看到之前推出来的三老哥做法我就头大，这玩意能过就鬼了。

这个数据范围看起来似乎是给一老哥留的。

首先想了一会，发现之前跑启发式合并的过程，似乎相当于初始有 n 个小区间。

那么有效的合并应该只有 n 次？？？也就是区间个数应该最多只有 2n-1 个。

好，我得到了一个树上的双 O(n\log^2n) 做法。

接下来似乎只需要优化掉那个三维偏序。

假设询问的是区间 [L,R]，树上薅出来的是区间 [l,r]，考虑他们什么时候满足条件。

不难发现，此时只有 4 种情况：

$[l,L,r,R]$，想了一会发现也好处理，只需要 $r\ge L+k-1$ 就能满足 $k$ 的限制，额外要求 $l\le L$ 就好。 $[L,l,R,r]$，和上面这个一样。 $[L,l,r,R]$，这个想了好久不知道怎么做，因为此时 $l,r,k$ 三个限制都需要满足。 我当时就觉得，我这个应该是能做的，毕竟其他三个三维偏序，都能化成二维的，最后一个没道理不行吧。 想了一会灵光乍现，我只需要让 $l\le R-k+1$ 并且 $r-l+1\ge k$ 就好了。 $r$ 在哪里并不重要，交 $\ge k$ 就够了，这样我就可以把 case34 当成一种情况跑二维偏序。 最后 case12 也是放到一起跑的 $l\le L$ 且 $r\ge L+k-1$。 发现这个二维偏序应该是对的，光速开写。 ~~哎不对你这个启发式合并怎么两个 log 啊，天塌了哥们~~ 后面发现这个启发式合并不需要用 set 跑，用 vector 和数组就行。 12:30 写完+调完过了大样例。 后面就检查了一下代码，freopen，然后一起拉到 linux 虚拟机了重新带文件 IO 测了一遍大样例。 --- 后续的等出分之后再写。 估分 $100+100+100+100=400$。 别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分别挂分。