CTT2024 游记

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

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

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

晚上打游戏。

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

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

晚上打游戏。

进场先看了一遍三个题，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 的复杂度，但没有成果。

$25+100+10=135$，总榜 rk23，集训队 rk16。

下午活动是逛校园，事实上我 thupc 的时候已经逛过了，所以没啥新鲜感。但为啥是徒步走 2.5h？太变态了。

晚饭是麦麦，吃完回酒店打游戏。

进场看题，A 感觉是小清新交互，B 看起来巨大困难，C 是神秘构造。

先做 A，很快发现答案一定 $\le 2$，更具体地，出度最大的点一定符合条件。

但想了一会感觉不太好直接求出最大出度的点，于是尝试弱化一下条件，事实上所有出边不被别的点包含点一定合法。

于是可以每次随机取一维 check，保留所有存在这一维的点，这样期望大小会减半。

很好写，在 30min 左右便通过了这个题。

发现旁边的人都在做 C，于是我也开 C。先想的是如何写一个 checker，结果发现完全不会啊。于是只能先放弃 checker，写一个一定能确定唯一树的方式。

发现两个拓扑序一定可以确定一条链上的边，写了一个 dp 求最优覆盖方案数获得了五十多分。

接着发现事实上这样子太浪费了，只需要满足在一个拓扑序的偏序关系，就可以用一个拓扑序确定一条祖先链。

这样可以做到叶子个数，多获得了 $10$ 分。

回来做 B，发现只有路径的限制是有用的，但想了半天完全不会多项式复杂度做法，写了搜索和 $type=1$ 的链跑路。

由于我认为 C 的分已经不低了，剩下的时间都在想 B，但没有什么成果。

$100+17+61.74=178.74$，单天 rk41，集训队 rk23，两天集训队 rk18。

为啥这 C 全场过啊，理解不了一点！

下午是讲座，不想听，于是跟 ljr 和 lhr 雀。

晚餐是牛肉饭，回酒店后继续电动。

算了一下，明天只要不被翻 $50$ 分就能进，还是挺稳的感觉。

进场看一遍题，A 看着是个很常见的问题，但数据范围咋这么大？B 有点神秘，C 是一个看不出难度的交互。

先开 A，目标是得到三方的做法，但想了半天没有进展，只会最基础的四方暴力。

这是观察到旁边的人已经获得了 A 的 $85$ 分，感觉有点绷不住了，先去看看 B。

发现动态放积木的过程是一个划分，划分关系构成一个二叉树，这个状态是比较少的。确定了二叉树后可以一遍树形 dp check。

写了一半脑子有点抽了，以为区间内的点不能全选，有点红，再回去看 A。看了一会发现 B 的做法好像是对的，回来写完获得 $70$ 分。

优化是容易的，枚举所有选的点然后状压 dp 可以直接做到 $O(4^n)$，很快就写完了，获得了…………$60$ 分？

卡了卡常卡到 $70$ 分，实在卡不动了，回去看 A，还是不会！

只有 2h 了，只能先开 C。发现这个操作很方便求重心，于是考虑点分治。

想了挺久怎么做，先求出最大子树的儿子的点集以及所有出边后可以整体二分确定所在点集。但是常数很大，只获得了六十几分。

再想了一会 A，还是不会，只能写四方。获得了…………$30$ 分？咋 $n=200$ 都过不去，卡了卡获得 $40$。

感觉现在还有很大的被翻的风险，想着能不能去优化 C。

突然会了一个乱搞，每次随机排列贪心求一个独立集，然后整体二分求出独立集和其他点之间的连边。

写了一下最后一个包 T 了，想了一下如果有两个相连的度数很大的点就寄了。但是求出的独立集中的所有点的连边事实上已经确定，于是可以删掉这些点。在结束前 10min 左右调出来了。

$40+70+100=210$，单天 rk35，集训队 rk23，总榜集训队 rk16。

发现大家 $O(n^4)$ 纷纷卡常得到 $85$，为啥我过 $40$ 都要卡常？写的 B 的两个做法分别是 lhr 过的做法和 std 做法可还行？

但至少进 CTS 了，福建四个人全进了，牛逼啊！