NOIP2024游记

· · 生活·游记

Day ?

连续几日在犇犇发

Der mir zeigt wo ich bin

Divano

Sei mein Licht

Ich smöchte mich dir schenken

Noch vor dem Sonnenaufgang

实测对放平心态很有效（大雾）

Day 0

上午看波特思维技巧，全是波特题恐怖如斯，拼尽全力无法战胜。

下午出发前往嘉祥，一路上一直听草东玩第五，感觉现在魔怔了明天就不魔怔了。

晚上先学习多头学长的考前做法去和机房一众人去买了麦当劳来吃叠buff，顺便买了士力架和茶 \pi 和我喜欢的东方树叶，晚上睡觉遇到了神秘枕头一个太矮两个又太高了和神秘冷热叠加被子。

Day 1

6:25 被小度的闹钟叫醒然后洗漱了一下吃了早饭，结果电脑忘餐厅了又回去拿。

进考场前心中默念不要 ad-hoc，实际上确实没有，然后进去之后发现键盘是强行从桌下隔板上拿上来的，线只能从键盘下边穿过感觉糖丸了。

开考先看了一下题，T1 感觉是贪心，T2 是计数，T3 神秘长死了的题面好像是什么边的 dfs 树计数？T4 读完就会两个 \log 的 dsu+二维数点。

感觉有希望啊，准备 1243 了。

T1 仔细想想就直接按 1 的连续段长的为基准贪心？然后贪完就从短的那个开头继续贪，感觉很对呀，10 分钟写完怎么样例一直 RE？结果喝口水发现读入的 char 写的 scanf("%s%s%s%s",s1,s2,t1,t2)，都补个 +1 就能过所有样例了。

T2 重读了一遍发现纯唐题，排个序推个式子就过了，判了一下 corner cases 后过了所有样例此时大概九点多点，优势在我！

T3 读了发现没思路就跳了，重新打磨了 T4 的思路，就是 P7880 的枚举 LCA 找子树内的关键对，发现有用的就是 [L,R,d] 这种三元极大区间，这个东西类似魔法少女网站维护即可，然后剩下的就考虑对询问的贡献，发现一个 [l,r,k] 询问只用查询 L\leq l,R\geq l+k-1 和 L\in []l,r-k+1],R-L+1\geq k 两个矩形的最大 d 即可，光速写完然后过不了样例 2，意识到自己魔法少女网站的那个维护假了不过我注意到不用撤销就直接上并查集了，然后就过了所用样例，我发现稍微剪了剪枝 5e5 大样例本机才 1.2s 然后造了个满二叉树类型的树也只有 1.3s，你能秒我保险起见给 B 写了单独的做法，然后挂了拍子，没有问题此时大概十点半过一点。（之后去 U 群问发现别人单 log 和我效率相当，又看到 251sec 大佬和我做法相同他估的 100 就放心了）

然后后面去 T4 看题解发现能证明关键 [L,R,d] 点数是 O(n) 所以这就是单 log 做法，赢！

开 T3 没有思路，发现链就是 1 然后画了画图发现 k=1 就是 \prod\limits_{i=1}^{n}(deg_{i}-1)!，然后才注意到了每个点周围边的连边是链的形式，于是菊花图就好做了直接去重一下，此时有 40 分。

然后想了一下 k=2 可以容斥写完 12 点多点，这时我意识到正解就是容斥，然后就是一个子集的权值就是 k=1 的答案乘上某条链的一个系数，而且这个边构成的类似虚树的玩意度数 \leq 2。然后我准备写 k\leq 8 验证一下但是经典毛病最后一段时间脑子开始抽一直到最后没写出来，最后只好把四道题扔虚拟机让跑没问题就交了。

最后几分钟怀着忐忑我开始回忆六年 OI 生涯，从小学四年级第一次进机房到初中没能和班主任谈判成功导致没怎么学 OI 到去年 CSP-S 快读没写类型爆零错过一个赛季，六年走马灯在脑袋中闪过，仿若梦将醒。

出场发现 onlycre 过了 T3，问了下他发现 T3 就是直接在容斥基础上 DP，woc 我怎么这么唐这都想不出来？？？

感觉策略没问题，就是 T3 不会正解而且暴力没写完还是可惜了。

最后如果不挂 100+100+56+100，求求你不要挂分吧我什么都会做的。