NOI2021线上同步赛游记

Mr_HY43205 · 2021-07-28 20:28:12 · 个人记录

这波，这波是台风天看€€£出锅

Day0

稍微复习了下板子，准备准备比赛。

当然现实是基本打不来多少板子

上次战绩：NOI2020 线上赛爆零

（当时打了半天暴力交上去期待有点分，然后出来发现爆零了，又过了两三个月才发现自己都不知道文件输入输出是什么

Day1

早上非常激动地开机，发现同步赛变成了延迟赛，一路等到 10 点才等到网址。

登进去后发现我要三天后才能下载下来题？所幸从别的地方找来了 pdf 才基本上正常开始比赛。

开题先把三道题过了一遍，计划 T1 多拿点分，然后 T2T3 冲着暴力分去。

T1 先想了把模拟，发现居然能过 20 分，然后又去想后面的部分分，本来想把 A 和 B 两个特殊性质都拿了，但搞了一会儿发现只会用线段树把 A 写了。

于是就写了模拟和线段树两段程序，加起来 200 多行，写完一看人傻了。还好写得都挺对，没怎么调就交上去了。

然后还剩两个小时开 T2T3。

T2 估摸一下应该有挺多性质可以搞，奈何没安排什么时间，于是先搞了个全排列统计逆序对捞了 20 分，然后去打 T3。

T3 看上去内容也挺多，想想还是先把暴力分拿了，写了个 Floyd 又捞了 16 分。

考完估分：50+20+16=86

结束以后听说 T1 是原题，用 LCT

T2 是原题，用 LGV 引理

T3 用虚树

稍微看了看自己的考试情况，发现整场考试写了一个模拟，一个线段树，一个全排列，一个 Floyd

笑死，普及组选手勇敢挑战 NOI

不过三道题两道原题这是？

虽然我说今年 NOI 会很水，但我指的是台风降雨多啊，没说要出原题啊？

洛谷数据：50+20+16=86 谢天谢地没挂分，相比去年已经进步了 \infty 倍了。

Day1.5

研究研究昨天 T1，笑死，根本不用 LCT，一个树剖搞定了

于是稍微把树剖捡一捡，切了这题，又写了篇题解

看到之前的 NOI 好像考过一些交互题和提交答案题诶？

然后发现自己非传统题见都没见过，于是看了看非传统题，额怎么全是黑题

Day2

本来看到官网上说 8:30 考到 13:30 还挺高兴，然后又被鸽了……

还好题目下载挺快，不用等到三天后

开题，照例先把三题看一看：T1 通信？啊不是通信题

T2 看上去还能想到挺多东西。

T3 计数，组合，容斥之类的，算了就打个暴力吧。

于是先看 T1，模拟要 O(256mn)。这种操作不用二进制数好不爽啊，于是想到了把 256 位字符串拆成 8 个 32 位二进制数，直接降到 O(mnk)，估计应该能跑 20 分。

然后看看 T2 还能打个不少分，性质和规律也挺多，就先把 T3 暴力打了。

T3 的暴力打完大概有 8 分。

T2 的 20 分暴力显然可做，跑个 O(n^2) 就够过了。然后先看性质 A，举了点例子发现就是个斐波那契数列，于是又 +15 分。之后再研究性质 BC，搞了半天发现没推出来，离考试时间还剩十五分钟，就放弃去检查代码了。

检查的时候发现可能能捞到性质 A 的部分分，就推了个组合数+快速幂又捞了 12 分。打完以后发现这个部分分做法是假的，12 分并没有捞到，但也没啥副作用，也就不改了交上去。

考完估分：20+35+8=63

等了半天洛谷出数据，然后测出来 24+30+12=66，还挂了 -3 分。

T1 的暴力跑得比较快，大概多挤进去了 4 分；T2 是性质 A 里面的边界算错了，挂了 5 分；T3看了半天，发现居然是那个假的算法多拿了 4 分，而且还不是性质 A 的测试点。这波，这波是歪打正着？

两天总分 152 分，不知道什么水平

在洛谷上看到正式赛选手的成绩，发现我在打铁第一名和打铜最后一名线上……？

总之这把 NOI2021 线上赛就这样了，之后继续努力吧！

这把打了个铜，没打铁，好耶