NOI 2021 游记

7.20

坐火车，路上改了一道北京集训的题

然后开始 dj，直到被家长查水表

到了酒店先去探险了一波，然后直接睡觉

7.21

余姚集训 Day1

T1 两头都分叉的情况忘记分奇偶讨论，100->10

T2T3 直接莫名消失，后来联系教练才找回来

10+40+30=80，被所有人吊起来打

7.22

余姚集训 Day2

预计得分 100+7+0=107

实际得分 0+0+0=0

T2 CE，打开代码发现一堆乱码，具体发生了什么也不是很清楚，依稀的能辨认出 universe.cpp，universe.swf.o 等子串

T1 交互题，调了一下午，发现我的函数第二个参数传进去了负数，又仔细看了一遍交互库的实现，发现它原来会把返回的答案信号当做参数给我传进去？题目里并没有提到会把负数传到函数里，感觉是出题人交互库写挂了

两天集训总分 187，被搞没了 177，认为非常 nb

晚上胡了一下北京集训 day7 的题，Mr_Wu 30min 切掉的题我和 wenhao801 用了两个小时才想出来，感觉药丸

突然接到消息说报道提前，和 801 讨论穿着救生衣去考试以及自然选择等问题

魔方大师 Mr_Wu

在房间激烈地讨论着如何拼出 3 阶魔方的一面

7.23

提前报道

大概是下午到的，看见旁边的人在签名墙上写了个 SSHtxdy!

当年 NOI2020 他 tiger0132 在签名墙上假我，今年必须要假回去

于是在签名墙上写了个 tiger0132 AK IOI，然后挑了个不起眼的地方签上了 Flamire

到了宿舍放下东西就出去随机游走（BNDS 探险队），途中找到了小卖部却没有开门，然后就是看着 saint 爬绳子

回来发现两个室友都在打音游（shh狂喜），刷了会手机出去吃饭了

我的床铺没有电源？？？？

后来爬到室友的上铺去蹭电源了

晚上 vp 了一场 global，只做出来 4 题，比较自闭

然后装了个 pvz，发现连不上手机热点，打了一个小时就熄灯了

7.24

今天啥安排没有/cy

早上起来先打 pvz 打到 10:30，然后看了下昨天的题的题解

感觉 EF 还行，没有到不可做的程度

吃饭的时候发现 saint 把那场的 A~H 全切了，这应该就是实力的差距吧/ll

中午回来得知下午要考笔试，急忙背了一下

根据前人经验，知道了丢密码条扣 5 分，但是……

最后 99，似乎也有好多人这题挂了？

回去了还连不上网，于是继续打 pvz

觉得自己简直太颓了，于是在手机上看了看北京集训 day8 的题，把 T1 胡出来，然后基本就睡觉了

7.25

早上起来应该干的第一件是当然是和 801 聊天！

由于断网+不想写代码，于是胁迫 801 交出一些题目给我口胡，但他并没有给我

于是打了一上午的 pvz，还一命通关了

中午考虑到自己在宿舍太颓了，打算吃完饭去自习室，于是背着包，考虑到雨伞并不能遮住包，于是穿的雨衣

出来了发现雨衣更垃，甚至盖不住裤子，后来索性连雨衣的帽子都不带了

看到自习室里全都是队爷（社恐属性解锁），又滚回宿舍了

口胡了一下 801 上午 vp 的一场 div1，花了 1h 胡完 ABC，不想写，然后不知道在干啥

晚饭吃完了被教练忽悠着去买了一堆零食，后来发现集体理解错意思（这种情况难道不是表达的有问题吗？）

晚上教练空降现场，开始 Day1 动员，发现大家笔试都扣了一分，就 801 AK 了

听 801 讲了一下那场的 D，感觉很离谱

7.26

NOI Day1

教练让 6:30 起，但我仍然是 7:00 起的

收拾好东西去吃饭，然后去报到处领密码条，突然发现没有带胸牌，于是又跑回去拿，然后成为最后一个拿密码条的人，考场里坐 801 旁边

上来先把三道题读了一遍，感觉 T1 最可做

T1 想了一会，尝试了在边上打 tag、点上打 tag 等奇怪想法，发现可以给每个点赋一个时间戳，那么1每次只需要找到和父亲相同的点有多少个即可

然后纠结这个纠结了半天，最后发现可以直接线段树维护，感觉自己是个 sb，想出正解时大概是 9:40，码完正解大概是 10:50，写完对拍大概是 11:40

然后剩下两题开始打暴力

感觉 T2 不太阳间，于是先看的 T3

先打了个显然的 $O(nm)$ 暴力，拿了 16 分的签到分

发现 $m=n-1$ 时是一棵外向树，似乎可以直接分类讨论判断从 $s$ 是否能到达 $t$

写的时候发现题目问的是节点个数而不是能否到达，抢救无果后只剩下 $k=0$ 的部分分，这时大概还剩 40min？

之后就是末日 rush T2，最后 rush 出来了 40pts

最后还尝试抢救了一波 T3 的 $k=1$，但是没有成功

预计得分 $100+40+28=168$，实际得分 $100+40+36=176$，$n\le 1000$ 的点过去了是我没想到的

saint 似乎 AK 了，Mr_Wu 也切了两道题，感觉甚是 nb

801 和我差不多，但他多打了 T3 的 $k=1$

复评完大家都回到了宿舍

教练：回来集合，嘱咐几句，坐了一天了走走也好

讲评听懂了 T3 的主要思想，一些细节可能还要再顺一顺，T2 什么 lgv 引理/行列式 完全不懂

《下一页》

7.27

休息日

上午和室友打 mc

打到下午 13:45 决定去看一眼嘉年华，到了报到处问工作人员说是 14:30 开始

于是带着室友开始在楼里探险

嘉年华扔骰子 9 点，非酋实锤

然后去看飞镖，扔了几个发现都脱靶了，于是弃疗去乒乓球

乒乓球居然要正反面轮换？？？

最后在投壶扔进去两个，获得 14 分

然后回到飞镖，练习的时候出了一系列奇怪的事故，如飞镖卡到墙缝里、在墙上擦出火星，把飞镖尾扔掉等，计分的时候对着 4 的格扔了三四个，光荣 12 分/cy

保龄球受身体限制（其实就是手臂没劲）扔了 8+6=14 个瓶子

回到阴间乒乓球，练了半个小时左右终于达到了有分的线，以后再也不想打乒乓球了

中途还单向面基了万弘和 Froggy

12+14+12+14+14=66，拿了盒榨菜滚蛋了/cy

回来继续电竞，晚上是 Day2 动员，教练说要合理安排时间，但我大概并没有听，导致 Day2 爆炸

7.28

Day2 翻盘了！

把我翻下去了/cy

上来先都看了一遍，感觉 T2 最可做，推了推式子也没推出两个操作到底在干啥，但是发现最后分子和分母是一堆乘积的和，而这些乘积是有规律的，可以 dp，于是开始码

码呀码……

码到了 11:00 还没码完，这时考虑先看一下其他两题有没有能拿的分，结果发现没有，于是滚回来继续写，此时有点慌了

11:40 刚写完， T1 没有多想直接打了个最低档部分分，写了个 bitset

T3 本来还想模拟一下样例解释的容斥，但怎么实现都是 $O(2^nn^3m)$ 的，于是弃疗打了个读题分

期望 20+50+8=78，实际 T1 反向挂出了 4 分，最后 82

晚上看榜应该上 Ag 了

和 801 简单复盘了一下就把机房的希望 801 拉去电竞去了

怎么走桥还能自走虚空的啊

7.29

颁奖

最后我是 99+(100+40+36)+(24+50+8)=357，拿了 Ag，比 801 高了 1 分

本来还想面 tyq 的，结果两个人手机都没电了，导致面基大失败

反思

这次考试总体来说考的还不错 起码比省选好点，但也反映出了我的一些问题

D1T1 能做出来表明我平时的知识点没白学，但线段树维护想了半天没想出来同样也显示出我对一些知识点的熟练度不足，以及还没有习惯一些套路，同时我在这道题上浪费了过多的时间，导致我后面暴力没有写完

D1T2 的正解是 lgv引理 或者 行列式，行列式在大纲里标的是 9，然而我完全不会，所以表明我在知识点上还有一些欠缺，尤其是数学方面，要着重补一下

Mr_Wu：所以 k 小生成树本质上就是@#*&T&#(H*YT*\&EG!*@#*(

Mr_Wu：这么出是不是太裸了？我觉得应该再套个壳？

Flamire：你加个结论或者套个其他算法不就行了？

Mr_Wu：我说的不是那种套，我觉的可以……

(几周之后)

Flamire：你不是要出 k 小生成树的吗？怎么改成 k 小割了？

Mr_Wu：他们思想都是一样的啊？本质上没有什么区别

我做题的时候仅仅是碰运气，并没有发现这些题之间的联系，没有总结出“套路”，没有理解里边的核心思想。每一道题对我来说都是一道新题，与之前做过的题毫不相关，这可能也是有些其他人做的出来的题我却毫无头绪的原因。

除了上述原因，还有一些临场发挥的问题：

1. 想题时，经常会忽略某个限制/把问题改掉/没有考虑全就去写题，这会浪费时间，轻则再读一遍题目就发现问题，重则写完了才发现算法假了。这种现象在这次 Day1 Day2 中均有体现，但在省选 Day2 体现的犹为明显（连续想出 T1T3 的假算法，都是写完了才发现假了），之后应该在写一道题之前先考虑好各种边界情况，认真的读题，把关键的信息记下来
2. 我在比赛中一直将暴力的优先级排的很低，经常把所有题全都想完一遍再去打暴力，并且打暴力的中途有时也会停下来思考能不能拿更高的分以及有没有更好的算法，比如这次的 D2T3，我打完程序的框架以及定义完变量后就把程序放着晾了半个小时，在思考能不能优化自己的容斥做法，导致时间比较紧迫，之后打比赛应当先把能拿的分全部拿到，再去思考有没有更多的能拿到的分

昂对，就这样吧