遗憾总是主旋律

· · 生活·游记

生涯最后一个赛季（虽然是打着玩），思来想去还是决定写个游记。

初赛

因为下午要考初赛，所以上午就只做了语文作业。初赛具体过程记不清了，只记得监考员是初中生活老师。大致一个小时做完之后就开始睡觉 or 焦虑自己糟糕的文化课，虽然前面还有几道不确定的，但是知道肯定能过也就没去检查。

估分：90+

实际得分：91.5

CSP-S

本来想上午请假在家睡懒觉的，但是一群jjn都说要上课，没办法只能来昏昏沉沉地上个课。考场就在 5 号机房，下午进考场的时候还差点迟到，但是好在在开考之前把缺省源写完了。

开题一开始被 T1 吓到了，感觉贪心有点伪，应该要上 DP。又想了一下发现只需要排个序再反悔一遍就行了，写写写，25min 过了 T1。看 T2，第一眼依旧没什么思路，吃了口巧克力发现了 k \leq 10，但是算了一下 O(2^km\alpha(n)) 是 10^9 级别的，感觉即使是 Ultra9 的评测机也跑不过。又观察了一下发现 m 条边中只有 n-1 条是有用的，可以将其预处理出来只遍历这些边，开写之后还发现了个小优化：每次只取 lowbit，时间复杂度就可以降至 O(2^kn\alpha(n))。大概 100min 的时候过了 T2，极限数据 1.1s。

这时我打算上个厕所再回来开 T3，出去还在楼梯口隐约听见了班主任讲作文的声音，心中不禁泛起“我已经是一个无能的常规生了，高考才是我的归宿”这样的感慨。读完 T3 题面，光速发现了每对串都是形如 XAY/XBY 的形状，于是我仅用了 10^{-998244353} 秒就想出了拼接成 X?AB?Y 用 AC 自动机跑多模匹配的做法。然而我身为退役选手，显然是不会写这么高级的算法的，于是我开始想仅用 trie/hash 的做法。就在 17:20 的下课铃响起之时，一种极其诡异的想法在我脑海中迸发出来——倒着对前缀建一棵 trie，每个终止节点再对后缀正着建一棵 trie，再用 hash 判中间段，查询的时候就查两颗 trie 上都是它祖先且中间段相同的有多少个，时间 O((n+L)\log L)，空间 O(L) 个 map（可以优化，但我不会）。然后就是经典情节，全力开冲正解未打一分暴力，到最后 15min 写完发现小样例都过不了。最后的一点时间我也放弃了调试，转而想道：如果我赛前加训了，肯定能轻松 300+……如果不退役明年是不是还有可能有省队……

出来以后得知gjy四题不会，2jczoo&不会 T2，稍稍让我有了些许安慰，但是 SZZ AK CSP。

估分：100+100+0+0

实际得分：100+100+0+0

NOIP

请了一天的假来考 NOIP，本来说好下午都不回去上课，结果 Creeper_l 这个 JJN 回去了。

在嘉祥外面找了个酒店住，睡得挺好的（比CW寝室好1e18倍，RP++）。早上随便吃了碗米线就进去了，路上还遇见了SZZ（RP+= \infin ）。到考场发现gjy就在不远的座位，但是不知为何这次不让开考前写代码。想着切一题就是赢，两题就赢麻了。

开考，看 T1 又是一眼不会，想了 5min 会了，手快 15min 左右写完了。这时我有点懵逼，去年 T1 是蓝（区分题），莫非今年很简单？全然没有意识到是 NOIP=NOI Plus。开 T2，感觉完全没有思路啊，急急急。想了约 30min 发现了个关键结论：不合法等价于存在一个三元组满足 a>b+c,b>\frac{a}{2} 且 wb=wc=1,wa=2。但是还是不会处理，觉得要容斥。然而经过了一段长时间的思考、走神、挣扎之后不知道怎么就突然会了：枚举第一个买不起的 a，再枚举满足条件的 b，而对于一个确定的 b，c 可以取的是一段前缀，这样统计显然是不重不漏的。写完一测样例2不对，反复调发现刚好剩 0 元钱时是不劣的，以及要判 b\ne a。11:15 过了所有大样例。

满怀信心开 T3 和 T4，然后又茫然无措地放弃。T3 是我 OI 生涯最讨厌的 mex，T4 是高深莫测的神奇数据结构，于是只打了一点比较简单的暴力。最后5min的时候想到了一个 T3 看上去正确性很高的 DP 但是也没写。

出来问了gjy没过T2。感觉难度应该是黄蓝紫黑，结果怎么上洛谷一看是黄紫黑黑，这下真成 NOI Plus 了。不过我这种退役选手真的能切紫吗？

预计得分：100 + 100 + 8 + [15,25]