ZJOI2022 游记

LJC00118 · 2022-05-07 09:35:30 · 个人记录

noip t4 数组一不小心只开了 233，喜提 8 分，还好前三题没挂，希望省选能翻盘。

考前一天本打算来机房和同学一起颓废，结果居然有模拟赛？？不过两个小时就写完了（~~原来是信心赛~~），结果一测 295，第一题写挂了一个小地方。

不过好像大家都有不同程度的挂分，只有 xyr 阿克了，被 LJ 告诫场上一定要对拍，希望场上不要 fst。

下午机房一起打德扑，打了一会就跑路了。

晚上看了下板子，发现不会最小树形图的 m log m 做法，口胡了一个还假了，最后到 loj 上找了 Itst 的代码学了个大概，希望场上能写出来。

晚上有点失眠，不知道这个分数还能不能翻进队，打了会星光咖啡馆与死神之蝶，推了两条线后终于睡着了。

脑子有点糊涂，记不清进场前发生什么事了。

进场时发了一个生成 md5 的指南，并不知道要拿来干什么。

今年解压密码是真的长，还好一次打对了。

开考先看了 t1，想了一会发现方案数可以看成每个点能选多少个父亲乘起来，复杂度是 O(n^3) 的，写到一半发现还要容斥，猜了个系数居然过样例了，非常感动，跑了跑 n = 500 好像能进时限，就放一边不管了。

然后看了看 t2, t3 的题意，t3 给出的性质感觉非常奇怪，看着还是 t2 可做。

看了会 t2 发现是特殊性质是最大子段和状物，暴力做法是 O(len^2) 的， len 是串长，感觉非常根号分治。想了会发现不会 polylog 做法，冲了个 n \sqrt n 过了大样例。

测了测极限数据决定把阈值 B 设为 700 ，两部分都只要跑 1s ，然后拿 B = 0, B = 700, B = 200000 互相拍，就去做 t3 了。

画了一会图发现 t3 的性质好像很棒，每个边双里最多只有两个 deg \ge 3 的点，这两个点直接会引出若干条路径，就是个圆方树板子题。

看了下时间还有三个小时，感觉时间充裕，又确认了一下结论正确性就开写了。

大概过了 1.5h 过了大小样例，assert 了下发现大样例居然是仙人掌，这大样例也太弱了。写了个暴力准备拍，但是发现不会 gen 合法的数据，只能手造了几组小样例，拍出了一个错，改掉就过拍了。

大样例要 5.5s，感觉应该能过，就不卡常了。

day1 估分 100 + 100 + 100 = 300。

考完后听说 yzc 240，hhz 300，但是 200+ 的好像不多，感觉今天发挥还行。

晚上学会了最小树形图，颓到 12 点才有睡意。

脑子还是很糊涂，记不清进场前发生什么事了。

看了看三个题，感觉 t1 t3 很可做，决定先开 t1。

t1 看了一会发现 n = 2^k 的情况做 k 轮所有数就都相同了，但是对于任意 n 感觉没有优美的性质，决定去做做 t3。

t3 想了一会感觉会了一个 2log 做法，先写了个 n^2 暴力发现过不去样例，画了一下发现做法假了，修了一下做法又假了，心态直接崩了。

此时过去了 3h，我的得分还是 0 。

冷静了一下决定打暴力。

先修完了 t3 的 n^2 做法，然后去看 t1，拼了个 n = 2^k 和 k \le 10 。

又去看了下 t2，感觉 a \le 4 可以状压，写了一下发现最大的数据要跑 4s，但是这个图是对称的，可以只做一半，卡完就只要 2s 了。

又找了会 a = b = c 的规律，但是完全没有头绪，就去写了下 t1 的矩阵快速幂。

最后 15min 写了 t3 的菊花图，检查了一下文件就结束了。

还能拼更多部分分，但是实在没有时间了，算了下得分甚至没上 100，感觉今天可能翻车了。

day2 估分 30 + 40 + 25 = 95。

出来后问了下同学，好像只有 wwc 和 xyr 上了 100，不挂分说不定也没那么差。

13:00 直播评测，感觉非常刺激。

大概 14:00 测到我，发现 day1 没 fst，居然成为标准分了。

17:30 测到我的 day2，也没 fst，好像进 A 队了，非常感动。

晚上得知 zky 是 rk1，感觉非常 nb。

hzez 进了 5 个，赢麻了！