[游记] HNOI 2022

· · 个人记录

初三观光选手，希望能拿点东西回去。

省选后大概就要回归文化课了，我的未来又是什么样呢。

Day ?

打模拟赛，但是感觉非常迷茫，感觉改完一场下一场还是不会，不知道打模拟赛对自己有啥用。总之感觉自己集训啥都没搞出来。

然后一直摸摸摸摸到了省选前一天。

Day 0

动员大会，感觉非常好玩，并且发现自己只要比第一名高 100pts 就能当 A 队队长，顿时就有了信心。

Day 1

省流：这天脑子非常乱，什么都没想出来。

开场根据压缩包大小猜了一手 数数+ds+???。

8:25 发密码了，这 T1 是出了个模拟？？？打算先看看 T2,T3。T2 确实是数数，T3 题面我喜欢，看起来有个 O(m^2\log m) 的费用流做法，但是稍微思考了一下发现有正环，而且比较难处理的样子。于是准备 2\to 3\to 1。这个时候 20\min 大概也过去了。

8:50，开始思考 T2，主要考虑了怎么去掉值域的影响，想到了枚举最小值然后定义 f(i) 为最小值是 i 的答案，此时寄希望于 f(i) 有部分性质。稍微思考了一下，f(i) 在每段是一个多项式，而且在每段是若干个 上升幂/下降幂/幂 卷起来的状物，发现这可能已经超出我的知识体系范围，再加上误以为 f(i) 是 k 次多项式（在写这篇游记的时候才发现它是 n 次的……），于是决定先跳掉这题，此时得到的只有一个 O(\prod (r_i-l_i+1)) 做法。

9:20，开始思考 T3，但是这题太魔怔了啊，弯弯绕绕半天都在思考怎么去掉正环，然后根本没什么好法子，然后也不知道那个标黑的重要提示是啥意思，然后就发呆了半个小时。期间冲了一个 O(2^mm^2) 的暴力。

10:00，意识到自己已经在后两题花了很多时间，此时得分还十分不理想，决定尝试写写 T1，结果写了 40\min 就过了所有样例，为了防止 FST 还特意盯着题面一个一个字检查了自己是否有实现错误。

11:00，上了个厕所回来，决定冲一冲 T2，然后又乱想了 40\min，啥都没想出来。此时我脑子里甚至没有一个 O(nk) 的暴力。

11:40，看 T3，猛然发现有 20pts 送，冲了一发。然后一直想各种部分分，发现自己一个都不会/fn/fn/fn

12:20，意识到只有不到 1h 的时间了，开始反复横跳，此时 T2 才想了一个不太正常的 O(n^3k) 的东西，写完后加了个前缀和变成了 O(n^2k)，祈祷它能卡过一个包。

然后罚坐了半个小时。

考场估分 [0,100]+20+28=[48,148]。

出来交流了一下发现 T2 40pts 是个极其 naive 的东西，但是考场降智了，可能心理一贯看不起暴力的缘故，写完那个暴力之后竟然没有丝毫优化的念头。忽略对暴力的思考也导致我的思路一直十分混乱。总之白扔了 20pts，长教训了。

Day1 这个分想进的话明天是不是要过两题啊……

upd：T1 民间过了。

Day2

省流：被科技卡了！

进场写了个 data.cpp 和 dp.cpp（对拍），希望能用上。

惯例看包，怎么又有 bracket？？？Day2 也塞了数数？？？

8:25，发密码了，监考把 L 写成 l 了，输错两次之后才进。然后大概思考了下 T1，想到了个寿司晚宴状物，感觉应该有不少分。看了 T2，这 WC 买一送一？？？看 T3 也不太会诶，今天要寄了。

8:50，看了一圈题，决定先写一下 T1，写完大概花了半个小时才过了样例。自信对拍，卧槽这怎么一拍就挂？？？然后思考了下发现自己还有好多好多细节没考虑，心态有点崩。冷静了好久，中途申请上了个厕所，大概又过了一个小时才过拍子。感觉自己写了个复杂度上限 O(\max s_i m2^{14}) 的东西，但是感觉跑不满然后也有挺多分就跳了。预估能跑过 55 分。

10:30，准备看 T2，但是感觉这个暴力也很恶心，准备先开 T3，想着自己会一个 poly 做法就赚了。搞了半天发现它其实就是一堆路径，然后每条边上下经过恰好一次，那是不是可以分类讨论一下然后 DP 啊？想了想 DP 状态大概是 f_{u,i,j} 表示此时在 u 结点的是 i，然后留了条长度为 j 的向下的链。感觉挺对的于是开始写。此时过去了差不多半个小时，然后花大概一个小时讨论全了情况，然后过拍了。此时预估时间和空间复杂度都是 O(n^3)，那是不是卡一卡可能能过 n=1000？于是改成了 dfs 的时候左右儿子各上传一个 DP 数组，调了大概 20\min 过拍了。随了一组 n=1000，0.4s，感觉根据 CCF 的数据湿度很有希望。

12:30，回来看 T1 能不能改改，然后想不到任何可靠做法，发呆了 20min。此时 T2 暴力感觉也写不完了，然后准备拍拍 T1,T3，检查了半天感觉就下考了。因为懒得造数据所以我也不知道 T1 那个玩意能过多少。

出来发现同学把 T1 切了，大受震撼。问了问发现他跟我做法基本一样。我问他怎么合并大素数的情况，他说 FWT。

完全不会 FWT，心态炸了。

那是不是只有 [55,90]+0+[44,64]=[99,154] 啊，感觉两天加起来不到 300，加上自己的垃圾 NOIP 应该进不去了/kk。只能祈祷 CCF 把数据造水点了。

upd:T3 那玩意好像是 O(n^4) 的/px，我造数据的时候深度造小了。

upd:T3 虽然理论 O(n^4) 但是它能稳定通过 n=1000 极限数据，其中一条链的数据光速通过，造了个深度 300 多的树，跑了 500ms 后过了。希望 CCF 放过去（

upd:自测 T1 全 WA 了，不知道为什么。

upd:明白了，预处理 2 的幂数组开小了，考场上疏于造极限数据，这波肯定亏分不少。

实际分数：100+20+28+50+0+60=258。

NOIP：212，标准分：669。