CSP-2024 S

Aleph_Drawer · 2024-10-27 20:08:45 · 生活·游记

2024: Episodio 2.

入场。拿到题目。

简要观看了一下题面，发现没有大模拟题目。认为自己已经失败了。

速速扫一眼题目。T1 看上去比较平凡，T2 看上去细节会非常多，T3……欸不是这个 T3 看上去很 practical 啊。看一眼 T4，感觉像是 NOI-type 的题目。

还没看完题全机房就已经在疯狂开写，说明 T1 难度并不大。

但因为之前吃过亏，还是在草稿纸上先模拟推算一下。

显然的我们有一个贪心策略：先进行排序，然后维护一个类似桶的东西，表示没有被删除的数。每次扫到一个新的，选择这个队列里面最小的即可（如果相同就选不了）。然后做完操作之后把这个数甩到桶里。这个正确性比较显然。写了写一开始写错了。后来发现可以双指针维护，于是简单改改调调就过了大样例。O(n)。

此时大概过了 20 分钟。但是感觉很多人已经先行一步了！

好好好，速速看 T2。

先简单扫了一遍题，发现不是很会！简单观察一下性质，对于 a_i = 0 的部分，我们可以轻易确定其超速区间，排个序。这样第一小问就非常好办了。然后第二小问似乎也挺容易。

注意到对于 a_i \neq 0 的情况，超速区间也是前缀或者后缀。我们也可以算出其超速区间。这样整道题就大概会了。

似乎边上的老哥已经在写了，于是决定先写第一部分，为了规避浮点数的计算，我废了一点脑子，写了不少东西，细节有点多。大概写了 30min 左右。

然后开始写第一部分的答案统计。这个很简单，排个序，速速写完。然后把没用的区间拉出来丢掉。

然后开始写第二部分。这其实是一个看上去就非常典的题目，但是自己似乎不是非常熟悉。于是手搓了一个类似于 dp 的做法。大概写了 20min 左右。

此时过去 1h10min 优势在我！

第一次运行，第一第二问都不对。

这下险路恶敌了。

开始慢慢调试。简单 debug 了一下，诶，dev-c++ 怎么用的是这么潮流的新版编译器啊！C++17 都能跑。于是简单设置了一下 path 转到了 vscode 上。这下得偿所愿了！

大概调试了 10min，然后过了第一小问。很快啊！

但第二小问好像是稀碎。

写写调调了大概 1h，两次换了做法，最后依靠一个神毕复合单调队列 + dp 过掉了所有大样例。我也不知道叫啥算法来着（

看着大样例挺强就没写拍了。

此时时间已经过半，大概 2h30min，落后！

唉唉，自己写法太复杂是这样的。

然后开始看 T3。其实第一眼看到 T3 就觉得这不就是一个简单线性 dp 吗，加个类似前缀和的小优化。我心里觉得完全不可能啊！T3 怎么这么弱！

关键是在草稿纸上反复论证了几遍好像也没啥问题。于是就直接开写了。

上个厕所，10min 写完，一遍过掉所有大样例。

？？？？？？？？？？？？？？？？

不是，戈门？

好吧好吧。

此时 2h40min，想着 T4 很复杂应该拿不了多少分，想着 T3 写个拍吧。

此时仍然不相信自己 T3 是过的，只是觉得大样例太水了。于是花了大概 20min 写了一个拍。然后 vscode 报了个错，一度以为我 T3 做法是假的。但是捣鼓完之后直接过了 1000+ 组。应该挺稳。

此时 3h。开始对 T4 发起冲击。

先看特殊性质。a_i \mid 2^{x} 是最好写的。暴力也不算太好写，B 性质也不算很好写。

想着想着决定先写 A。细节很多，码码码大概 25min 通过了样例 2。然后瞪第一档暴力。想着要不算了别写了。check 一下吧。

然后就开始疯狂 check，开虚拟机编译云云。

欸不是我 T1 怎么写成了 freopen("deul.out", "w", stdout);。差点爆了。

反复 check 没有问题。差不多了。

终章。

出考场，大家基本都是 300+，想着自己终于正常发挥了一次。

不是 T2 怎么都写的二分？？？

不是 T3 怎么都写的线段树？？？

好在最后 T2 找到了跟我一样爆算的，T3 跟我一样线性的。要不然真要睡不着觉了。

好好好。

就这样了。大概就是我的一般实力。