NOIP2024 游记

Day -？

模拟赛期望标准分只有 305，被同学吊打了。

Day 0

在高速上塞车，真是**的过分！

经典桔子水晶。

没有带电脑，只能自己随机看手机了。

睡的还不错。

Day 1

品尝早饭，但是有一点小感冒，嗓子有点烧。

老大说不要紧张，紧张了容易爆蛋。

进入考场，没有面积到人/fad。

听到密码是 forget#2501 和 memory@2107 总感觉有啥特殊含义，但是想不出来，算了不管了。

Sublime 启动，复制 down 到主目录启动！

先看 T1，好难啊。

想了 O(1) 分钟发现不会做。

哦停停，你是 NOIP T1 是吧，发动技能自信即巅峰，我先把相等匹配最大变成两个 1 匹配最大，然后我直接从左往右贪，每次 1 能匹配就匹配，看上去就非常正确，直接启动！

写完发现小样例都过不去，发现原来是我没有正确预处理每个位置还能用多少个 1，加个后缀和预处理，啪的一下就过了，很快啊，只过了大概 10min。

感觉这个题不知道怎么拍，先扔了在说。

开 T2，我会 DP！是不是把 DP 改成矩乘的形式来个快速幂就好了！速速开始写，先把暴力 DP 写出来，测个样例，过了，再改个矩乘，过了，很快啊！

好像我又有一个 map 又有一个矩乘，感觉 O(m\log n) 有点危，造了个 mkdata 测一下，跑的还挺快，算了不管了。

感觉今年前两题比去年前两题难不少，而我现在还只有 9：30，感觉有点小优势。

发现 T3 题面一坨，T4 很短，而且看上去就是一个可做的 DS，直接先看 T4。

看了一眼部分分，\leq 5000 和 B 是简单的，一条链也是简单的（？？？），那这样就有很多分了。假如我随便编一个能过 10^5 的暴力，这样就是 80 分，然后我在转到 T3，如果 T3 是简单题我就可以搞到 380，这个分就算队线 400 省选也还有救，如果 T3 是困难题我就话多点时间把暴力拼满，搞到大概 350 分左右，这个时候队线大概率不是 400，也还有救，瞬间把自己代入到一个很幽默的乌托邦中了。

想了一会，发现我可以枚举 LCA 的深度，然后我搞一个 dsu on tree，扣出了 n\log n 个关键区间，然后问题就变成了：“给出若干区间，再询问某个区间与给出的区间的交 \geq k 的权值最大区间”，诶，我把他写成 \min(r,r')-\max(l,l')\geq k-1 的形式，然后讨论一下 \min 和 \max 就变成了三维偏序，于是就可以做到 O(n\log^3 n)！

我去，有毛病吧，这个东西能有很多分吗？而且也不是特别好写啊！

诶，我有一招，我把 k 移到左边去，就变成了 \min(r,r')-\max(l,l')+1-k\geq 0，然后在拆 \min 和 \max 的时候把 k 和 l,r 绑在一起，相当于是我钦定了左端点或者右端点往里面所进去 k 个点，这样就变成二维偏序了！

发现在询问区间包含给定区间的时候还是有问题，好幽默啊，而且这些偏序问题 NOIP 纲内真有比较合适的做法吗？感觉自己有点想远了，于是打住。

诶，我还有一招，发现给出的区间有不少长度都很短，而他要和询问的区间交大于等于 k，那他自己长度就得大与等于 k，我直接枚举询问区间中 k 比他自身长度要小的，然后暴力检查合不合法，如果脚造数据的话很能过 10^5，直接启动！

先把 \leq 5000 和 B 性质的暴力写了，然后开始拼 A 性质，诶，A 性质咋做来着？

发现自己刚刚想的 A 性质假掉了，重新理了一下，发现这个东西好想跟我刚刚想的东西等难。

噔 噔 咚……

那不是完蛋了！但是开弓也没有回头路，只能硬着头皮写了。

写完，把性质 B 去掉后测了测样例 3，跑了 2s 多，那不是要死透了！！！！

发现自己维护了一个元素并不多的 set，把他改成 vector，快了不少，只要 0.5s，那应该还有救。

不是哥们，我想了很久的东西最后随机得分，而且浪费了很多时间，那不是完全崩盘了！！！！！

现在大概十一点多，赶紧去看 T3，我去，我怎么 k=1 都不会。

手玩了一下，相当于每个树上的初始点代表了一个是团的点双，那 dfs 在点双内只能是一条链，所以 k=1 相当于是钦定了每个点双内的一个点，剩下乱连，哦那直接把每个点度数减一然后阶乘乘起来就好了。

然后把链和菊花的暴力都拼起来，出题人给了每个点一个样例，好评。

看了一下 k=2，相当于是连个关键边之间的链会受到影响，其他连法都是一样的，那我对这些边的方案数容斥一下，是不是就能做了。

看了一下下面的 k=8，是不是考虑关键边虚树上的边，搞一个 O(n2^k) 的子集反演就好了，那正解是不是把这个幽默的子集反演去掉，搞一个看起来有点阴间的树形 DP，就能把整个题切了？

brbrbrbr，那这个 T3 不成纯纯时间和收益成正比题了，但是我刚刚时间都浪费在了 T4 啊。

感觉开始幽默了，有一点小寄。

尝试拼上 k=2 拯救一下，结果没想明白开始随机拟合样例，最后寄掉了。

100+100+40+?=?

好像大家后两题都过了至少一个，还有过了 T3 写 T4 双 \log 的，有些过了有些没过。

听说海亮有人三 \log 过了 T4，我直接疑了个大惑。

感觉这把有点寄，T4 多过一点也只是寄的不那么透一点。

我的 OI 生涯就是被暴力害了！！！！！

Day ？

复刻了一下 T4 暴力，Luogu 上一条链全没过，但是其他点除了最后一个都过了，我疑惑。

原来一条链是真的 u=i,v=i+1，那没事了，

yundou 上除了 5\times 10^5 都过了，搞了 68。

两个 OJ 并集得分高达 96，太幽默了。

发现 yundou 上 B 性质被过，发现是因为虽然所有询问都跑完了，但还是要空跑一个 dsu on tree 套 set，但是我那个 set 非常丑陋，按照 ODT 的形式写的，导致常数过大，这下分数下界只有 20 分了，希望官方数据别寄 。