NOI2023场外魔怔记

cool_milo · 2023-08-05 16:33:00 · 个人记录

摘要：一篇以魔怔为题的游记并不魔怔，这是否本身也是一种魔怔。

打铜了，很难受。过程很精彩，结局很惨烈。

day -???

联合省选爆炸，在极度悲愤（？）的情况下立下flag：如果我同步赛没Au我就请bot一杯奶茶。

day -??

同步赛没了，变成异步赛。

day -?

UNRD1T1做了4.5h，最后用非标算过了。

day0

做了ARC140D。
确切地说，早上自闭了两个半小时，没自闭出来。
下午打了杭电的多校，目标rk50，最终成绩rk50。属于是属于是了。
晚上继续自闭。于是找秒掉这题的bot要一些奇奇怪怪的提示：

——这题是dp吗？
——是的。
——这题的状态i含义是什么？
——环的长度。

然后继续自闭。
自闭到放学终于想出做法来了。 非常开心的在机房转了三圈。边转圈边喊：好开心好开心好开心……（雾）
奠定了接下来两天魔怔的基调。

day1

小丑选手开始表演。
用10分钟读了一遍题目。
然后想T1，想了15min会了，写了114514下，最后在1h30min的时候调完了，鉴定为菜。
大样例很强，自信不拍。
然后就开始看T2。
看T2。
看T2。
接下来就走上了不归路。
我直接跳过了前面几档部分分，开始看 n = 1, k = 0，因为我觉得前面几档部分分没有启发性，感觉这个题是先对n=1计数，然后再把形成的m个点的树通过某种方式挂回原树上。因为感觉 k \neq 0 很难做，所以我尝试直接对 n = 1, k = 0 设计dp，想了一个小时，居然真被我想出来了。
简单写一下。
注意到 k=0 相当于所有比当前节点点权小的点进入同一棵子树，记 f_n 为大小为 n 的树的方案数，g_n 为大小为 n ，根节点为 1 的树的方案数，然后枚举当前节点是树里的第几个点，写出转移：

这个式子是 m^3 的，然后我思考了半个小时，发现可以交换求和号，然后维护 \sum\frac{(i-x)!}{(j-x)!} ,就可以优化到 m^2，顿时感觉自己走上了正确的道路（没救了），然后就开始想 怎么把构建好的树挂回原树上， 然后想出了一个假做法，然后没有验证样例就开写了，写完还有60min，发现不对劲，急急急拼暴力，写了一个 n,m\leq4，又写了一个 m=0 巨大送分，思考了一会 m=1 的答案发现就是 2n-1 ，这时候才感觉到奇怪，但是已经来不及细想了。赶紧去写 T3 暴力，但是 不知道怎么写，因为 没想起来无向图DFS树没有横叉边，总之写了30min没写出来。爆0了。哈哈。我是消愁。

结束了。

刚结束就听到 bot 、byn和lhx宣称会T2的70分做法，这么牛！bot 还宣称自己会T3 52，但是没调出来，只写了 36，那 bot 不是 200+ 啊，那不是上队线了啊，但是发现队线 210+ ，你说的对，但是 bot 好闪，拜谢 bot。

今天因为太莽寄了，明天要稳一点， Ag 应该还是有的。（flag）

day2

用10分钟读了一遍题目。
然后想T1，想了15min会了，写了114514下，最后在1h30min的时候调完了，鉴定为菜。
（熟悉的剧本）
然后发现大样例 8s+ ，这很不好。仔细一想复杂度不太对，加上一个人类智慧优化就变成了 0.15s，复杂度也对了，直接扔掉。这怎么就2h了
然后看T2 ，一上来就秒了 72pts，然后没有仔细想，直接就看T3去了。感觉不是什么正经题，应该没有正经复杂度，先写了一个DFS还写挂了，然后发现一个点都跑不过去？ 于是往下翻，看到 w_i=1，就开始猜结论一定是二分合并（好像是错的）。造了一个六个1，然拿DFS跑了一遍，拿结论跑了一遍（两个错误代码对拍），发现输出不一样，冷静分析好像磨损值是 2^k-1 ，那就可以状压dp了啊，w_i=1也能做了啊，不知道我在干嘛。
写了 25pts。 这怎么就3h10min了 然后倒回去看T2，完全不慌了好吧（flag * 2），给自己定下 3h30min 开写暴力的下限。

然 后 我 就 会 T 2 了

直 接 裂 开

抱着“如果这个T2冲出来说不定我能上一手day2队线”的想法开写。最后标准结局没调完。SA太久没写写了40min才写对。关键是小样例一个bug都没查出来就给过了你说气不气。

upd:真就是两个很小的问题：我没判询问左边界必须在回文左边界右边，还有一个 n,q 写反了。但是因为后者，我连B性质的16分都挂了。

就结束了。

两天 100 + 40 + 0 + 100 + 0 + 25 喜提Cu。