CSP-S 2023 游记

First Post:

Last Update:

希望别挂分。

Day -2 ~ Day -1

睡得不怎么好,背部总是发热,像火烤一样。

Day 1

14:30 ~ 18:30

开场先把四道题都看了一遍,T1 简单题,T2 只会 50,看上去好难,T3 大模拟, T4 不知道是啥,先二分答案。没有一道 !吐了。看完题时 14:40。

然后花 分钟写了个 fread 快读,接下来 分钟写完 T1。一开始以为 T1 能操作很多次,发现无论输入如何答案都是 。改完就过样例了。

此时我发现 T1 只有两个样例!查看剩下题目的样例,发现没有一个题目的样例是给全了的。看来这场暗藏杀机。有模拟赛那味了。

还有十分钟到 ,见缝插针地想了 分钟 T4,发现菊花的部分只要求出 表示一个点最晚要在 时刻到达,然后把 从小到大排序即可完成二分答案的 Check 部分。想到这点后意识到 T4 是个贪心题,且有点像 exchange argument 的变种。此时已经 ,开始写 T2。

开始写 T2。先用 分钟写了 分暴力。然后对着暴力观察,容易发现只需对每个 求出 表示最大的 满足 可以消掉,就很容易求出以 结尾的合法串数 )。关键在于 怎么求。容易发现 ,且 之间的字符肯定能被划分成若干个 形成的区间。于是有朴素做法是先设 ,如果此时 就令 ,直到 。这就是一个向前跳跃的过程。所以可以开个数组 记录从 开始跳,跳到的最近的字符 在那个位置,然后直接令 怎么求 ? 可以由 拷贝过来,然后让 即可。

太难了啊这个 T2。当时想了 个求 的做法都假了,当时已经过了 分钟,额头已经微微出汗,大脑开始红温,去上了个厕所,意外发现厕所里窗边的凉风吹得非常舒服,状态很快就恢复正常了。

写完 T2 之后

测完样例,喝了瓶牛奶,大致规划了一下 T3 的思路,发现如何求地址已经被写在题面里了,这大概是出题人唯一良心的地方。 中开始码码码,到了 才码完。 调过了所有样例。 写了 行和不计其数的 string 和 map。STL 真是好用啊!

现在还有 个小时,我在写 T4 暴力和冲正解的选择中徘徊了一会儿,然后决定直接冲。发现我只需找到 的一个排列,使得 最大化,同时还要让这个排列满足树的限制,即父亲的出现位置必须在儿子前面。最后判这个最大化的 是否 即可。菊花的邻项交换正确性不难证明,把问题搬到树上,应该只需套用树上 exchange argument 的做法即可。观察全局 最小的那个点 。如果某个时刻 被选,下一步一定是先走到 。这是由邻项交换的正确性保证的。于是我们可以将 合并,表示它们一定是紧挨着的。合并出来的新点的 就是 。重复这样的合并过程,对于每个点,我们只需记录其大小和其对应的 ,将其放到优先队列中去即可。合并过程可使用并查集维护。于是一次 Check 的复杂度就是 。其中的 是计算 的复杂度,因为我使用的是另一个二分来计算 。总时间复杂度就是双

写完,发现 T4 大样例要跑 ,开始卡常。尝试很多种方法后,发现只有快读的优化最为显著,其次就是算分段函数的时候有一个小数除法可以提到外面去,加了这两个优化之后跑了约 ,然后看到本地机子是 i3 8 代,想着评测机应该比这快,就没管它了。卡常的间隙还写了个 T2 的拍。

最后半个小时,我发现虽然我会 题的正解,但我只会 题的暴力。怀着这种心态,我到最后都没有想起来 T4 其实是可以对拍的。

下考之后发现这场确实出得比去年简单很多,题目质量也更加不好评价。后来听说 T4 的大样例不读入树的形态就能过,当时感觉有点悬,现在也看淡了,这种比赛挂 分也没啥。

当天晚上,很多自测网站其实已经开始营业,但我也没去关注,只看了小图灵发现 T1 和 T2 过了,就去睡觉了。晚上又没睡好。

我觉得这次发挥最主要的下饭之处就在于 T4 没有对拍,其他的都还好,前三个小时头脑也比较清醒,希望 NOIP 时也能保持清醒与理智。