CTT 2024 游记

· · 个人记录

DAY -?

考完 noi 以后一直有点醉生梦死。从算法竞赛的视角来看，我只是打够了互测的分，在周末打把 ucup/cf/at，除此之外就没有训练了。noip 之前加训了一下，具体就是做了些 ucup 队友做的题。这次目标就是拼尽全力打，给自己的生涯一个体面的结尾吧。

DAY -1

到达北京，晚上住的酒店非常舒服。

投屏到电视上重温了一下天气之子。唉唉，感觉自己看不得这个，自己现在又胖又懒，已经和这样的青春少男少女不在一个频道了，是不会有人喜欢我这种看起来像中年大叔还不知道怎么正常交友的肥宅的。突然很想找回当初换座位刚好换到她旁边，那种纯真的心跳加速的感觉。但我找不回了阿，现在想起来只有惆怅了。只能说，我们直线，曾经交叉过了。

DAY 0

去官方的酒店报到，见到了偶像萃老师。

发现酒店没昨晚上的舒服，除了空间大一点以外，一无是处，设施看起来都有点旧了。

中午见到了偶像佳老师。和 cw 几个人一起吃了酒店对面的川菜馆子，味道还挺正的。

下午去试机，竟然是人生第一次做元旦激光炮，感觉自己打的比赛还是太少了。

题解：可以把三个序列看成无穷的序列。令 t=[\frac{k-2}{3}] ，我们找出 A_t,B_t,C_t 中最小的那个，不妨令 A_t 最小，可以发现至多有 3t 个数是比 A_t 小的。3t+1<k ，所以直接把 A_0 到 A_t 丢掉并令 k:=k-t-1 即可，k 每次会成为原来的 \frac{2}{3} ，复杂度即 O(\log k) 。

突然发现这是 OI 生涯倒数第二次试机了，接下来三天是倒数第五场、第四场、第三场比赛。心里交织着“一切就要结束了吗。”和“一切就要结束了！”的冲突的想法呢。

晚上怎么是吃盒饭。这盒饭也不好吃啊，还不如自己点的外卖。

发现偶像川哥也是志愿者。

晚上龟来房间撅人。一起玩了 gartic。

DAY 1

先摸了一遍。T1 是不像有多项式做法的数数，T2 是简单但要写很久的题，T3 什么有效的思路都没有。

先写了 T2 45。T1 摸出来 O(2^mpoly(n)) 的做法，写了一发竟然有 45。开始冲 T2 ，还剩 2h 的时候过了。再来摸 T1，摸出来了 m>\frac{n}{2} 时的 O(2^{n-m}poly(n)) 做法，但是不太想写，打算再想一想。想了很久也没有低于 O(2^\frac{n}{2}poly(n)) 的东西，于是开始写这个，还剩 10min 的时候过了。

60+100+0，rank 9，比自己预期的排名高很多。

交流了一下发现自己是小丑，m>\frac{n}{2} 的时候可以考虑 [n-m+1,m] 全都是 c 所以能直接挖掉，草。就只需要 m\le \frac{n}{2} 了。

听讲评，原来 m\geq \frac{n}{3} 的时候可以做到 O(poly(n)) ，感觉很牛啊。

T1 题意：

给定 n,m,c 和一个序列 p 满足 \sum p_i=1 。我们会对一个初始全 0 的序列 a 进行 c 次操作，每次会选择一个在 [1,n-m+1] 间的整数，其中 i 有 p_i 的概率被选中：选中 i 后让 a_i,a_{i+1},\dots,a_{i+m-1} 加 1 。求 \prod a 的期望。

做法： 首先是 $m$ 较小的做法：经过一定的拆贡献后其实可以看成是把 $n$ 个位置划分成若干集合，使得每个集合极差 $\le m$，给答案带来的系数只和每个集合的 $L,R$ 以及集合个数有关。于是从左往右 dp ，记下来当前已经出现过多少个 L，以及还没找到 R 的那些 L 构成的集合即可，可以发现那些既不是 L 也不是 R 的位置就不需要太关心它们的集合，转移时乘上还存在的 L 个数即可。复杂度 $O(2^mn^2m)$ 。 $m\geq \frac{n}{3}$ 时要抛掉拆贡献的想法，画个图，把 $n$ 个位置排成 $m$ 个一行。可以发现 $a_i+a_{i+m}+a_{i+2m}=c$ ，且通过 $a$ 序列是可以倒推出每种操作进行的次数，于是直接对着 $a$ 来 dp，设 $dp_{i,j,k}$ 是 $a_i=j,a_{2m+i}=k$ 的所有方案的系数和，转移就枚举 $j',k'$ 即可，大概需要乘上 $j'k'(c-j'-k')\frac{p_i^{j'-j}}{(j'-j)!}\frac{p_{n+i+2}^{k-k'}}{(k-k')!}$ 。这样是 $O(nc^4)$ 的，但其实可 以插值，于是复杂度 $O(n^6)$ 。 有点 emo。感觉我还是太平庸了，学 OI 这么多年始终没有真正的感受到水平的进步，从来都没有独立的做出过任何一道让自己觉得很牛的题。那些短暂的过题的自豪感基本都来源于“很多人没过我过了”，而不是真的觉得自己很厉害。 我感受到了和梦想中的自己的可悲的障壁。自己只是成为了套 trick 机器，而并没有成为算法竞赛领域大神呢。我迷茫了。 算了我已经退役了，这些都和我没有关系了来着，和解吧。 中午盒饭味道好转。晚饭是麦。晚上练习 generals。 **DAY 2** 摸了一遍题，T1 是神秘交互，T3 是神秘构造， 其中 T1 好像不是很难。T2 是神秘计数，没有成功简化这个条件啊，那这还咋做。 T1 想了半个小时终于会了个看起来能得很多分的做法，写一发直接过了。 去看 T3，一开始感觉根本做不了，发现 $n-1$ 有二十多分，乐。观察样例发现可以通过两个排列得到一条链的所有边，交上去有五十多分。然后想了很久感觉没啥进展，给 T2 补了点笨蛋分，回来再看了看，发现把构造稍微改一下可以得到一条毛毛虫的边（每一节有两个脚）。把这个加上之后也只有六十几分，之后就会不了新东西了。 100+11+69.04，rank37，还是符合预期的 rank，被狠狠区分了。T3 确实比我想的要简单一些，不少人过了呢，本来就不擅长做这种东西唉唉。 青鱼做了总榜以及每个人的夺胜赔率，目前竟然还排在 rank12。进前三十的概率 89%，但是进前四概率只有 9% ，属于是上不去下不来，整个人就卡在那里了。中午盒饭还行。晚饭是啥来着，忘记了。 意识到自己既不可能挨喷了也不可能进队，整个人就轻松多了！本该如此的，都是老年选手了为啥要在意这个结果呢。 听讲评， T3 确实不是我能会的题，和解了和解了。 T3 题意： 给定一棵无根树，你需要构造尽量少的排列，使得每个排列都是这棵树的一个 dfs 序，且通过它们可以唯一的确定出这棵树。得分计算方式是 $0.97^{与答案的差}$ 。 T3 做法： 先找一点答案的下界。不妨设第一个排列的根是 $1$ ，我们以 $1$ 为根来观察这棵树，现在可以看做要确定每个点的父亲。 最关键的性质：如果没有一个排列的根取在 $fa_x$ 子树内，那我们就不可能确定 $x$ 的父亲是不是 $fa_x$ 。不妨设 $1$ 不是叶子，除去菊花的情况，答案的下界就是删掉所有叶子后的叶子个数。 这个也是能取到的。首先我们设一个点的权值是它在第一个排列中的位置，那发现对于一个以 $x$ 为根的排列，取出那些权值为前缀最小的位置，也就得到了 $1$ 到 $x$ 的所有边。现在只需要思考怎么让那些叶子节点的父亲能唯一确定：由于已经可以推出挖掉叶子后树的形态，所以一个以 $x$ 为根的排列，我们先遍历其上挂的叶子。就可以确定这些叶子再 $x$ 子树内，但还不能确定 $x$ 的子树是个菊花的形态。那其实类似于菊花的做法，在那个 $1$ 为根的排列里把遍历顺序翻转即可。 哎，感觉自己还是太平庸了。构造交互什么的一直是迈不过去的大山，或者说应该是找性质的能力。算了我已经退役了。 晚上川哥带我和 251 去清华的台球馆，虽然还不知道怎么样能打的准，也一直在呲杆，但至少大力击飞的感觉还是很爽的！ 然后开始非常期待大学的生活了。是时候脱离只能不停学习和偷偷颓废的中学时代，学会怎么正大光明的玩了，成为一个正常的人类了！然后，也该找到一些算法竞赛以外的一些给自己的目标了。 **DAY 3** 摸了一遍题，发现 T1 一看就可以通过从小到大插入数，记几种空隙的数量做到 $O(n^4)$ 。T2 很神秘欸。T3 是神秘交互。 T1 想了很久也只会 $O(n^4)$ ，去看 T2。发现可以倒着来做，这样可以确定每个空隙的上下界，就有一个搜索的做法。仔细想了想发现了这个结构可以直接状压 dp，于是得到了 $O(4^n)$ 的做法，交上去发现直接通过，跑的飞快。 回来看 T1，仔细推了推式子，发现只需要记：左蓝右红且右大，以及左红右蓝且右大的位置个数即可。这样就是 $O(n^3)$ 的，成功获得 85 分。观察了这个时候的式子，感觉没有我能力范围内的 $O(n^2)$ ，就去做 T3 了。 此时只过去了 2h ，我发现自己好像要翻盘了。心跳开始砰砰的加速，我意识到此生仅有的进国家队的机会大概就在眼前，因为我有大量的时间在 T3 上拿到更高的分数。 摸了一个小时终于想到了 $O(n\log n)$ 次数的做法，大概就是先把 $n$ 个数都塞进 $S$，再通过 $2n$ 次操作找到重心，再清空 $S$ 只保留重心，通过 $2(n-1)$ 次操作找到与重心相连的点，现在只需要确定每个点在哪个子树就能点分治下去了，先把所有点加回来，对重心的儿子做一个分治，我们把 $[l,mid]$ 的儿子删掉，然后对剩下的点，判断把它删掉后 max siz 是否变化即可。做完之后还需要把所有点删掉。 可以发现这样操作次数大概有 10 倍的常数，但是当时我并没有仔细算过常数，以为写个对的东西就过了，于是开始提前开香槟，慢慢悠悠的写。 还剩 1h 的时候写完，交上去一看发现只有五十多分，顿时感觉自己成小丑了。接下来也一直没有想到更好的做法，只能对着原做法纳米推分，最后卡到了 68 分再也卡不动了，遗憾离场。 85+100+68.01，rank11，有一万个人把 T3 过了。有人 T1 $n^4$ 过 500 了，操蛋。 总榜上回到了 rank9，夺胜概率来到了 11%，但我觉得已经一点机会没有了，被大家在交互题上打出 gap 了，唉唉。饭吃的啥来着，只记得晚上有个特别阴间的肥牛饭了，不能说难吃，但是甜口的肥牛与我想象的酸辣味不同，这就很奇怪欸。 听讲评，发现 T1 原来是 $O(n^2\log n)$ 的，唉唉。出题人做法看起来有点麻烦。T2 被很多暴搜通过了，唉唉。T3 原来根本就不是点分治，唉唉。 T3 题意： 交互题，想知道一棵树的所有边。有一个初始为空的集合，每次可以在集合里加一个点/删一个点，操作后交互库会告诉你这个点集导出子图的最大连通块大小。最后需要报告这棵树的所有边。$n\le 10000$ ，次数要求 $6*10^5$ 。 T3 做法： 先把 $S$ 塞满，再在每个点一吐一吞找到重心，其实顺便求出了每个点在重心为根时的 siz。接下来把除了重心的点按 siz 从大到小排序，一个个删掉直到重心所在的 siz $<\frac{n}{2}$ 。把最后删的这个点加回去，现在其实其实树已经分成了两部分，就是与根联通的点，与剩下的点。我们只需要确认哪些点与根联通就可以分治下去了，方法也很简单，只需要通过一吐一吞观察 max siz 是否变化即可。 哎确实没想到只用分成两部分，唉唉。 T1 题意： 有 $n$ 个小球，第 $i$ 个球编号是 $i$ ，每个小球是红色/蓝色，颜色是给出的。需要把它们排成一个环，对于 $k\in [-n,n]$ ，需要求出 $\sum[相邻RB，R大，R在右]-\sum [相邻RB,B大]=k$ 的方案数。 T1 $O(n^3)$ 做法： 首先由于 $\sum[左R右B]=\sum [左B右R]=K$，所以 $k=\sum [左B右R，R大]-\sum[左B右R，B大]-\sum[左R右B，B大]=2\sum [左B右R，R大]-K-\sum[左R右B，B大])=\sum [左B右R，R大]-2\sum[左R右B,B大]$ 。 定义 $x=\sum [左R右B,R大],y=\sum [左R右B,B大]$ ，则 $k=x-2y$ 。考虑从小往大插入球，观察 $x,y$ 的变化。设当前插入的球前面已经有 $P$ 个 R，$Q$ 个 B，不妨设现在插入的是 R。 经过分类讨论发现 $Q-x-y$ 个位置能使 $x$ 加 $1$ ，$y$ 个位置能让 $y$ 减 $1$ ，$x$ 加 $1$ ，其余 $P+x$ 个位置 $x,y$ 不变。这样就得到了 $O(n^3)$ 的做法：状态中记录 $x,y$ 即可。 室友提前回去了，一个人玩到了很晚很晚。 。。。。怎么论文 ddl 是 23 号！操了，危机感又回来了。 **DAY 4** 是时候找到想做的事了