WC2021 兼 SCOI2021 游记

时间好快啊,感觉 SCOI 2020 游记还没写多久就到 2021 年的省选了。

终于,没有了垃圾 SCOI 计算几何。

Day 0

早上看了看字符串板子,该看的板子其实大多都看过了,再复习了一遍 SAM PAM 以及 KMP 之类的,虽然多半也用不上。

下午一直在颓,大概 FC 了个 GOODFORTUNE,希望为明天考试带来好运。

81D9D96FAE0FDEEBAB7B36A979634182.jpg

晚上写了一遍 cdq 分治 NTT 的板子,发现好像这个板子没有以前想的那么难写。

反正感觉能准备的都准备了,实在不行就听天由命了。

Day 1

又是笔记本差评,但是终于不用坐在大堂里面考试,可以到机房里面考了。

写板子的时候刻意在最后加了一句

// memory limit , out of bounds, long long ?

但愿明天出成绩不要出这种问题。。

开场先通读了一下题目,大致想法:

  • T1 看起来很之前模拟赛的某个题
  • T2 看起来很萃老师之前开的某个题,甚至数据范围都很像
  • T3 看起来很经典题,感觉又是前段时间写过的矩阵 bsgs 之类的东西

反正刚开题心态挺好的。先想了想 T1 发现按照之前模拟赛某题的做法复杂度大概是 O(n×as+m2)O(n\times as + m^2)asas 是答案。没细想,先开 T2。

T2 开了后发现真的很类似萃老师之前在 CF 随机开的题。

想了一会感觉套个树 dp 就行了。写了一发,发现过不去大样例,心态有点炸。试了试 #define int long long 发现答案不同,查了很久炸 int 浪费了二十多分钟啥都没查出来。上了个厕所回来造了点小数据发现把自己叉掉了,后来发现是某个地方 OB 了。。终于过了大样例。把大样例的 EE 复制了三份跑了跑发现时间没啥大问题就没管了。

然后想了想 T3 发现直接 bsgs 复杂度可能是 O(mn23logn)O(m\sqrt n 2^3 \log n) 或者不带 log\log 。先写了一发 20pts 。想了想不会其他做法滚去 T1。

T1 想了很久,发现我最多也就只会 O(n3w+m2)O(\frac {n^3} w + m^2) 之类的东西。。但是写起来非常恼火,不知道 bitset 可不可以用那个找第一个元素的东西。于是就自闭了很久,还是想不到什么好做法。

反正就自闭了快两个小时,对着暴力发呆,一直想多会那么一点分但是啥都不会。。

最后花半个多小时莽了一发 T3 的 bsgs ,过了样例发现要跑不动 10510^5 。于是 3kb 写了个寂寞。

最后十五分钟日常检查细节吧。

感觉后大半场就一直自闭。很难受。

果然考试前复习的板子一个也用不上。

如果运气非常好,不挂分,希望有 32 + 100 + 20 = 152 。但是实际上就不知道了。

很可能退役了。感谢陪伴。

Day 2

出成绩居然 tm 从低到高放 PTT 简直就是故意恶心人。。

最后居然 48 + 100 + 20 = 168 ,可能 mn1m \le n-1 的数据比较水,把我放过去了。没有挂题,希望申诉完了能进队。。

\