是非成败转头空 —— NOIP2018 游记

$Day\ $懒得算 在煎熬中苟过了初赛。 -------------------- $Day\ 0$ 刚了一波品酒大会，新手村到省选斗兽场的最后一块蓝色总算消失，然后就滚去颓了。 享受了一个下午的欢乐时光，才听说要复习模板题，然而我一道模板都没敲，有点慌。 -------------------- $Day\ 1$ 睡了一觉，猛地发现已经 $Day\ 1$ 了。坐上前往学军的大巴车，陪同一群人毒奶。“今年会考树链剖分、概率期望、$kmp$、网络流。”我奶道。 装着很自信的样子进了考场，考场真的空前地大……这时指导人员喊道：为了防止选手插入 $U$ 盘作弊，$USB$ 接口已经用封条覆盖。一看，我位置上的封条已经松开了是 $smg$……赶紧举手，结果说什么没关系，是手撕掉还是自然松动能够识别出来的。$exm?\ $突然很虚。 于是开包，看题。 由于太弱，无法倒开，直冲 $T1$。等等，这不是原题积木啥的吗？$5min$ 敲完快读啥的秒了这题。 然后 $T2$，最初以为是裴蜀定理，加上我对“网友”这个词表示莫名地恐惧，就顺便把 $T3$ 的题意看了……仔细想了一阵子 $T2$，好像不需要什么高深的东西，排完序敲了个疑似的背包东西一遍过大样例就滚了。 很想敲 $T2$ 的暴力对拍，但感觉暴力比正解还难想……正确性暂时就没去管。 $T3$ 符合二分模型，再看数据范围二分是没逃了。按去年的风格，以为还需要数据结构维护，想了一遍发现并不要，只需要从根结点跑一遍 $dfs$。 一开始认为对于某个节点，贪心一遍把剩下的继承给父亲就 $ok$，没多久就被 $hack$ 了。如果考虑 $O(n)$ 枚举哪段路径继承给父亲还要多一个 $n$ 的复杂度……这才发现似乎有点单调性，马上开敲。复杂度应该是 $O(n\ log^{2}\ n)$ 的。 小样例挺水，躺着过，大样例 $wa$ 了一次，发现犯了 $sb$ 错误——大于小于打反了。改了就过了。 于是为 $T3$ 写了个 $O(n^{2m})$ 的暴力，好像还有个 $log$，但加上剪枝跑得很快，拿去拍了。 苦思冥想 $T2$ 的暴力，乱写了一个哈希，复杂度爆炸。由于 $n$ 大跑不动，具体背包是对的尚不知……只拍了 $n \leqslant 5,\ a_i \leqslant 30$ 的。 这个时候已经过去 $1h$ 多了。 ~~为了向学长致敬，我把两题的对拍左放一个、右放一个，中间打开扫雷。这里想吐槽一下：电脑的声音居然能够外放，搞得我刚打开的时候声音响得一比。~~ 最后 $1h$ 总害怕自己还有什么地方会挂……这儿看看那儿看看，考后还惦记着，发的面包也不想吃。 $Day\ 1$ 预计得分 $100 + 100 + 100 = 300$。场外才发觉人人 $AK$……别再有 $sb$ 错误了，一错包凉……另外听说机子更新了，希望我常数贼大的 $T3$ 能撑住。 一个都没奶中……竟然考三道贪心……~~而且做题少的我不知道最后两题也是原题。~~ 晚上看了一下 $pj$ 的题，虽然能嘴巴出正解，但今年的 $pj$ 题确实比以前难好多。这样一说，明天的 $Day\ 2$ 不知道会难到哪去，更别提码量了。 -------------------- $Day\ 2$ 睡了一觉，猛地发现已经 $Day\ 2$ 了。坐上前往学军的大巴车，陪同一群人毒奶。“今天 $T1$ $kmp$、$T2$ 概率期望、$T3$ 树链剖分。”我奶道。 开包，看题。~~密码居然和昨天猜的差不多，怕不是要被禁赛。~~ 今天的 $T1$ 就没昨天那么显然了，没理睬数据范围想了 $20min$ 的 $O(n\ log\ n)$，之后才发现数据范围这么小，而且 $m$ 竟然要么等于 $n - 1$ 要么等于 $n$，害我想了一大堆特殊情况。于是枚举非割边得到树跑 $dfs$，写了 $15min$ 调了 $5min$ 过了大样例。大样例应该没那么水，就扔了 $T1$ 再也没管。 $T2$ 题意有点乱七八糟，理解了比较久，尽管 $n$ 小到可怜，往状压、容斥想还是没有头绪，我是从斜对角线入手的，但没有考虑边界的一些繁琐的情况，频繁把我自己的想法 $hack$。 理论是无路可走了，果断打表，此时已经过了 $90min$ 了，打出来的表也只有 $n \leqslant 3$ 的时候有点规律，$n > 3$……猜了 $30min$ 的递推式也没猜出，只好拿个 $65$ 走人。 $T3$ 又双叒叕是一棵树，回忆起早上的毒奶，难道真是树链剖分？然而朴素的树链剖分好像不能维护这种东西……慌忙中只得先敲个 $44$ 分的暴力树形 $dp$，过了大样例，之后加了一点剪枝。 当时就想到了，树形 $dp$，多次查询，会不会是动态 $dp$？不少次点进那模板，却无一次愿意去做……尽管大致核心我还是看过的，但考场上 $yy$ 了 $1h$ 还是以失败告终。 只剩 $30min$ 了，面包没心思吃，我必须在 $T2$ 和 $T3$ 中作出一个抉择。 熟悉我的人应该都知道，我是一个心态很差的人，由于 $T2$ 和 $T3$ 双双不会做直接导致我心态爆炸，一时的紧张不可收拾。脑子一热，感觉 $T3$ 的链线段树合并很可做，没多想，直接滚去敲了。当然，实际上留给我的时间不到 $20min$，最后一段时间我还要检查文件。 可惜结果不尽人意，我敲挂了，原因很可笑，由于脑子烫，原本清楚正确题意的我，敲出来的是求最小权独立点集。显然不管怎么查询，结果一定是 $0$。 考后 $1min$ 突然才发现，然而，一切都来不及了，即使早一点发现，也未必调得出来。要是 $Day\ 1$ 的时间补给 $Day\ 2$ 一点多好。 果然啊，$Day\ 1$ 是信心赛，$Day\ 2$ 是……虐心赛。预计得分 $100 + 65 + 44 = 209$。同样，但愿没锅。两天合计**上限** $509$，能稳住就好。出考场时发现大家的神情一致和昨天截然不同……~~刀片预定。~~ 我一直渴望让他人认可我的机会，可惜这次不是了。 再等等吧。 ------------------------- $Day\ $懒得算 神 $tm$ 实际得分就是 $509$ 分，其他地方自测都在 $516$ 到 $522$ 之间的，小老板数据还是挺毒的呢，卡我所有骗分…… 退役了，搬去云南睡厕所了。 ------------------------- $End$