CSP 2024 发电寄录

Angraecum

2024-10-29 11:51:40

Life & Travel

卑微了一辈子了

卑微的强省弱校垫底中老年选手,真垫底了。

考虑到可能没机会了,记录一下最后的挣扎。

这个时候才写游寄是不是有点晚了(

初赛

教练让只报S组,对于高中生也确实,不过现在来看让我去考J组能不能做出T4都不知道?

随便过了,但是只有 70.5,好像是全校倒二(

最后一个完形填空错四个真的麻了,还是不够努力,不过相较于去年的神金水平确实很有进步了。

中间

觉得有时候太颓废了,于是整了个持续更新的计划,发现有计划的情况下效率确实还可以,但问题是会忘记写计划,然后意识到的时候已经颓麻了啊(>﹏<)

每道题写完都要总结一下,希望能有用吧。

但是我的做题速度和量似乎都太少了,根本比不上别人了😢

我不退役谁退役(

但是能自己做一点网络流了,只能说以前留的坑还是太多了,让我时光倒流我一定是进步最大的人,但是也没这回事儿了😢

虽然但是,考前复习的东西一点用没派上,也许学的很多像网络流这样的东西对于我这种打不到省选的退役人只算是自我取悦吧😢

但还是觉得学OI很好啊,觉得做OI题比做whk的题有意思多了,而且学OI还能和珍视的人在一起,但可惜实力是真的不允许了,真想把六年级和初一的自己扇死惹😡。

10.26

上午做了个J组的dp,然后写了下网络流,终于是能自己写出来不用粘板子了(

哦对还终于会自己写拍子了。

然后中午在机房躺了半个小时,一睁眼发现人走得差不多了,然后就急忙收一下东西,就到校门口集合了。不过还拍了张照,这应该是MZOI近来拍的照中人数最多的了,不过可惜没有多头同款AC抱枕。

然后上了教练的车去了某百年名校,也是几年前能吊打妻中的OI强校/oh

到了那个老校门口,感觉有点熟悉,一些回忆涌上心头,不过都一年了,已经模拟赛垫底无数次了,可以说心态已经金刚不坏百毒不侵了,所以基本没有一点紧张。

有趣的是,在我们考室的座位表上看到了lxl😮,真的是李欣隆,字都一模一样,当时真的被吓到了,但是我好像没看见 lxl?合理怀疑是有人整活,反正考号和我的差很小,枚举一下应该能找到。

货车还给我指了一个叫 lmx 的人,说是去年高一省队的佬orz,还是乐山的,很神奇。

沾了沾队爷货车(orz)的灵气之后进了考场,座位在后排靠窗王的故乡,右边是高二学长,右前方居然就是那个高一进队的佬,而且得益于 NS 优秀的防作弊措施,我可以完全看完那位队爷的屏幕,但完全无法看清他写的东西,为什么会有人写代码用默认大小来写啊,不放大的话不难受吗(

提前把拍子打好了,我也没啥缺省源可打。然后等啊等就提前了一点发密码了。

开题

先都看了一眼。T1 感觉是很简单的题,T2 有点长但应该能做,T3 是dp,T4 长得有点史就没看了。

开T1,发现就是简单贪心,排序之后不断选前面最小的数就行了。比去年T1还简单,10min内过完大样例了,主要是优先队列没有重载稍微浪费了一点时间。

然后看T2,耐心读完题首先想到能将 a\ge 0a<0 的部分分开处理,然后简单贪心想到 a\ge 0 的车取最后一个检测器判断瞬时速度就行,对于 a<0lower_bound 找到第一个能检测到它的检测器一样判断。

然后第二问想了一下就把对 a<0 的转化成了区间覆盖问题,神奇的是我忘记了这种问题怎么做,还是自己糊了一个有点扫描线(?)感觉的东西,感觉挺对的。然后判了一下 a\ge 0 的还要不要额外选点就完了。

写完稍微调了一下就过题面的小样例了,然后去测大的。结果第二个就错了,给我整慌了,都是第二问出错了。然后我以为是区间覆盖可能假了,但直接肉眼盯显然盯真不出来,于是我聪明的加了个离散化,这样就直接能在纸上画了(

结果画完之后又手推一下,发现根本没问题啊,感觉调了好久好久,期间是真的有点破防了。

还没调出T2有点破防了,赶紧去看T3。T3一上来状态就设错了,设成 dp[i][j] 表示前 i 个数,上一个与 i 颜色相同是 j 时的答案。然后推出了一些性质啊,就越陷越深了,然后想到了一种 O(n^4) 的区间dp,但看这个数据范围真不对啊,只有 35\text{pts} 我写个锤子,然后越来越慌就光速打完 O(n2^n) 跑了😰。

觉得T2必须要过,就有回去看T2,我还在每一个判断是否超速的地方把具体的数值都输出来了,发现数值和计数的数量都是对的啊。结果不经意间瞟到输出答案那里我写成了 n-ans2,瞬间破大防,改成了 m-ans2,然后就把所有大样例给冲过去了,是真有点破防了,因为这个错调的时间至少有 1.5h,真的是全场最大失误,导致没时间去重新想T3了。

看了一下时间:wc怎么一个小时不到了。觉得自己太菜了T3真没前途,于是耐心去读T4。想了想对于 n,m\le 8 的那些能力不确定的人可以直接dfs枚举 0\sim 3,因为最多只有三轮,然后比赛过程可以用两个 vector 维护。至于两个特殊性质一眼看着不知道有啥用,就弃了。

然后就写啊写,写了一个大概框架出来,但是我突然发现这个 c[i] 到底是啥意思啊,然后又读啊读,又发现一开始理解错了,然后开始慌。不过冷静了一下发现枚举到 c[i] 时直接把他当作 n 就行了,然后直接更新 k 和比赛轮次 kt 就行了,dfs 只用稍微改一下处理结果时的预处理。

然后有一些小错,调啊调啊一直到了最后十分钟,讲真是真有点慌,不过还在还剩六七分钟的时候也是调出来了,小样例直接过了,大样例看了一眼都很大没啥意义。然后就检查了一下前面交的题的freopen和数组大小。然后就开始在注释里写发电的东西,不过很可惜的是在T2代码里写了很多发电东西正要交上去时结束了,就没交成(当然T2是交上了的),只是在代码大赏里没我的了(

一整场忘了拍子,不过也没啥时间拍

中途上了两次厕所,一瓶茶\pi没喝完。

结束之后没有起立环节,不过当时也忘了有这事儿了。

有点难受

出来一问同学,发现真的全都把T3切了啊啊啊😫,真不夸张,全切了,不过货车说他T2没调出来,大受震撼。结果是人均 300+,不过好像基本都没动T4?

然后出校门,找小灰兔问了下做法,然后发现我的状态一来就设错了,有点悲伤。正解是想到数据结构维护,但是可以维护前缀 \max 和全局加 \text{tag} 优化到 O(n)

记不到发生了啥,反正都陆续走了。不过给我爷爷打电话的时候踢到停车的那个杆子了,真的疼。等了一会儿也走了,还有为什么教练会问有没有人做出来T4啊,不过高端选手的区分度确实就在T4上,虽然我不是高端选手,我连 \sqrt{7} 都不知道有没有😢

回家玩黑神话,杨戬是真的难也是真的帅😋,初见打到第三阶段了,但打了几把后还是直接坐轮椅了,带金身套打了三次就过了,法天象地是真的帅😋,四大天王是真的帅😋,处决是真的帅😋。然后去打大圣,前三个阶段初见过了,总共打了三次没坐轮椅就过了,感觉打起来真的很有意思啊,技能动作感觉比杨戬帅😋。

打完看了眼洛谷,好家伙T4是黑题,前三道和预估的难度一样,然后发现T3怎么也是一堆人都做出来了,真感觉全世界都做出T3了,就很悲伤。发现小灰兔也没睡,他说他默写T2出来挂成90pts了,然后不知道怎么知道了T2的精度问题要不开根直接long long解决。当时又慌了,因为我直接用double开根来算的瞬时速度然后比较,只是比较时写的是 if(vt-1.0*V>eps),赋的 eps=1e-9,真的有点慌了,感觉要挂惨。

第二天下午到学校开始默写T3 T4,T4写出来居然多了 16\text{pts},结果发现顺便把 A 性质过了,因为 A 性质是只要把比赛过程给模拟出来了就能过。但是T3确实只有 20,还是很悲惨。不敢测T2。

然后就各种发电,最后还是在别人打ARC的时候把T2写了。一交,嘿,您猜怎么着,CE了!看了一下编译信息,发现我写的 max2=max(max2,lower_bound(lc+1,lc+cnt+1,p[find2(i)])-lc); CE了,然后就又慌了啊😱,结果想起来赛时因为调试的离散化所以加了很多东西,改成了赛时写的 max2=max(max2,pp[find2(i)]); 后,就直接,AC了?!真被吓到了。

感觉是洛谷数据比较逊,就又去云斗和信友队测了下,居然也AC了,遂放心下来。

还是自己加油吧,珍惜当下的人和事,珍惜每一分每一秒,不要后悔。 如果不想后悔的话就请多做点题吧。 就这样了,总结留给自己看吧。 管理审核辛苦了,没想到电一发起来就写了这么多东西😰 文章里可以加emoji挺不错的😋 ----------- ### Update on 10.31: T4 每次都直接模拟了比赛过程,A性质本来可以预处理每个 $c_i$,因为不同 $c_i$ 的数量最多 $\log n$,但我没有( 总复杂度 $O(Tmn)$,这在洛谷上能有 $28\text{pts}$ 也是神了,只有 $20$ 了/ll T2 在小图零上一开始也过了,再交一遍后 RE on #8?真求你别挂了,$\sqrt{6}$ 都要没有了😭难受死了