NOI Online 2022 行记
纪念一下这个 爆炸 的考试
Day 0
晚上考完数学考试就到机房刷题。写了几道状压 DP。没过多久就下课了。然后回寝睡觉。
Day 1
早上起来后看了一下 DP 题,感觉没啥做的,就看了会儿 B 站
然后发现鸽子 Alan Becker 居然更新了。
没过多久就开始考试,提前开网页,题目加载出来后把题面扔在了我们学校的 OI 群里。
首先看了一下 T1
丹钓战,谐音梗扣钱。考场上想不出来正解,就胡乱写了暴力。然后再暴力的基础上优化了一下,预处理了可使
\((a_i, b_i)\)
成为成功的二元组的最近的下标,复杂度优化到了 \(O(n^2)\)。
然后看了一下 T3,感觉考得是多项式之类的题,没学过,就打了一个 \(O(n^3)\) 的暴力走人了。
最后看了 T2,想着用图论搞,就建了一个无向图,写了一个用 bitset 优化的 Floyd 传递闭包,最后用 bitset 检测集合是否互相包含,不包含就输出答案。复杂度大概是 \(O(\frac{n^3}{w})\)。
Day 1.5
下午考入门组,题目简单一点。考试前不想刷题,就看了会儿群。没过多久就开始考试了。
T1 是水题,很快就切掉了。
T2 想了一下,一道比较有意思的数论题,用 \(\gcd\)
乱搞一下就可以了。有点怕中间程序爆精度,就开了
__int128_t
。
T3 感觉是 Trie 或者是 AC
自动机,没学过就没管了。没想到是跟这些没啥关系的 DP 题
后来看了洛谷,真的没想到这次的入门组难度评级是红蓝蓝。。。
Day ???
分数线出来了。提高组 100 分,入门组 140 分。
我的成绩提高组 70,入门组 200。。。