負け犬にアンコールはいらない - CSP & NOIP 2024 游记（NOIP 部分）

· · 生活·游记

为啥洛谷不能同一篇文章投两个地方。

获得更好的阅读体验。

NOIP

Day -2

联考，都是套路题，但是 T4 犯唐了不会做。

Day -1

据说是信心场，但是 T3 DP 不会做，T4 数据结构被卡常了，打成了一坨，心态爆炸了。

Day 0

摆了一个上午，随便写了点板子，然后又摆了一个下午……

吃完晚饭上车，在车上开了一把 generals，但是由于操作不便被薄纱了，遂关上电脑开始听歌，听着听着睡过去了，醒来刚好放到的尾奏，太爽了。然后又过了一会才到酒店。

这把又是橘子水晶，已经在橘子水晶爆蛋两回了，真该反思为啥老是订这个风水差酒店。

登记完去牢张房间开 Impart，七个人点了顿炸鸡，人均 12R。建议这种活动要多搞！

然后和牢张开了会 MC，到差不多十点就回去了，接着又小摆一会十一点上床睡觉，祈祷明天不会爆蛋。

Day 1

早上起来精神状态良好，早饭喝了杯咖啡。

进考场，感觉位子好像比 CSP 的时候要小。看了圈周围，好像除了我左边第三个的 lcy 没有熟人。

报密码的时候右前方的老哥好像眼镜断了，难蚌，后来知道原来是 BreakPlus。

开题先看 T1，读完题感觉我草怎么这么难，先上个厕所，回来考虑大胆猜想如果从前往后贪心会怎么样，发现直接就是对的，然后开写，调了一会过大样例了，此时过去了四十多分钟，好像花的时间有点久。

然后看 T2，感觉就简单数数题，显然值不重要，然后考虑啥时候不合法，就是存在相邻两个确定的位置可以推导出来结果不一样，算一下方案数再乘起来就做完了。中间系数不小心写错了调了一下，然后过了，大概花了半小时左右？

然后看 T3，感觉有点复杂，看眼 T4，我去传统数据结构题！还是先做下 T3 吧。先考虑 k = 1，发现对于每个点，与其相连的边会形成一条链，然后固定根之后每个点第一个访问的边是确定的，因此方案数就是 \prod_{i = 1}^n (d_i - 1)!，然后显然应该考虑容斥，对于两条关键边都会统计的情况，显然是对于他们之间路径上的边都确定首尾，因此这中间的点贡献会变成 (d_i - 2)!。然后显然有多条边的时候生成的树要有相同的必须满足这些边能串成一条链，因此直接 DP 就可以了。然后就设 dp_{u, 0/1} 表示 u 子树内，链没有 / 有继续延伸时的方案乘上容斥系数的总和，稍微分讨 O(1) 个转移，应该要维护子树内 \prod (d_i - 1)! 的和，然后就做完了。

我一看这不傻逼题，就是情况有点多，祈祷不会写挂。写完小调一下就把大样例都过了，但是跑得有点慢，于是再处理一下 \prod (d_i - 1)! 的逆元把快速幂的 \log 去掉，跑得飞快。算了一下还剩下 2.5h，这下真优势在我了！感觉好像比去年 NOIP 还简单，不会又 AK 一车吧？

做 T4 的时候打了个哈欠，感觉有点困，没道理啊我不是喝了咖啡吗？算了不管还是想想咋做吧。肯定是树分治之类的东西，于是就考虑 dsu on tree，然后就考虑每次新出现的连续段，要成为答案就需要连续段和询问的区间交大于等于 k，感觉不可做，陷入玉玉症。

发现 dsu on tree 不太对劲后尝试考虑区间长度从小到大变化的过程，然后发现对于 k \ge 2，从 [i, i + k - 1], [i + 1, i + k] 合并成 [i, i + k] 时，由于中间有交 [i + 1, i + k - 1]，因此原来两个区间的 LCA 有祖先关系，然后新的 LCA 就是原来两个点较浅的那个，在深度上就是取 \min，于是把问题转化成有一个序列，每次相邻两项取 \min，查询做 k 次后区间 [l, r - k] 的 \max，显然可以二分然后判断是否存在长度大于等于 k 的连续段，那么整体二分或者主席树就随便做到双 \log 了！算了下分，364？好像有点少。

这个时候应该还没过多久，具体啥时间记不清了，但想了一会怎么优化到一 \log，不会做，于是先把双 \log 写了，写完应该还有 1.5h？跑了下大样例，最后一个要 8s，嗯，果然双 \log 什么的还是不可能在 2s 内跑 5\times10^5 吧！

考虑这个东西在笛卡尔树上长啥样，那就是找一个子树大小大于等于 k 的点的权值最大值，但是查询的是区间，所以会裂成若干棵子树和若干个不完整的树，看起来很麻烦。胡了个假做法，忘记是啥了，但是为了保险先把特殊性质 B 拼上，然后保存，然后写到一半发现假了。此时只剩大概 1h 了，开始破防。但题还得做，考虑从前往后扫一遍然后分别求最小值左右两侧的答案，发现还是不可做。

最后半小时多的时候彻底弃疗，回去拍了下 T1，没挂，这是好的，然后默默等待结束。此时的心理预期大概是又有一车人 AK，然后 T4 正解大概和我做法没啥大关系或者我的做法要加上一个比较巧妙的转化。

结束之后马上问 lcy T4 过了没 & 有无 AK，结果他 T4 过了但 T3 没调出来？唉果然还是会有一车人过 T4 吧。

在考场门口碰到了楼阁、张花、Fido_Puppy 和牢张，lcy 说 T4 是变成 O(n\log n) 个区间然后搞搞之类的。啊？支配对啊？咋又是这玩意，咋我又不会做。诶不是等会，你复杂度双 \log 的？啊楼阁你们复杂度也是双 \log 的？不是哥们你们都跑进去了啊？啊？！只有我一个小丑觉得双 \log 过不了啊？！

这下真破防了，原来我离 AK 只差一个常数优化，感觉我只要把整体二分换成主席树或者随便哪里优化一下就铁过了啊！为什么，为什么我不去试一下？到底在想什么？

出来听 cyf 说他是单 \log 的，感觉符合预期，但是问了一圈好像真只有我双 \log 没过。海亮还有个哥三 \log 都过了，真破防。

在出去的路上楼阁问我啥做法，我说我整体二分或主席树，他很问号。稍微给他嘴了一下，他说这玩意能变成笛卡尔树上 n 个区间，然后就是要求区间交大于等于 k，我一听好像不太对劲，问他这玩意咋做，他说直接转化成偏序就做完了。原来我一开始就想到正解然后钦定他不可做了……唐完。

问了一圈，绍一+诸中+海亮+镇海已经 8+ AK 了，看来队线又上 400 了，彻底没救。

唉，为什么从 CSP 到 NOIP，总是差一点，最后彻底沦为小丑。

真的无法接受，在题目完全在我优势区间的情况下，以这种方式输掉。

省选，还能翻盘吗？

破防实录：