CSP-S 2020 游记

CSP-S 2020 游记

考后 Day 3 才写游记是否搞错了什么

Day $-\infty$

初赛。到考场时发现包里有支昨天没吃的牛奶软糖,心情愉悦(?

先去机房摸了会儿鱼,然后跑去考场。左边坐了个初中生唉

然后开题。

恩,选择题没得问题。然后香农那个题,前几天 yy 跑来给神题:

要求设计两个程序,评测机给 1 号程序一个值域 [0, 256) 的序列,1 号程序给出一个值域 [0, 256) 序列,然后评测机把给出的这个序列随机打乱,给 2 号程序,要求 2 号程序还原原序列(评测机给 1 号程序的)。

然后跑去 google 什么 map sequence to multisetinformatics on multiset然后莫名奇妙查到香农的信息论,没想到用上了(

然后阅读程序,都挺好做。不过那个 nth_element 有个时间复杂度分析自己魔怔了,错失 3 分。然后那个交换的玄学分析,自己用的找规律,然后考试玩了半个多小时没玩出来构造方案…

后面补全完全是傻逼题了。感觉难度是要比前几年低一些。

考后实际 97,就是那个时间复杂度分析。我是傻逼。

Day -1

颓。看 amelia 的 stream。

Day 0

打板子。淀粉质、长链剖分、左偏树、任意模多项式乘(???)、扩展中国剩余定理、矩阵求逆、Manacher…

显而易见,以上打的板子没一个用上了。

Day 1

早上起得比较晚来着,很久没这么爽过了(不是

看 amelia 的 stream(?

家长让早上不要做题了(并不是啊喂),于是跑去旁边刷手机,一个愉快的上午(??

然后中午想起了自己已经忘得差不多了的点双/边双,赶紧手机上临时复习了波,及其草率。

吃完饭坐同学家长的车去到考场,到考场时教练已经到了,然后无所事事的我们在车上睡了半个小时。

该进考室了,进门发现健康码已失效,不过保安完全没在意(

考试

恩,开始码了板子,无所事事后看见旁边人都已经开题了,才发现是我没听见考题已经下发了,赶紧下题((

密码文本下发好评。

T1:?草 不想写 跳了

T2:?傻逼

然后赶紧把 T2 写了,那时候开考了半个小时感觉。不过当时并没有发现 cnt 可以等于 64。

T3:?

然后想到应该倒序处理操作,然后由于自己过菜就不是想得很清楚了。

此时周围考生全部在狂码,而我一直纠结于想不出来的 T3 和完全不想写的 T1…

然后想到了 T3 拓扑序的做法,不过公式推错了,甚至还用到了一个玄学等比数列求和,然后发现过不了大样例和自己的 hack,心态比较炸,于是转头看 T1,心态更炸了(草

这时已经过了一个半小时。然后赶紧狂码 T1,然后在计算器的加持下没用多久,唯一就是刚开始时没注意到 400 年的整数倍也是闰年。代码有点长,不过逻辑还算清晰,因此没调多久,一个小时之后就过了大样例。

出这种题的人的外公的女儿是…?

T3:恩…

重新推了一波式子,发现我是傻逼,赶紧推翻重写,一波过大样例。然后考试只有半个小时了,赶紧开 T4。

T4:蛤?

当时以为的策略是,一直模拟这个吃的过程,如果遇到一个 y 正准备吃 x,并且这个 x 是有过选择权的(当过最强的蛇),那么 x 肯定会选择在他当老大时直接结束游戏。然后码了一波发现过不了大样例,而且错得离谱。

为什么错得离谱呢?考后发现自己是傻逼。原本应该是

1
2
int x = [当前最强的蛇];
while (更为厉害(x, 当前次强的蛇)) [x 吃最弱的];

自己脑抽写了个

1
2
int x = [当前最强的蛇];
while (更为厉害(x, 当前最弱的蛇)) [x 吃最弱的];

恩,我真牛逼。然后上面这个策略也是错的。你考虑当上老大的分别是 x ... c ... y,其中这个 c草我亏了不吃了,然后 x 是能想到的,于是尽管 y 会吃他但 x 依旧会选择吃掉当时最弱的蛇,因为游戏在 c 时就会终止了,y 上不了台。

总之 T4 怎么都没有弄出来,直接留着这份代码交了。最后 5 分钟回去看了前面几道题,发现 T2 cnt 可以等于 64,然后 由于自己手写过 bitset 想起 1ULL << 一个变量 是会有循环位移,也就是说 1ULL << x == 1ULL << (x % 64),但是本题中肯定是应该等于 0 符合题意(在模 2^64 意义下),于是加了一波特判,以为自己很帅,但并没有发现 n 还能是 0,肝。

考出来预估 100 + 100 + 100 + 0 = 300,然后出场遇到神昆,苦诉 T4 不会时神昆表示极为疑惑,并表示 70 分不是基础分吗?于是神昆顺利 370,而且考后冥间数据测出来确实如此。

到家里想起我那种旋风写法貌似能通过某些玄学途径拿到 n = 3 的 20 分(毕竟过了小样例来着),不清不楚。

Day 2

颓。到外面吃饭,鱼刺卡喉咙了,现在还痛。

看 amelia 的沙雕 collection。

想了一个 T4 的玄学单调队列,然后过了洛谷数据。

Day 3

讨论 T4,发现单调性自己证不来,然后自己找到自己的 hack,然后自己手改了一下又过了,然后又找到 hack,然后手改一下又过了,然后就貌似对了。

这两个 hack 把 SC 除了 zjk 全部人都 hack 成了非满分来着(

然后发现自己 T4 居然真的莫名其妙 20 分,搞不民白(

作者

Mivik

发布于

2020-11-10

更新于

2021-05-31

许可协议

评论