CTT2024 游记

Nesraychan · 2024-12-08 15:51:04 · 个人记录

NOI 后没怎么学 OI 了，就打了打集训队胡策和 AT/CF，觉得进个 CTS 就差不多得了。

Day -1

提前一天到了北京，订了 CCF 订的酒店，第二天比较方便换房间。

感觉北京不是很适合人类居住，风大得离谱，拿个外卖差点没了半条命！

晚上打游戏。

Day 0

上午先换了下房间，室友是 lcj，非常强力！

试机。第 inf 次写了传统试机三道题，发现番茄 oj 比清华的本机慢了 3 倍，有点离谱。

晚上打游戏。

Day1

进场先看了一遍三个题，A 看着可做，B 看起来很简单，C 是神秘交互。

先开 B，发现直接贪心匹配就是对的，然后每次修改只会改变 O(1) 个位置，只需要线段树维护括号匹配就行了。

有点难写，写了 6k 左右，调了挺久才调出来的。一开始 O(n\log^2n) 被卡常了，改成 O(n\log n) 才勉强跑过去。

开 A，首先肯定要拆贡献成计算概率。想了一下 m=1 怎么做，发现只有覆盖某个点的操作对概率有影响，于是可以考虑状压。

会了个 O(2^mn^3m) 的容斥，发现序列的头 m 和尾 m 个元素是不用容斥的，想到可以设计一个 O(2^{n-2m}\text{poly}(n)) 的做法。

但是想了半天无论如何都优化不了复杂度的 n 的个数，写了一下只有 25 分，本地甚至无法通过 n=30,m=10。

卡了半天常无法通过，只能开 C。感觉这个题是类欧状物，但想了半天不是很会，目标改为先通过 sub1。

可以用 V+\log V 次操作对于每个 x 求出所有 kx+b 下取整的值，然后暴力枚举 k,b 的取值 check 就过了。

剩下的时间一直在想如何优化 A 的复杂度，但没有成果。