NOI 2020 游记

咕了好久，现在更 另，我和 LHQ 都在 533，欢迎来夜袭(bushi) ## Day -2 晚上到了长沙，和正在长沙玩的同学吃了个饭就 10:00 了。 根据我父母的计划，晚上在酒店睡，明天下午送我去一中。 颓了一会就睡了。 ## Day -1 早上被父母拉起来爬岳麓山去了，累炸了 /youl 中午吃完饭以后去酒店休息了一下，然后去一中。 大约 4:30 到达一中，而拿着我的各种报道资料的教练 4:40 才到。 整好了以后面了下神虎，就去宿舍看了。 然后发现宿舍是阴间网络 /px 稍微水了一下下群就去吃晚饭，晚饭还是挺香的。 并第一次忘记带胸牌。 回来继续水群，才知道有自(tui)习(fei)室，于是就拿着电脑去自(tui)习(fei)室学(tui)习(fei)了。 在自(tui)习(fei)室持续水群，和一堆人讨论了半天面基结果我谁都没有面到 晚上回寝室睡觉。 ## Day 0 早上起来以后吃完了饭就去操场了，并持续水群 运动会既视感 一边等叫江西一边水群，然后突然发现左边是 SH 队 往后扫了一下就看到 ix35 了，sto ix35 orz 进场后就一直在睡觉 “有剩饭的扣一分” “五个线性代数题我做出来四个” 然后还有万众瞩目的 CCF 宣传片，3 M 原 则 结束后合影，然后……江西是非常非常晚被叫到的……阿卡林省石锤 旁边的同学（江西的）：“江西是什么省啊，有这个省吗？” 拍完照就拉着 LHQ 去自习室颓（ 中午吃完饭以后，回寝室颓了一会 DL 然后去练习赛 在赛场门口见到了 Fz 和 EA orz 笔试 T47 我纠结了好久，不过最后还是选到了 ABCD 我和 zmy 笔试都是 100，LHQ 因为莫名其妙的原因挂了两分 看了一会试机题，觉得十分自闭，并不想写，就溜了 回寝室继续颓 DL，然后 LHQ 在旁边玩 mc。 一个下午我感觉 LHQ 确实玩过有一会但比云玩还要云玩…… 本来想三人搞联机的结果没搞成，然后我就开始玩单人。 一个下午就在 mc 和 DL 交替玩中过去了，晚上也是。 似乎是晚上，Froggy 从我们寝室门口路过，然后被 LHQ 抓了进来（ 我们准备睡觉的时间一再推迟，9:00 -> 9:30 -> 9:50 -> 10:00 -> 10:30 ## Day 1 早上出去吃饭的时候又忘记带胸牌了……吃完饭才发现…… 于是 7:35 我还在赶上楼拿胸牌。 进场前持续水群，进场后找到位置然后就在那里看钟。 8:01 正式开始，然后我开始翻试题。 看了下 T1，想到了一个十分暴力的 $O(Tm)$ dp，看到 $w\le 5$ 发现可以矩乘优化。看到 $n\le 50,m\le 500$ 我更加坚定了这是矩乘题。 于是就开始写，写到 9:30 终于过了所有样例。 算了一发复杂度，$O(w^2n^2\log T(wn+k))$，非常稳。 然后开 T2。 我认真看完了原版题面，发现好像有点奇奇怪怪的诗意（？） 一开始只能想到 $O(mn2^n)$ 的彩笔做法，只有 16pts。想了想发现可以容斥做到 $O(nm2^m)$，然后一想把暴力跳覆盖换成树剖+线段树不就 $O(m2^m\log^2n)$ 了吗，然后就开始写。 写完算了算复杂度只有 32pts，不过对我这种彩笔选手差不多了。 然后开 T3。 我要成为时代的眼泪了 /dk 给定排列，离线求区间在一定范围内的数的顺序对？ 甚是自闭，就写了 $O(n^2\log n)$ 的大暴力，测了样例 1 发现没问题，然后继续自闭。 区间逆序对的部分分我又不会，特殊性质 2 我也没啥想法。 然后我就写了个随机数据生成器，结果发现只能过 $n\le5000$，自闭。 不知道为什么我去测了样例三，然后……秒跑完？real time<0.2s？？？ 想了一下发现好像没啥问题，这个特殊性质只要出题人不特意卡暴力就完完全全跑不满。 然后我去跑样例二…… real time 2min 自闭。不过答案是对的，这是好的。 算了一下大概 100+32+36 了？才 11:30 不过我啥都想不出来啊…… 然后就在乱搞，测了许多遍样例。 最后 10min 突然发现我 T1 用 dfs 求 $T \le 4$ 的情况貌似可以卡 /jk 紧急修改，过了样例，放心了。 出来以后去吃饭，继续水群，交流分数。 LHQ：50+32+40=122 我：？T1 不是矩乘练习题吗你怎么没切 LHQ：？？？ 我：？？？ 吃完饭回寝室来补游记了。 下午去看分数，85+32+36=153 怎么挂了 15pts 啊草，重测一下 诶草我这里好像是对的？？？？ test 2,4 提示 wa 但本地 ac，申诉去 钓来 lxl 以后，我才意识到： 我最终改的代码没有编译过。 所以我之前的代码 test 2,4 正常，但是我结束前修改的版本 wa 了。 大草 自闭了，成功一波操作 163 -> 153 晚上忘记有讲题，颓了一晚上 mc ## Day 2 luogu 打卡 500 天整了呢。  吃饭吃的很晚，大概 7:50 才到。 一看，今年六道传统题搞啥子 先去开 T1，马上就想到了一个奇奇怪怪的贪心，人脑模拟过了样例 1 的 test 123，然后在 test 4 挂了。 想了想发现 $m\ge n-1$ 的时候这个贪心就是对的，那么 $m <n-1$ 呢？ 然后我想，把被一起用过的原料连边，得到一个图，思考以后发现它可以变成树，然后发现 $m<n-1$ 相当于要搞一个 $n-m$ 个联通块的森林。 这时我发现数据范围的 $m\ge n-2$，那就是两个联通块，那么只要找到 $t$ 个 $a_i$ 使得他们的和是 $k(t-1)$ 即可。 一开始我以为是 $k$ 的倍数即可，就写了个 $O(nk)$ 的 dp，后来发现不对，但是就没想到怎么做了。 想了想发现只要取出若干个 $k-a_i$ 使得和为 $k$，然后可以背包瞎搞一下，用了 map 实现。 然后一测样例非常快，感觉能 A，然后写了个 gen 发现……我的程序慢炸了…… 不过好像有 85pts 比较稳，海星 自闭 于是去开 B，这题目怎么这么长？？？ 花了 5min 读完，感到劝退 一看数据范围，就没几个我会的特殊性质，十分自闭 仔细思考了很久，发现自己会了 32pts（$h\le2$ 12pts，特殊性质3 4pts，特殊性质4 16pts） 过于自闭，就断断续续的写，终于写完了调过了 然后开 T3，发现我完完全全不会。 满足这个性质的图好像叫弦图来着？但是我没学过弦图啊草 看了看数据范围，好像 B 比较可做，推了一下下没推出来 弃疗了一会， 12:00 开始继续试图做 终于把 B 推了出来，写了，25pts 有了 一算 85+32+25=142，和昨天一起没到 300，难受 于是就把 T3 不满足 B 个写了个暴力最短路上去，然后……莫名其妙过了样例 4？ 虽然我也不知道为什么，但是能过就好 出来以后 LHQ：我 T1 写的退火 我：？ 我：退火还能做啊草，什么玩意 边吃饭边水群，然后回来咕游记了 玩了会 MC，然后准备去拿成绩 3:00 到了却没有开门，我就在那里一直等，边等边水群 然后就开始讨论面基（ 熬到 4:10 我不想等了，就回寝室继续玩 mc 不知道什么时候，教练说门开了，我就去看成绩 T1 只搞到了 70，wtcl T2 特殊性质 4 挂掉了，wtcl T3 过了 test 8~15，7 不知道为啥挂了 总分 70+16+40=126 两天总成绩：85+32+36+70+16+40=279 我还是菜 /kk 教练说我应该稳上 Ag 线，那就海星 去听讲题，事实上是划水 然后颓了一个晚上，1:00 才睡 ## Day 3 没去听答辩，又颓了一早上 然后发现自己确实 Ag 了 中间教练拉我们去和北大的人谈，要根据我和 LHQ 的 Ag 把我们的约换成 1=（我们之前去北大拿了 2=） 闭幕式又一直在划水 然后持续膜拜 Au ix35 吃完饭又回去继续颓，捡了下东西 下午被妈接走了，目前在火车上