可以说我的 OI 生涯圆满了,不管 NOIP 能否获奖,我都有了一个省一足以应付。在一个月后我将彻底滚回去搞文化课。
发现学弟们好强啊,有位 300pts 的神。我或许已经是个该滚蛋的老东西了吧。
Day -2
在学校与学弟们开始打模拟。排名大概在 3~4 左右,每次都有两位初中学弟获得 rk1/2。
抽象的是我在第一场模拟是快读写挂,190->0。然而更为抽象的是,某位同学在那天晚上说出自己曾经写挂过快读后,在明天犯了完全相同的错误。
Day 1
我还是喜欢以 1 开始编号。
下午到考场,同学们纷纷在考场门口购买巧克力,然而因为那里的巧克力全是红色的,我并不打算购买。
开题,只能说每题都让我在过 sancheck,还都大失败了(悲)。
T1
刚开始以为密码锁有 $n$ 位,因此思考了 5min 数学规律做法,此后发现我是散兵。但由于我没看懂样例二,去写了一个暴力。然后,我发现,tmd,暴力跑的飞快。
当时很震惊 CCF 出了这样一道题,怀疑了一会时间复杂度,然后感觉挂不掉果断去写 T2。
T2
第一感觉是,预处理出所有偶回文串,然后尝试 DP 拼接。不久想到了,$dp_i$ 表示以 $i$ 结尾的合法串数量,然后对每个位置,找最近合法左端点拼接。但在样例二挂掉了。
然后开始对着样例二调试,发现这个样例是 200 位一种类型。盯着它逐步跟了快半个小时,手推无数小样例,最后发现,我tm没处理...p abba cddc effe pggp...这种情况。
于是修改,对这种情况补充了一步“暴力”跳合法左端点。直至此时我对我的复杂度仍然抱有疑问,于是写了对拍,造了 200000 的数据跑的飞快,然后就放那对拍了。
但是啊但是,在最后 10min 的时候,我回来测了一下 200000 个 a,发现我nnd会T!发现原因在于,我预处理回文串的时候,理论可以被卡到 $n^2$。当时很慌,但发现此前我有尝试判 $a_i=a_{i+1}$ 的情况,尝试在此时 break,发现跑的飞快,并且样例也能过。当时没证明正确性,继续挂上对拍。
现在发现它确实是正确的,因为我在此后的跳左端点中会更新它。
T3
此时,考试时间过去两小时半左右。看到大模拟就感觉不可做,我的模拟能力一向很差。直到 17:30,我仍在丑陋的变量名中挣扎。这是我的一行代码:str[strcnt].siz +=ceil((double)str[ str_id[str[strcnt].mem[i]] ].siz /str[strcnt].qi )*str[strcnt].qi ;
。
去上了个厕所,回来再花了十几分钟写出来一个能过样例 1 的 $2\sqrt2$ 玩意,但发现样例 2 就寄。由于我看不懂它的对齐究竟是什么抽象玩意,特殊性质我也没有什么好想法,我放弃了 T3。
T4
对于一道压轴,我本没有任何想法,写了卡时爆搜滚蛋。时间实在不足,我无法针对特殊性质拿分了。滚回去检查 T1T2。事实证明,回去检查是我最正确的选择。
出场
开始怀疑我 T2 的正确性,晚上睡觉做了挂掉两题的梦。
所幸,洛谷 & 小图灵都是 200pts,省一稳了。