WYXkk 的博客

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

吃完饭又回去继续颓,捡了下东西

下午被妈接走了,目前在火车上


2020-08-18 14:31:34 in 游记