NOI2020 游记

~~流水账警告~~ ### day -1 在出发的前几天，基本上就只有我和 wyt 会每天到机房自习。但是即使是在机房，看到 Epic 上 fuyuki2002 在线的时候也顿时失去了做 题的动力，然后开始颓废。（ Fuyuki 的用户名叫 BJpers2，BJpers2 的用户名叫 fuyuki2002，很有意思） 到了湖南之后，因为健康码的问题+没找到 CCF 的接机人员，下车后等了 40 分钟才终于坐上前往长沙一中的大巴。然后司机就将我们放到了侧门而不是正门，又花了 15 分钟才找到进学校的路。 没啥买纪念品的心情（和钱），在领完东西之后就直奔宿舍。宿舍里的生活用品一应俱全，我带的牙刷被子洗衣液顿时成了无用的摆设。 完全看不明白寝室的分法，应该是按学校分的，但我们学校却分成了 AAD+ACE 的组合（虽然隔壁外校也没按排名分 晚饭非常丰盛，自助餐甚至还有糕点和饮料，更重要的是大部分的菜都不辣，在长沙一中吃的甚至比在华师一吃的还好。 听说有自习室，迷路了一圈之后终于找到了，但是门上写着啥“试卷分发室”，”国家候选队答辩准备室“之类的话，感觉是啥一进去就会禁赛三年的房间，但实际上就是学生的自习室，甚至有网。 在自习室看到一群神仙在玩 PVZ。复习了俩匹配算法之后，下了一部漫画就差不多到关门的时间了，感觉啥都没干一个晚上就过去了。 回寝室后背笔试，然而大家都在颓？Fz 在空洞骑士，蒋队长似乎在文明？记不太清了。 ### day 0 对开幕式已经没啥印象了，只记得 dzd 说剩饭的话要扣分，然后就是 ”1912 年以来，长沙一中一直培养这样的人“ $\times 4$。会议厅里似乎就我的手机连不上网，只能百无聊赖的看漫画和翻看过去的相册。 下午的笔试顺利过关，中午临时抱佛脚似乎有点成效。试机的题目中有一道交互题，这不是很妙，如果这个题的区分度高一点的话我怕是要暴毙，只能祈祷交互题放在啥 D2T3 的位置，最好再不可做一点。 晚上继续泡在自习室，寝室里 Fz 打游戏太吵了而且坐床上根本不适合学习。 ### day1 长沙一中的寝室其实非常痛苦，尤其是靠门的一号床位。门关不上并且走廊上一直有光，更恐怖的是通往阳台的玻璃门是没有窗帘遮住的，导致我 6:00 就醒了，而昨天晚上又紧张，翻来覆去到 11:30 才睡着，感觉人要没了。 座位在 C100，密码是 pkhwhk（北京好，文化课？）Zeven 和 ustze 就坐在我后面的一排。 8:01 开题，T1 似乎是个矩阵快速幂，但是似乎转移有点麻烦，想了想似乎可以在矩阵乘法时枚举边集，这样做一次倍增的复杂度就是 $O(n^2mw)$，用向量乘矩阵的技巧可以做到总复杂度 $O((n\log T+k)nmw)$，看起来十分诡异，全部数据算出来大概是 2e8，但是至少 有 85pts，于是就写了。1h 的时候调过所有样例，一测极限数据需要 2.2s，但是随机数据只需要 1.7s（极限数据就是将矩阵快速幂时指数上 1 的个数整的非常多）。一边卡常一边思考有没有什么优化的空间，1.5h 还没有什么想法就放弃了。 T2 一眼有一个跟深度相关的暴力可以做，转移是点乘，区间加和前缀清空。于是直接写了个长剖，写到转移部分的时候才发现不对劲，这玩意的转移不是和到叶子的距离相关的，而是和到根的距离相关的。想了一会发现实际上不同的权值段数是和子树内的修改次数相关的，于是改了个以修改次数为大小的重剖然后上线段树。复杂度是 $O(n\log^2n)$，但是不太清楚怎么卡满，随便造了一些 1e5 的数据大概需要 0.3s~0.4s，感觉 88pts 应该是稳的。但是一时不知道怎么去掉一个 $logn$，就放弃了。 T3 有个子任务是区间逆序对，环顾四周想看看有没有 lxl，然后发现自己根本不认识 lxl，于是还是安心做题。部分分似乎很足，暴力和 A 两个部分写完就有 40 分，但是似乎就没啥别的东西可以做了。还剩 1h，B 似乎有一个 $O(m\log^3n)$ 的启发式树套树合并，但是非常繁琐。回忆了一会二维莫队怎么写，然后发现自己根本没写过二维莫队，推了一会感觉是个 $O(mn^{3/4})$ 的东西，但是还剩 0.5h 写不完了。这时发现最底下还有一个 C 的 12pts 可以做，赶紧 rush 掉了。 然后就是不断检查文件名，检查输入输出，检查空间，检查数据类型，卡 T1 的常数，改了某个位置后似乎可以卡到 1.98s 但再测的时候就变成 2.1s... 估分 85+88+52=225，应该还行。 出考场一问，蒋队长估分 240，Zeven T2 炸了，只有 160，EA 甚至估分达到了 252，顿时对自己的分数失去了信心。蒋队说 T2 是线段树合并时打标记，但是感觉自己考场上想起来了也不太一定调的出来只写过一次的东西，于是作罢。不过蒋队没看到 T3 的 C，不然就可以和 EA 平分秋色了。而 T1 直接拆点就是正解了，继续后悔... 下午看分数，结果是 100+100+52=252，T1T2 看上去不太行的东西居然都过了，T3 也没挂分，是个不错的开局。 HB 的其他人却有不同程度的挂分，蒋队挂到 227，EA 只有 180，xht 和 ouuan 也挂的很厉害。。。 下午无所事事，吃完晚饭后等密码条时被向总拉着绕行操场。这时有个工作人员说要找人采访，我当机立断把 ustze 推了出去，但没想到把自己也搭了进去。emmmm....还好同学们到的时候我已经整完了，于是一起欣赏（摄像）ustze 的英姿（口误）。（”这场考试将确定我的地位“ 晚上听讲课的时候，发现 T2 的数据奇水无比，甚至放了 $O(n^2logn)$，而 T3 写二维莫队至少可以多拿 12pts。lxl 的大分块有两个人场切，简直震撼。 晚上继续泡自习室，原因同昨天。 ### day2 绝了，昨天晚上 10:10 睡下，翻来覆去到 11:50 才睡着，今天早上 5:30 就醒了，简直了。要不是平常我也不怎么睡觉，这早就完蛋了。 座位是 E001，密码是 cwggxe（艹我，哥哥，邪恶？）。EI 坐在我左手方，莫名感觉压力山大。 准时开考，看题。T1 是个构造，但是没思路。T2 是个啥啊，完全没思路。T3 是个弦图，但是也完全没思路。 1h 过去了，依旧一点进展都没有，T1 写了个贪心每次取最小的去合并，但是怎么都过不了样例。而这时 EI 已经走了（？？？）。 去洗了把脸，强迫自己使劲想 T1。玩了下发现贪心可以过那个 $m=n-1$ 的样例，那是不是找一个大小为 $x$ 的集合使得元素和为 $(x-1)k$ 就做完了？用 bitset 优化背包后复杂度 $O(\frac{n^2k}{w})$ 长的非常正常，于是码，1 h 40min 的时候过了所有样例，测了发极限数据需要 2.2s，于是卡常。发现如果 bitset 开 $2\times500\times5000$ 需要 2.2s，但是开 $2\times 498\times5000$ 就只需要 1.98s。虽然依旧不明白为啥，但是我也没啥理由继续整这个题了，于是放弃。 T2 完全没思路，但是送了 16pts，先码掉。 T3 居然没有暴力分，但是 C 似乎可做。先写了个 dp，但是假掉了，然后发现拆成若干段之后每一段可以分别贪心，于是过掉了 C 的样例。 还剩 1h ,回去看 T2。感觉 $O(2^{2^n})$ 一脸不可过，但是性质 4 似乎可以整一个类似三合一的东西。于是赶紧 rush，但是到最后都没有过掉样例，只得作罢。 估分是 100+16+25=141，两天加起来 393 分，这恰好是我去年 CSP 的得分（...） 吃饭的时候讨论题目，Zeven 估分 120，蒋队没看到 $m\geq n-2$，瞬间爆炸，HB 的其他人都没切 T1，在欢声笑语中打出 GG。 下午查分咕咕咕了大概 90min，最后分数是 100+16+25=141，一分没挂。Zeven T2 拿到了更高的分数，总分 137。蒋队的 T2 也多了一些分，但是因为 T1 爆炸，总分只有 59，留下了深深的遗憾。 虽然感觉 D1T3 和 D2T2 还可以拿更高的分数，但是至少做出来部分一分都没有挂，也没有啥遗憾了。 17:00 的时候听说队线是 450，过了不久排名也出来了，我 rk26，甚至比一些以前只能仰望的选手都要高，甚至感到一些不真实。Zeven rk77，蒋队 rk90，YDykjjj rk160。Zeven 和蒋队只要不挂分的话都可以进队，可惜没有如果。 晚上去签约的时候因为迷路去晚了一些，招生的老师说就差我了。我和 Zeven 选了清华，蒋队和 YDykjjjj 选了北大。面试之后都拿到了一个叫做《申报建议》的东西，也算有所收获。 晚上本来说要通宵，结果我们寝室不到 12:00 都睡下了，我 1:40 的时候手机没电也睡了。 ### day3 闭幕式的时候，会议厅里我的手机还是连不上网，幸亏之前下了部漫画不然要无聊致死。 day1 晚上的采访也被剪了出来，简直是公开处刑。 颁奖是从铜牌开始从低到高发的，金牌是一轮 12 个，所以我的名字排在了那一轮的最上面。 午饭后就离开了长沙一中，一路上在聊些没营养的话，yhx 的杯摔了之类的（笑 然后一切就都结束了。 ### ending BJpers2，Zeven，YDykjjj，yurzhang，Collin，Sinner，Topcarry，colemak，ouuan，xht37，JasonZhan....希望这届的 HB OIer 都能考入自己心仪的大学。 EternalAlexander，ustze，Fzzzz，（为啥 hsy 下一届的没多少英文 id 啊，而且我没背下来）... 希望未来的 HBOI 越来越好。