NOI 省选 2023 游记

· · 个人记录

前言

因为自己 2022 暑假一些感情和精神状态的问题吧，一直没有达到什么优秀的状态。导致去年秋天联赛犯低级错误寄了，一等都没有。其实挺难受的，但也无话可说。这次只能以“锻炼选手”身份参赛，事实上内心还是有很多不甘的。很难受，希望今年和明年能翻盘。

Day 0

上午九点多的车程，在这之前在机房找了几个蓝数据结构题做，居然还能胡出来个假做法，临走也没调出来。

坐动车遇到了好几个同僚大佬，虽然也没太多交谈，但是还是感觉到明显差距的存在。

宾馆很棒，可能在我所有住过的里面能排个 rk2。

在宾馆吃的晚饭，出乎意料的棒，炫了好多，大抵是我吃过最好的宾馆自助餐。

试机的时候写了遍文艺平衡树，出了点小插曲，但总体还是顺利。适应了一下考场的键盘，美中不足的是敲空格再敲字母再敲空格太快会把第二个空格吞掉，有点延缓我的打字速度。

晚上也没啥心思接着调题，摆。

Day 1

不到一点就睡着了，还好。

六点多起来，喝了罐咖啡，非常精神。

八点半开题。这次头脑十分清醒，先比较冷静地读了一遍所有题。

第一印象：T1 签到，在考场上甚至怀疑省选是否真的会出这么简单的题，T2 感觉是个边双加上某些性质，没细想，T3 数据结构维护信息，感觉比较板。

8:45 左右，写 T1。到了 9:00 就写完并且一次性过了所有样例。其实，对于我的信心还是不错的促进作用。（upd: 2022.4.3 晚上听 pc 说有个区间边界的坑点，后来一想确实没考虑到，不知道会挂多少分。upd：数据太水，假做法一分没挂。）

上了个厕所，回来 9：03 左右开 T2。最开始读了好几遍题没看懂，感觉它的描述和形式化描述是两个东西。又慌于自己好像好久没有写过边双板子，害怕拍不对板子，结果还是一遍写对了，其实也是还蛮高兴的。然后开始想存在的性质。推了两三个左右，感觉没啥太大问题，写了一下，样例 1 过了，但是 2 死活过不去。回头开 T3。

T3 发现远没有我的第一印象那么简单。本来想写个平衡树，结果发现还要求维护原来树的形态。然后考虑树剖，发现没法做到 \log 查询和修改。再考虑特殊性质 v = v_i = 1，推了个信息的更新方式，结果后来又自己手玩了个样例把自己 hack 了。好吧，当时觉得自己可能做不出来了，回头看 T2。

怎么想也想不出我的性质有什么问题，又回去重新读题，发现其中有个概念好像第一次理解错了，又全部推倒重新来。到最后还是觉得题意描述有点模棱两可。疯狂喝水上厕所，保持自己的脑子清醒。前前后后读了十几遍题意，终于明白了，但是此时时间也已经过去蛮久了。想了个 O(n ^ 2 \times 2 ^ m) 的暴力，直接枚举每条边的状态然后判断合法性，又看了一眼数据范围，好像第一个点都过不去。好吧那还是接着想性质。

到 12：30 也没什么优秀的进展，前后想了几个要不就是发现题意没看懂，要不就是发现可以被 hack 。惨。

后面半个小时又回去拍了一会 T1（当时还是没有考虑到边界，惨。），检查了一下文件夹和格式，差不多就交了。

考场估分：100 + 0 + 0 = 100。

出来到学校吃自助餐，也是出乎意料的棒。除了蛋糕奶油有点腻。让人吃一口有种上不来气的感觉。

下午一直在摆，打打游戏聊聊天，不幸的是事是在傍晚还是接到了一条让我比较难受的消息。吃过晚饭出去溜达，又到了联赛时同样出来溜达到的浚河，风景还是非常美的。

回去心情就非常非常不好，晚上躺床上翻来覆去死活睡不着。

Day 2

2:00，依旧睡不着。不知道什么时候意识稍微模糊了一会，然后不到六点又睡不着了。基本上通了个宵。

早饭已经没心情吃得下了，基本上啥也没吃。

去楼下自动售货机买昨天一样的咖啡，发现告罄了，只能买罐红牛。

8：30 开题，还是先读了一遍所有题，出题人放了两道双人博弈的题，很有趣，虽然不会，但我喜欢。

T1 似乎纯博弈论，规则太多，看了下数据范围像是模拟或者暴搜。不想写。于是写了特殊性质 1，去开 T2。

T2 考虑性质。发现似乎费用流可做，在考场上兴奋地差点蹦起来，以为自己居然可以切掉。出去上了个厕所冷静一下，开始打。建模想出来之后没几分钟就写完了，发现能过几个特殊性质的样例。思考是不是某些限制没想到。死活没想出来，样例 2 也比较大不好手玩，很烦，又开始 hack 自己的思路，死活想不出哪里假了。又看了个特殊性质的大样例，发现题意跟自己想的有些出入。又重新回去看题。发现 Bob 是可以根据 Alice 的数列后手处理自己的序列，这个 trick 似乎从来没见过，建模得改。又重新想建模，发现无论如何自己似乎都不会满足这种性质的建模，又开始考虑能不能记录一下可行的入流量，不出意外地假了。但是发现特殊性质自己的费用流应该是可以解决的。那么就只有部分分。

upd: D2T2 挂分，非常傻逼。数组大小开的是按照 100 \% 的数据，但是期间一直 memset，导致全 T。

T3 从来没见过类似的题，设计状态想了几种转移方式都不可行。回去改状态，还是不会。那么还是去考虑性质吧。打了个 t = 1 的部分分。（出来交流了一下才发现 t = n 似乎直接输出 1 0 可以有 2 分，但是在考场上以为还要判断合法性，就没写，白丢两分。）大概率假，但还是抱有一线希望吧。

估分：30 + 20 + 3 = 53。

我大抵是整个考场上厕所最多的人了，但位置还在最里面，由衷地为我出来可能造成对我这排人的不利影响感到抱歉。

午饭没吃，吃不下，回去又坐高铁。到了临沂出高铁站有个公园和地下城，风景还是蛮不错的，日月同辉，月亮很美。

然后是拼的车，一起的还有个女的。超级挤，车厢超级小，挺不直腰放不开腿，难受。出来就感觉腰很疼。

晚上很累，没回学校，晚饭还是几乎没吃。躺在家睡的还蛮早。

出分：只有 D1T1 拿了 100。其他挂没了。居然假做法能拿满。