CTT 2024 游记

· · 个人记录

CTT 2024 游记

DAY -1

提前来到酒店。

然后和 wtc qbf 快乐 generals。

和 qbf 组队打 2v2 二十多把只赢了四把，这下菜完了。

DAY 0

报道日。

下午试机，先写了个 NTT，又写了个 SAM，然后写了个 MCMF，最后写了个可持久化平衡树，然而接下来三天一个也没用上。

晚上继续跟 qbf wtc gen。

DAY 1

晚上没睡好。

wtf 我直接做 cxy 旁边，那不得被炸心态了？

看到 T1，先快速想了个 O(2^mmn^2) 的做法，但感觉没前途。

然后想 2\times m\ge n 的时候怎么做，然后我也不知道我当时脑子里咋想的想了个 O(n^9) 的 dp，显然是没救的。

不过旁边的 cxy 似乎也没有动手，似乎今天的 T1 有点难度。

于是去看 T2，结果看了一眼发现会了。

打算写，但想到是个 DS，虽说细节不是非常多但写起来也是有点恶心的。

于是去看了眼，结果发现根本不可做。

于是开始写 T2，为了方便我直接写了个离线，然后线段树瞎二分一下，很快写完并一遍过。

然后去给 T1 写 O(2^mmn^2)，虽说只预算了 m=16 的数组但是直接把 n\le 20 给过了，拿下 45 分，令我大为震撼。

然后又去想 2\times m>n 怎么做，结果想了半天依旧没有任何进展。

然后去看了眼 T3，随便感受一下上下两部分凸包大小是 \log n 的，但并没有往类欧方面想。

想着怎么求凸包，想假了一万个做法，最后 G 了。

然后发现有 20 分 SB-tree 倍增的分，于是开写，很快拿下。

此时还剩下半个小时，我开始在 T1 的 n\le 30 和 T3 的 V\le 100 中反复横跳，最后自然是都没过。

然后被旁边的 cxy 90+100+0 爆杀了。

出场之后发现 T1 似乎过了一万个人，标算好像是 O(2^{n/3}nm^2)，我第一步就已经偏离标算了，看来我真没救了。

飞带长队全被 T1 创了，然后分数组成了一个等差数列。

然后我去问别人 2\times m>n 怎么做，别人都一脸震惊的看着我反问道：2m>n 的时候中间的数不是全是 c 吗？

于是我直接就红温了。

出题人讲 T3 的时候说第二个包没人过，不是哥们我怎么被忽略了。

晚上直接开 impart，听了很多 OIER 讲述他们身边的故事。

DAY 2

晚上睡得挺好。

点开题看完 T1，心想：只要取度数最大的点就行了，一看次数限制，刚好 \frac{n(n-1)}2，那不直接送分？哦，原来这个次数只有 1 分。

然后先想了一下存在一个点能到达所有点的情况咋做，发现很简单。

于是借鉴一下思路，先找到这么一个点，但此时可能会存在一些点连向这个个点，于是怎么办呢？

简单想了一下，好像递归处理就行了，复杂度毛估估一下好像是 O(n) 的，但常数有点大。

突然想着好像直接随机找一个点再这么做就行了，虽说好像会有波动，但我也不会证明波动的范围，想着要不写一写试一下，写了 399 \text{ byte} 交上去一遍通过，那我就不管了。

于是去看 T2，发现题目有点抽象，于是先去看 T3，刚开始以为答案下界是度数最大的点，结果直接被样例打脸，然后去想 checker 怎么写，然后也不会。然后手玩了一下菊花的情况，发现两次就行了。

然后手玩了一条链，然后手玩了菊花加链，手玩了毛毛虫，然后就会了。

于是速通了，此时还剩下 4h，怎么输。

去看 T2，想到把除了头尾以外度数为二的链缩起来，看作一个方点（如果两个度数 >2 的点之间没有连边也要连一个方点），这样就是圆方树了，于是 k=1 就 OK 了。

然后此时还没写代码，先去想了一想 k>1 怎么做，似乎是进行一些点的合并，但做起来很困难。

然后突然发现我似乎找到了一个反例，于是开始红温了。

此时还剩 3h，怎么输。

此时还剩 2h，怎么输。

此时还剩 1h，要输了。

先把链和菊花写了，然后发现我的反例好像并没有问题，于是直接红温了。

因为时间不够，最后只把 p=1,k=1 写了，直接破大防。

奋斗 4h T2，最后拿了 18 分。

不过最后好像也不是很靠后。方队好像爆炸了，不过想必他一定能翻盘，郑钧比我略高一点。

后来听说 T2 把圆方树的方点直接替换成一个团，然后性质就能更好的刻画了。

晚上和北京的学长一起吃饭，XC 直接在吃饭过程中鼓励大家谈 NPY，不是哥们……

DAY 3

早上 5:30 醒来，然后睡不着了。

今天居然坐 FXT 旁边，那我不得整场红温。

看完 T1 想了几个做法，发现都不太对。

于是去看了眼 T2，似乎有点难度。

看了眼 T3，似乎有点难度。

于是继续回来看 T1，想了一下还是不会。

于是又去看 T2，想了一会儿想到一个 O(n!) 的做法，随便优化一下是 O(4^n)，不知道能不能过于是决定写写看。

于是写写写，交上去一遍过，81\text{ms}。

又回去看 T1，觉得还不如去看 T3，于是想了一下，似乎找到独立集就好做了。

于是直接开随然后贪心找独立集，感受一下复杂度是 O(n\log n) 的，写完交上去一遍过。

然后又跟昨天一样，看着 T1 题面坐牢。

先想了个 n^6 的连续段 dp，不过转移有 50 种情况，直接写可能会让人直接红温。

过了若干小时侯开始想插入 dp，发现复杂度立马降到了 n^4，于是开写。

写完发现好像跑 n=500 也并不是很吃力，于是卡卡常，直接把 n=500 冲过去了。

有一说一卡常的过程还怪辛苦的。

于是 85+100+100 了，然而 zxx 今天直接 AK 了，他还是太牛了，不过对我这种人来说，285 足够了。

然后是日常讲题，好像 T1 还挺有难度的，集训队选手只有 le0n 做出来了。

DAY 4

凌晨室友还在别的房间打游戏，但我要赶飞机，必须得睡觉了。

于是给他发了个消息，结果一不小心发错人了，发给了 zxx。

早上在飞机场等飞机的时候觉得无聊打开了 tetr.io，结果直接被 XC 训斥了一番。

大概是训斥我带坏他人，说在他的影响下现在的人出来都不打游戏了，开始背单词了，我一看 wtc qbf 直接吓了一大跳，他们居然在背单词，完了这下 wtc qbf 都不能要了。

好在飞机上 XC 还是管不了我，于是提前登录 tetr.io，然后手机上打开 kindomrush 交替玩，似乎很爽。

部分题目题解

D1T3

我们的目标是找出上下部分的凸包，然后就随便做了。

考虑到找到左右对应的高度，然后发现可以进行类似欧几里得的操作使得斜率绝对值变小然后两维翻转递归处理，复杂度是 O(\log V) 的。

D2T2

考虑对于一棵树，生成一个图 G，G 中 x,y 有连边当且仅当树上 x,y 的简单路径的点除去 x,y 后剩余的度数都为 2（如果没有别的点了也算）。可以发现，一棵树小于等于另一棵树当且仅当这棵树的生成图的边集包含另一棵树的生成数的边集。

然后就是常规圆方树 dp 了（然而比较繁琐）。

D3T1

首先设 rB 表示左右分别是 r,b 并且右边比左边大的情况，Br,Rb,bR 同理。

我们要求的是 Rb-Br-rB，但注意到 rB+Rb=Br+bR，令 n=Rb+rB，则答案为 Rb-(n-bR)-(n-Rb)=Rb-n+bR-(n-rB)=bR-2(n-Rb)=bR-2rB。

考虑容斥，钦定 bR 出现了 x 次，rB 出现了 y 次，首先这个是独立的，所以可以求出来之后两维分别二项式反演得到。

考虑这个东西咋算，发现无论是 bR 还是 rB 本质上都是要求这一个小于下一个，这相当于是选出一些 RB 交替的链然后算贡献，但复杂度显然不可接受。

考虑换一个角度，我们发现我们只关注从大到小 dp 的时候只关注有多少个 r 后面目前没接 b，以及有多少个 b 后面没接 r，然后记录这两个状态，实际上就是当前 r 的数量减去钦定的 bR 的数量，于是可以得到一个 O(n^3) dp。

再进一步的，我们发现 bR 的数量和 rB 的数量其实是独立的，比如说算 bR 的时候只关注前面有多少个 r 和 bR，rB 同理，于是分别算出两个直接乘起来即可。

复杂度 O(n^2\log n)，可以获得 100 分。