APIO/NOI 2020 断网记

为什么周围都是热点，而我却只有 2G（x

APIO

Day 0

今年 APIO 是在自己学校打，而且 NOI 官网上的规则写了可以访问网络资源，只是不能用别人的代码。

看到之后就问了教练，然后一开始还说要用机房电脑，后来就同意让我们带笔记本用自己的板子了。

然而这个规则和 CF 之类的不一样，虽然可以用板子，但必须是自己写的..想了想我的板子里 debug 那些东西是从 tourist 板子里抄的，而且更重要的是，有一堆 define，又是 grader 题，感觉可能出问题，还有就是 IOI 赛制对板子需求也不是很大。所以最后就没用板子。

但是自己的笔记本还是比机房电脑舒服多了。

Day 1

首先面临的第一个问题就是 CP Editor 怎么测 grader 题..

最后的方法是用 #ifdef OUUAN 把 grader 粘进代码里，其它都好说，就只有 Language Server 不太好搞，直接 include 头文件会报错。

先看 T1，看了一会儿感觉不太会。

然后看 T2，第一眼以为能够 swap 是要双连通，看到树的部分分才发现不对劲。然后又想了几种情况，以为自己会树了，先写了个环，然后去看 T3。

T3，交互题（虽然另外两题也是），几乎是二叉树，询问两点距离，很自然地想到了 Nauuo and Binary Tree，但一看数据范围发现并没有什么用。能不能给一档 n≤5000 的分，我会！ 写了个每次暴力询问直径就跑路了。

然后去看 T2，想到了一个假做法。写了 2h+，过了样例，提交 WA 了。写了个 $O(nm\log)$ 的二分答案，T 了，然后换成了并查集，过了那个 subtask。然后对拍，发现自己漏了两种情况，然后发现自己不会处理这两种情况，就去看 T1 了。

发现 T1 比我第一眼看到的貌似简单一些，先写了 subtask1，然后写了个 $O(nm)$，然后看着 $\sum f(i)^2 \le 4\cdot 10^5$ 的限制一直以为复杂度里带一个 $\sum f(i)^2$，就没想到正解。然后去把 T2 的菊花图写了。

最后 30min 在想 T3 的完全二叉树 subtask，写了个假做法，考试结束了。

出考场后听说 $\sum f(i)^2$ 的限制是用来限制 $f(i) \le \sqrt{4\cdot 10^5}$，自己想了下就会做了。

听说 T2 我考虑的那一堆情况合并起来就是 $x$ 和 $y$ 所在连通块不是一条链，自己想了下也会做了。

下午去 给 CP Editor 加了一些适用于 grader 题的 feature。

NOI

前篇：NIO9102 落雨大。

Day -1

早上坐一小时高铁到了长沙。

可能是因为到的比较早，一路都有摄影跟着 🌚

可能也是因为到的比较早，并且签完名会被拍照，签名墙上只有大家的姓名和 ID，没有任何奇奇怪怪的话（

去年 WC 的时候还能开玩笑地写下 <font color="gray">ouuan</font>，今年已经没心情写这种东西了。不想写姓名，ID 也不像 vfleaking 那么炫酷，就没签。

寝室虽然环境比广二好，可是：

1. 没有广二那个超适合坐在上面的梯子（
2. 不仅没有桌子也没有梯子，床的边上还有一圈凸出来的，空床完全没法坐边上，只能坐在用来睡的床上（有床垫，和凸出来的那一圈差不多高）。
3. 信号和广二一样差。

最赞的一点，大概是插座不像广二那样藏在床底。（但据群友们说，有的寝室只有一个插座。我的寝室是每个床一个插座。）

到寝室之后以及下午写了写游记。

听说有自习室，就去了，然而很困 💤，几乎啥也没干。稍微面基了一些人，然而并没有面基到（指见到且知道对方 ID）以前没面基过的人。

晚上见到了 @AprilGrimoiore 和 @ruogu，然后就开始了关于 Arch Linux 的交流，以及我教 @AprilGrimoiore 用 git。

最后走的时候 @AprilGrimoiore 把胸牌落在了自习室，让我第二天给他。

Day 0

早上吃完饭先去了自习室。

想把胸牌给 @AprilGrimoiore 的时候听说他发烧去医院了 /jk 希望胸牌没事希望人没事 🙏

不知道为什么，我在开阔的操场上以及开幕式的会场都没有信号 /yun

开幕式先放了在 WC 看过好多次的 3M 原则宣传片，然后放了一年前就在广二看过的长沙一中宣传片。

今年不用喊口号。感觉认识的人比去年少 /fad 同省都有一堆不认识的。倒也和 2020 年没有出去集训过有关。

dzd 演讲依然非常精彩，得到的掌声也依然是其他人的好几倍。当场公布了新规：有剩饭会扣 1 分。

今年也有花式开幕，是一个 扫描线 发光的电扇一样的东西，可以显示动画。

开幕式结束后去自习室把 APIO 的 T2 写了。

下午听说发烧了有隔离考场 /fad 把胸牌由工作人员转交给了 @AprilGrimoiore。

这次的赛场和广二一样是由一个像是体育馆/报告厅一样的地方改造的。不知道再之前几届怎么样，我感觉这种赛场比机房舒服多了。

今年笔试有好几道题库里没有的题，包括：（题面和答案都是印象中的大意）

1. 程序在某个测试点运行时使用的内存超过了内存限制会怎么样？

   不能正常运行，该测试点获得 0 分。

2. 机试时忘记了用户名和密码，找工作人员求助，扣几分？

   5分

3. 哪些行为是禁止的？

   （多选，选项之一）在监考人员宣布 NOI 机试开始之前，禁止触摸键盘鼠标等外设。

只不过还是顺利 AC 了。

看练习赛题目，发现有 C++11。王宏宣布考试时编译选项和练习赛一样时，全场掌声雷动（

练习赛题目是去年的 D1T2, D1T3, D2T3，暗示 今年没有简单题 今年有交互。

并没有写题，和 lk 还有 @rushcheyo 闲聊了一会儿就去自习室了。

Day 1

半夜醒了 1h 还流了鼻血，只不过睡得比较早所以问题不大。

看到 T1 后大概几分钟就会做了。

看到 T2 后大概几分钟就会 40 分了。又想了一会儿，发现除了 40 分啥都不会。

看到 T3 后大概几分钟就发现区间逆序对是部分分（A），后面还有一个特殊性质（C）可做，暴力应该也没问题。

然后开始写 T1，写了 1h 过了样例。测了个极限数据发现要 2s，然后把矩乘的 for 循环顺序换了一下就 1.5s 了，感觉很神奇。

然后开始写 T2 40 分，写了 1h 过了样例。感觉瓶颈上没有任何可以卡常的地方，就没测极限数据。

然后开始写 T3 暴力，想了两分钟 $O(n^2\log)$ 怎么做，发现自己是 sb，直接二维前缀和就可以 $O(n^2+nm)$。然后想了下另外一档特殊性质（B），感觉好像不太可做。写了 2h，三档分都过了样例。A 的样例不是极限数据，但只跑了 0.3s，感觉应该没问题。C 测了下极限数据，感觉没问题。C 没有合适的样例，就手造了组数据，发现暴力 T 了，然后发现暴力不小心写成了 $O(n^2m)$，赶紧改过来。

这个时候只剩 0.5h 了，感觉没啥可做的了，就去写 T1 对拍。然后对拍挂了好多次，每次都发现数据不合法。最后不到 10min 的时候在看起来好像合法的数据上拍出来了，但是没时间了，非常自闭地考试结束了。

今年可以多人同时上厕所。要不是这样的话不知道要排多久的队。

看成绩，矩阵乘向量的 i 和 j 写反了，192 -> 112。（仔细分析后意识到，本质上是，我根据边建出来的那个矩阵适用于横向量乘矩阵，而我矩阵乘向量的时候写的是矩阵乘竖向量。由于题目求的是一个环，这样写可以通过 $k=0$ 的数据。）（其实只要写矩阵乘向量的时候想着“$A_{u, v}$ 表示从 $u$ 到 $v$ 的边”就不会有事，但我当时愣是去套普通的矩阵乘法，结果就写反了。）

听讲题，T1 没啥意外自己写的就是标算，T2 听说正解和容斥几乎无关之后就没仔细听了，T3 很神仙，听完只记得用梯度下降法造数据卡莫队。

看到成绩分布时，发现就算没挂分也很不会太靠前，有种输得心服口服的感觉。毕竟也没抱太大的进队的希望，但如果是因为挂分而退役还是挺难受的。这么想很蠢吧，知道自己排名不前反而放下心来。

Day 2

虽然 T2 这个题面很长，对话的形式读起来还是很舒服的，非常巧妙地把形式化定义和易于理解的说明结合在了一起。（另外 X1, X2 和 X3 是 OI Diary 的角色，之前我只看过 「萌新的随想文坑」OI Diary Beta，还不知道 X1 和 X3，后来才知道。）

依次读完三题，发现一题都不会，暴力也不太会。

不如来写贪心吧！于是写了个 T1 的贪心：每次把最小和最大的合并。发现没过样例。换成了每次把最小的和最小的可以合并的合并，发现过了大多数样例，只有几个没过。之前看到数据范围时我就有注意到 $m\ge n-1$ 有很多分，再一看，我没过的都是 $m=n-2$ 的。于是大胆猜想这个东西在 $m\ge n-1$ 时是对的。写了个暴力简单拍了一下，发现 $m\ge n-1$ 确实拍不出来。手玩了一些拍出来的 $m=n-2$，又想了几个贪心，全假了。这个时候已经 2h 多了，把几个贪心和暴力拼在一起就没管了。

然后再去看了下 T2，突然感觉自己会做，写了之后没过样例，再仔细一看，只有叶子能长东西，我看成了每个点都能长东西..然后尝试着写了下特殊性质 4，发现并没有合适的样例（也可能是一个样例里有若干组满足特殊性质 4 的，反正我看开头不满足就没看了…），于是手捏了一个样例过掉了。并不会写暴力，于是很难受，只能当它是对的（

然后再看 T3，暴力完全没思路，只好看特殊性质。大力猜想一波性质 A 可以去掉割边跑最短路，过了大样例，然后把判割边去掉，发现也过了大样例…但我也不会暴力，只能当它是对的（

再看 T3 的性质 B，一开始想了个 DP，写完之后才发现完全不对..再仔细想了一下，发现看起来貌似是没有隔 2 边的间隔把整条链分成了若干段，每一段貌似选一条隔 2 边就行，又貌似必须在交接处选 /yun 不是很懂，但有大样例，于是写了一下，发现答案很接近每一段的最小值之和，然后又加加减减凑了一会儿，最后在 12:57 的时候把样例凑出来了。

看成绩 & 复评咕了。等的时候又想了下 T3 的性质 B，发现 $n=3$ 就能 hack 掉我。然后再仔细回想了一下：我最后凑出来的答案是每一段的最小值加上 $n-1$ 减去段数，在调试过程中，我有试过最后一段是不是不计入答案，发现把最后一段去掉后答案几乎没有影响；当时我也没有多想，因为已经 12:50+ 了，当时我离答案还差好几万，都没注意到个位数的差别；在调试过程中，我有输出过一个值，这个值我见过它有两次相差了 $3$；而在 12:57 时，我把输出凑到了比答案小 2，然后我就直接加了 2。综上考虑，再在几个小的例子上测了一下，我几乎确信了把加二改成加上最后一段的最小值再减一是正解。在边权范围是 $1$ 到 $10^9$ 的情况下，样例中竟然有边权为 $3$ 的边，还恰好位于最后一段 /yun

16:40 左右终于不咕了，$45+40+25=110$。T1 没有意外（然而貌似好多人都意外获得了很多分），T2 莫名过了 15 和 16 两个没有特殊性质的点，T3 的性质 B 过了一个点。把 T3 按上一段说的改过来，果然过了性质 B。

听讲题，发现 T1 很可做。

T3：《丢失密码条，puts("-1") 就好了》。听说性质 A 直接判最短路是否合法就行 /fad 只不过判是否合法貌似也不比把割边找出来简单多少（

听说 C++11 是为了 T2 的 unordered_set 开的。（多谢出题人）（不会明年就没了吧）

出榜了，在银牌线到队线减 100（意思就是没挂分也进不了队）之间。

Day 3

听论文答辩，感觉 zrf 非常稳，jmr 有点悬。然而不知道是不是分差比较大，排名也是 3 和 5，并没有像去年那样影响到最终的结果。

闭幕式就如往年那样进行，只是我不会再看第二次余姚中学的宣传片，无法明年再会了。

我双色 NOI 的第二色，是银白色的。