CSP-S2021 挂分记

赛前

数了数,这是我第五次来南航,不知道以后还有机会了(2018 NOIP, 2019CSP, 2020CSP, 2020NOIP)。

上午一觉睡到 10 点,学了一下感觉很有用的 BIT 倍增,顺手拿了究极卡常题冰火战士的最优解。

大概一点钟的时候就到了实验楼门口,天气不错,阳光晒在身上很暖和。估摸着要等四五十分钟,于是先在实验楼旁边的操场上锻炼了一会,然后排了老长时间队。

没有看到同级的 ycx tzc ymx lxr csy 等人,估计他们在 1 号教学楼考试。不过倒是碰到了高二神仙(jgh syr djq)以及 dxm,我直接狂暴膜拜!


赛时

S103 考场,座位号 42(不知道附近会不会有认识我的老哥)。

1:50 进考场,光速打了份缺省源和 IO 板子等待下发试题。

2:25 下发试题,正序开题先看 T1 发现是签到直接开写(比赛还没开始就写代码会不会被判犯规啊,大雾),测完大样例是 2:35,感觉还不错。

2:35 看 T2,题意看错后(本来以为 (nleq 10^5) 是道神题,看完数据范围哈哈了)直接莽了一个 (n^3) 序列 DP,2:50 发现连样例都过不了,糗大了糗大了。冷静下来重读题面发现读错题了。感觉像极了区间 DP ,所以根据题目限制重构了代码((f_{i,j}) 表示答案,(g_{i,j}) 表示 AS 的个数)结果过不了第二个样例。

3:10 一直在想哪里会算重,想了大概 15 分钟才发现 ()()() 会被我算两遍,哈哈。思考了一下如何补救,发现只需要再搞一个 (b_{i,j}) 表示最外层是括号的方案数就行,抱着试一试的心态改了改代码发现啪的一下过了样例,很快啊,上来就是一个样例 3 一个样例 4,全部防出去了啊。测了一下极限数据要跑 1.1s,很慌,所以把递归改成了递推顺便卡了卡常卡到 0.5s 就扔了。

3:45 开 T3,乍一看没啥头绪,想到枚举第一个是 L 还是 R 把序列分成两段之后就不难做了。上个洗手间冷静了一把回来 10min 写掉并过了大样例,以为稳了(实际上大样例 (n) 全等于 (20) 没看出来上面犯的错误)。

4:30 看 T4,题面直接把最小割给写脸上了,然后我一想 (k=2) 这不是狼抓兔子么,能不能用平面图最小割转对偶图最短路的思想切掉这题,发现不是很会,所以写了个多源汇(我甚至不知道怎么写多源汇的网络流,只能凭感觉)Dinic 直接过了大样例,样例 4 要跑 130ms,5 要跑 5s,能拿 60,可以接受可以接受。

5:30 打算动手写 (k=2) 的部分分,发现写起来有点麻烦(实际上一点也不麻烦,只是我想复杂了,一直在想狼抓兔子的一个源一个汇,但实际上可以把周围一圈都分别看成源和汇,说不定这样就能想到正解了)就弃掉了。

5:50 再检查了一下四题能不能过大样例,懒得写对拍(唉)就玩起了扫雷一直玩到比赛结束,南航实验楼 Win7 系统有游戏,好评。


赛后

出来的时候又去操场跑了 1km,算是给自己的一个小庆祝。是不是所有大学晚上操场都会有一车情侣啊,大雾

跑完碰到了 djq,和他交流了一下 T4 正解,居然是区间 DP + 最短路,我直接狂暴膜拜!

后面和一众同学交流了一下估分,ycx 和我一样 360,tzc T3 没想出来只有 72 332,其他人就不知道了。

拿到代码才意识到 T3 要挂大分,当时还挺难受的,不过很快心情就平静了下来。首先,CSP 不选省队没啥好难过的,又不是要退役;其次,这次挂分给了我血的教训,吃一堑长一智;此外,我在赛场上很快做出了这道题目,这让我对自己的水平以及接下来的 NOIP 有了一定信心(虽然是风格非常 codeforces 的萌萌贪心题)。

infoj 测出来是 (100+100+32+80=312),洛谷民间数据是 (100+100+8+[95,100]( ext{Dinic 有 95 就挺离谱的,感觉是数据水了})=[303,308])。加一个 ans[(n << 1) + 1] = 0 之后是 (100)

实际上 T3 在哪测出来的分数都不具有任何参考意义,因为我这题的分数相当于 (mathrm{rand}mod 101)。当然,寄希望于出题人造数据不出现 (n) 的逆序对既不现实也没必要,至少我会做,这就足够了。所以,CSP-S 2021 就这样吧,不算成功,也没啥好可惜的。

出了分数之后会小更一下。


出分

我超,西西艾弗!T3 给了我 (72) 分!

(100+100+72+60=332)

原文地址:https://www.cnblogs.com/alex-wei/p/CSP-S2021.html