Keep dreaming, remain loving.

· · 生活·游记

又是半年,去年的 NOI 仿佛刚刚过去。

2.28

去了机房,下午和群友一起打了 trackmania,拿了几块金牌。

晚上回家并没有像往年一样写板子,而是随机点开了几个 CF 题看了看,尝试维持平时的训练状态。

晚上睡得不算太晚,似乎并没有像担心的那样因为省选而过度紧张,很快就入睡了。

3.1

起的得比平常早,不过还算习惯,早上开半小时车去杭师大。路上发现这是我最后一次去杭师大考试了,这条路走了四年,也许这是最后一次。

这是一场只能赢不能输的战役。

进考场,座位右边是 Nz,往右是 Z301,再往右是 umbrella_leaf,斜对面是 cyfff,shaojia 在斜对面的左侧。开考前,我尝试通过不断喝水来维持自己清醒。

先看 T1,猜了一个答案是一段区间的结论,然后二分一下上下界,小样例过了但是大样例挂了。我的心跳瞬间加快,也许是过于大的压力和刚开考不久过于紧张的心态,那一刻我的脑海瞬间浮现过退役后一切可能的情景。不过我努力缓了过来,分析了一下发现可以对值域扫一下,大约半个小时通过了大样例。

T2 是有向图可达性类似问题,2G 6s 的限制直接让我傻了眼,我对这一类可达性 bitset 问题一窍不通啊,唯一做过的题目可能只有 qoj4000 了。

简单分析了一下,根号重构套上值域分块似乎能做到 O(\frac{nm}{w}+(nq)^{1/3}n) 的复杂度,看起来是能过的,而且感觉上常数不大,开写,大概又过了半个小时写完。最大的样例要跑 10s 左右。

简单卡了一会儿常,最大的样例和自己造的数据还是得 8s 左右。这时候已经过了将近 2h 了,我觉得该放一下了。

去看 T3,一看到题就开始想逐位贪心,于是尝试如何 check 一个前缀是否合法。中途猜了一堆结论,但是怎么都过不去大样例,甚至一个都过不去。只剩 1.5h 了,我的 T3 还是 0 分。

想着是时候拼暴力了,先写了个爆搜,然后分析了一下特殊性质,发现树的结构是简单的,很快就写完了,森林也是类似的。随后开始研究 图联通 的性质有什么用,但是分析了很久无果。

最后检查了一下文件就结束了,没能再给 T2 卡常。

出场问了一下发现应该是大众分,群友的区分主要是在 T2 的效率上。下午尝试忍住不看 LA 群和 U 群的讨论,努力放松心态。

晚上开始随机看了一些 QOJ 和 CF 的题,一是维持平常的感觉,二是尝试忘记白天发生的一切。睡眠质量很好,很庆幸这两天都没有失眠。

3.2

比前一天晚了一点。给自己的比赛策略是打的稳一点。

开电脑之后看了一下文件大小,为什么 years 这个题的输入文件大小这么小呢,不会又有集合幂级数题吧?

开题,T1 似乎是直接模拟一下就行的,过去 20 分钟写完并过了样例,测了一下极限数据的速度很快。

看 T2,居然是数最小树形图?一看数据范围,n\le 15,心里一凉,这不是至少得要一个主旋律?但是我最近根本没有做什么集合幂级数题啊,这可咋办,只能硬着头皮做了。

先把 w_i 互不相同的性质拼了,然后开始尝试推到 w_i=1 的性质。花了很久终于推出了主旋律的做法,然后开始编各种容斥,花了很久终于才编出一个 O(4^n) 的做法,但是只有 44 分!我甚至不会把这个做法优化到 O(3^n),更别提带边权了。

我尝试对这道题的难度进行评估,感觉这是一道和去年 d2t2 类似的题啊,想进省队大概得通过吧,这样的分数肯定是不够的。

我尝试让自己恢复理智,先去把 T3 开了。但是我怎么完全不会呢,似乎只能写一个爆搜,过 n,m\le 108 分。虽然爆搜能跑后面的样例,但是自己造了一个 m-n+1,\dots,m 的数据就爆了。尝试只记录 delta 数组也还是跑不出来。

原本想拼点 T3 的分来冷静一下的,结果一点分也不会,这下更红温了。反复尝试冲 T3 的特殊性质和 T2 的更有复杂度做法但是都无果。

最后 3 分钟,我把所有文件都放好。然后我把 T2 的暴力和 w_i 互不相同性质拍了一下,挂了!我的大脑一片空白,我不知道我该干什么,愣在那里,直到比赛结束。

此时我只能祈祷只是对拍的数据造挂了,或者更坏一些,只有 w_i 互不相同的性质写挂了。

出场问了一下,似乎 T2 并不是大众题,但是 64 分的选手还是不少的。好在 NOIp 稍微一些领先,以往能补上 day2 的劣势吧。

现在能做的,只有祈祷不要 FST 了。

3.6

经过了一整个下午的等待,终于要到了分数:400+(100+88+52)+(100+32+8)=400+240+140,两天各 FST 了 12 分,按照民间传的榜,最后去掉两个国家队似乎正好被卡出 A 队?

Day2 打的保守一点早点写拍结果会不会更好呢?