SCN- 的博客

SCN- 的博客

Welcome to my Blog !

[NOI2020]游记

posted on 2020-07-27 23:28:34 | under 未分类 |

Day -2

在家自己复习,感觉状态不是很好。打了几道模板SAM带线段树合并维护endpos集合的题,调了很久,心态有点崩。


Day -1

早上出发赶火车,在火车站前和教练学长回合。

顺利登上火车。中途还要换乘。第一次做高铁,体验还是不错的。就是火车上网络不咋样,想刷下洛谷都刷不成。后来试着连高铁上的WiFi结果3分钟断一次,差评。

下午一点到长沙火车站,再坐十几分钟就到了学校(学校比想象中小

报道程序后就到宿舍。环境比想象中好。毕竟原本住8个人的房间只住3个人还是很舒适的。

唯一不满意的地方就是宿舍里的网络太差了,文字半天加载不出来,更不要说什么图片。不过看的别的宿舍网络都挺正常的,难道是运气不好rp--

晚上在学校食堂吃的饭,伙食好评。合口味还不限量,看来这次NOI没有白来(bushi


Day 0

起来后到操场集合,然后到礼堂参加开幕式。原本以为宿舍里的网差的不行,到礼堂后才发现这里根本没有信号……

开幕式还是挺套路的,什么3M原则(money,money,money),然后杜总发言,东道主表演几个节目,各省选手上去拍个照。不知道JX为什么排在很后面,看来又要rp--。

回到宿舍还要背笔试内容,做套题目发现一堆不记得,内心有点慌。不过想到笔试拉分不多,稍微平静一点。

下午考笔试,10分钟写完然后一直在检查。就是一道多选题实在想不起来了,随便蒙了一个。出成绩后发现果然错了rp--。

搞不好这次只能Cu了

晚上熬夜CF有点刺激。主笔写BD题。结果都WA了一发,B题忘记开longlong有点弱智,D题有点情况没有考虑清楚。

因为第二天还要考试11点多就睡了。


Day 1

早上起来知道的第一件事是我B题FST了???!检查下发现极值设小了rp--。

进考场,尽管有昨天的心理准备但考场的空调还是凉的不行。

开题发现T1有点思路,暴力DP分就有了,10分钟写了。然后看了下T2T3,嗯T2二进制枚举又分,T3有点毒瘤(并不知道是lxl出的题,考场上也没认出来lxl捂脸

想了快一个小时T1,发现每一行转移只和前面五行有关,可以倍增优化一下,这样复杂度是 $\operatorname{O(5^3N^3KlogT)}$,当时考场上没有把5的常数算进去,计算器算了一波极限数据发现可做,就开始码,码了快一个半小时过了大样例然后丢到一边。

在看了一边T2,感觉题意很清晰但没啥思路,仔细想了一下感觉可以DP,推了半个小时得到一个貌似可做的式子,调了很久没调出来,怀疑是式子出了问题,于是去看T3。

T3感觉暴力分很可做,先写一个 $\operatorname{O(N^2logN)}$的大暴力,然后又写了一个 $\operatorname{O(N\sqrt{N}logN)}$的貌似过不去的莫队,调了下发现跑的飞快,就是答案算的是错的。

???

调了半个多小时都没发现问题,现在还有30分钟,想到T2T3啥都不会有点焦急。读下源代码,猛然发现应该先维护树状数组再统计答案,改一下过了样例。

只有十几分钟,抉择到底要不要写T2的暴力16分,写的话风险太大,不写又太亏了。后来还是决定写,以我开始几个小时来最快的手速花了7分钟写完代码,调了2分钟发现能过样例。没时间了检查一下文件文件名就离场了。

出了考场一身冷汗。快两点没有去吃饭,考场上的食物都还没有吃。回宿舍。

3点钟去复评,用微微发抖的手打开成绩表,发现

我T1崩了?woc

只过了K比较小的点,其他的都超时被Kill了。冷静下来一想常数 $5^3=125$时间直接爆炸,艹人都傻了。前面暴力DP能过的点都T了,早知道写两个 $Subtask$把两个程序绑一起这样就有75了。

庆幸T2T3没有挂分, $45+16+40=101$,感觉只有Cu了,翻盘难。


Day 2

心情没昨天好,但不至于像昨天那么紧张。

开题,先读了一下三道题的题面。

T1题面很清新,T2题面很新颖,不过读一遍还没读懂啥意思,T3的图的形态 很神奇,当时并不知道是弦图。

然后开始想T1,其实限制条件就这么几个,题意像网络流,输入输出像网络流,数据范围也像网络流,总之满脑子都是网络流。

发现 $k$个 $m$的条件很好满足,直接最大流即可,每道菜只有两种原料怎么都没想到怎么写,最后只好写个爆搜。

然后又读了一遍T2,大概明白了意思。发现 $h$较小的点挺多的,准备写个状压。但想了很久没想明白细节。然后挖掘一下性质,根据给的样例和手推结果,发现只有一个节点可以覆盖所有,左链右链和左右都有可以合成一个没有儿子的节点。按照这个思路写,写了一个类似整体二分的分治,struct里面封装vector,又vector装struct,写着写着发现代码已经不可读了。调了半天还是全部输出No。

心态完全炸了,想到就要这么打铁离场,心中还是强烈的不甘心。吃了两块士力架,昨天考场上根本没吃,接着思路调,调着调着发现可以过小样例,但大样例还是全输出No。

看下T3发现十分不可做,估计1分都拿不到,直接print了一个-1,有没有分就看命了。

然后有点茫然,T1只能拿暴力16分,T2过不了大样例,正确性可能有点问题。最后一个小时是调T1还是T2。

剑走偏锋方能取胜,最后还是选择T2。大概重构了两遍代码发现可以过样例5,修改了些智障错误能过样例6,开O2能卡进0.1s。感觉有了,检查了一遍没啥错误就放了。

还有半个小时,T1毫无头绪,于是喝着水吃着面包思考人生。感觉作为非正式选手第一次参加NOI,Cu也不是特别不可接受,毕竟以后还有机会,这次权当练习。

下午复评,3点准时到了考场,结果咕了很久,又回到了宿舍。四点半听说下面弄好了,拿着密码条去看成绩。

感觉今天手抖比昨天还严重。打开后发现。

wocT2切了,感动感动。

这样总分就有 $15+100+5=120$,于是乎发现Day2分比Day1分高。

晚上听讲评,发现T2写的是正解,只不过自己不会算时间复杂度。。。只有20个人切了还是蛮有成就的。

讲评回来出榜了,大概能Ag?

青春回来了。

经过这次NOI,菜鸡深刻认识到自己的弱小。NOI挂分是偶然还是必然,个人还是倾向于必然,是能力,积累和心态导致的必然结果。自己能做的,就是让自己成长的更加强大和成熟。

希望明年作为A队而不是E队参加NOI,并希望明年的我不再像现在的自己这么naive和simple。那时的我,应该会更强更有力量吧。