NOI 2021 游记及其相关

ix35 · 2021-06-27 11:45:59 · 个人记录

本篇可能包含如下内容：NOI 游记，算法学习情况，联测（不涉及题目），相关的吐槽，各种奇奇怪怪的图。

NOI，银定了！

将非比赛部分放在比赛游记后方了。

理性看待 ix35 为啥 NOI rp 叠满：

7.6 联测，挂了 100 分。

7.8 联测，挂了 100 分。

UNR D1，挂了至少 95 分。

UNR D2，挂了至少 90 分。

Day 1（7.26）

提要：取得阶段性胜利。

九点开考。

以下时间可能有小偏差。

0 h 0 min：开始看题，一看 T1 感觉是个比较签到的题，但麻烦之处在于码量较大，我决定先把后面的题看完。

0 h 2 min：看到了 T2，k=2 是个显然的行列式，然后发现 A,B 部分分都十分简单，然后思考正解，一开始想到了直接求路径数量对应矩阵的行列式，发现没有处理交叉。

0 h 10 min：看到了 T3，由于 T1,T2 比较简单所以暂时没有仔细思考。

0 h 15 min：发现 T2 那个行列式就是 LGV 引理裸题，所以刚刚的做法直接上就是对的，开始码 T2。

0 h 20 min：工作人员通知 T2 题面有锅，不过我比较确信我读的题是对的，所以继续写。

0 h 40 min：T2 写完调完，过了全部的样例。

0 h 50 min：观察了一下 T3，发现 k=0 以及 k=1 的做法显然。

1 h 0 min：发现自己至少已经可以拿 264 分，思考了一下 T1 的实现后开始写树剖。

1 h 35 min：T1 写完。

2 h 0 min：T1 调完。

2 h 10 min：手玩出了 T3 中 k=1 的所有分类情况，然后开始写。

2 h 50 min：写掉了 T3 的 k=0 情况。

3 h 0 min：写了一下 T3 的 k=1 情况，但是没过样例。

3 h 20 min：经过很多次的修正，将分类全部调对，过了 k=1。

3 h 25 min：发现 k=1 可以用一种虚树来理解，并且可以推广到 k=2。

3 h 40 min：写完 T3。

4 h 0 min：三题测样例和测速完成，发现 T3 有点小卡。

4 h 20 min：给 T3 加了个 O(1) LCA。

然后罚坐了四十分钟。

难度：T2 < T1 < T3

分数：100+100+100=300

题解：

https://www.luogu.com.cn/blog/ix-35/solution-p7735

https://www.luogu.com.cn/blog/ix-35/solution-p7736

https://www.luogu.com.cn/blog/ix-35/solution-p7737

Day 2（7.28）

八点开考。

0 h 10 min：三题都好难耶，今天要拿不到 100 分了。

0 h 20 min：仔细看了一下 T1，还是不会。

0 h 35 min：这 T2 好像只需要用矩阵维护分子分母线性变换，倒着乘就可以了，只有 APPEND 的部分分是送的。

0 h 40 min：好像 T2 只要冲个平衡树就做完了，但是预估了一下大概这题需要 2~3 h，于是先去开可能更简单的 T1。

0 h 50 min：发现 T1 可以随机，每次随机选出 18 位，然后只根据每次选的这些位来匹配相同的字典串。

1 h 5 min：根据一系列的尝试，暂时定为了 40 轮*18 次。

1 h 40 min：写完+调完 T1，上了个厕所后准备搞 T2 平衡树。

4 h 0 min：中间经历了极为痛苦的 2.5h 左右，终于通过了 T2 的所有样例，由于过于痛苦所以我都不想再写一遍我干了些啥。

4 h 30 min：重新审查 T1 复杂度和正确率，发现定在 30 轮*18 位，并且使用循环展开时可以获得较优的时间，以及 10000 次询问大于 90\% 的正确率，于是将轮数改为 30 并进行了循环展开。

4 h 45 min：写了一个 T3 的 O(3^n\times \operatorname{poly}) 暴力，当然我也知道容斥可以得到更多分数，但时间不允许。

难度：T2 < T1 < T3

分数：84+100+12=196

NOI 总分：100+300+196+5=601，勉强进了 rk15，和 djq 同分。

6.27

距离 NOI 报道日还有 4 周。

目前的复习计划基本完成了 网络流，字符串，数数，最大的重点在于 数据结构（毕竟 NOI 年年有数据结构题），次重点在于图论和 线性代数。

主要正在学习 树（链）分治，虚树，K-D Tree，线段树扩展 等，正在计划完成 NOI 2017~2020 的剩余题目。

7.1

BDFZ 联测

预估：240

实际：240（rk 3）

评价：T1 是个水题，T2 是一个叉姐讲过的原题。

T3 暴力输了前两名 10 分，我的做法需要借助一些复杂的数据结构，所以就放弃了那 10 分，结果似乎有简单做法。

7.3

HZEZ 联测

预估：160

实际：160（rk 4）

评价：太困难了，这是什么信心赛。

7.5

CJ 联测

预估：250

实际：230（rk 4）

评价：大分块题被卡常了，少了 20 分，反正 NOI 不会有分块的！

7.6

NFLS 联测

预估：160

实际：60（rk 14）

评价：交互题爆零了，小编十分疑惑。

upd. 交错代码了

7.8

CDQZ 联测

预估：265

实际：150（rk 8）

评价：T2 炸了，一百分拿来祭天，NOI 能不能多点分？

今天 T2 好像有一卡车人爆零了，哈哈。

出了 7.10 的一道题，感觉是人均会做的签到题。

7.10

我的题送分到位。

7.12

BDFZ 联测

预估：190

实际：180（rk 10）

评价：数数场也就图一乐。

蜜雪冰城写错地方了，搞挂了 10 分还行。

7.13

HZEZ 联测

三道原题两道我做过，今天这场还是图一乐。

评测机真 nm 慢。

结果 rk3~7 都是 210，rk8~9 都是 155，我被卡了就从 rk3 变成 rk8。