CTT2024 游记

试机题和去年一样，20 分钟做完了。

测了下机子速度，发现大约是本地的 $\frac{2}{3}$。

写了网络流和 NTT 的板子。写了个拍子。

不知道还能干啥，坐牢。

开幕式。CCF 的老师拷打了去年国家队。

晚上摆。

早饭不错。

8:00 进场，先坐牢半小时。

然后先看 T1，乘积的期望咋求啊？

想了一会得到了一个 $O(2^mn^3m)$ 的做法。先去写，发现过了 $25$ 分。

然后思考怎么优化，优化不了一点。

先跑路，看 T2。看完会了。写完了。样例过了。交上去 WA 了。

然后写了个拍子，发现错了一堆。改改过了。

滚回去看 T1，发现 $2m>n$ 的时候可以 $O(poly(n))$。写完一测还是 $25$。

还剩一个小时的时候感觉该开 T3 了，看完没注意到斜率不超过 $1$，我是小丑。

想了半小时一分都不会。最后编了个 $V\le 100$ 的做法，根本过不去。

想了两个半小时不会 T1 第二个包，鉴定为若智。

$25+100+0=125$，集训队并列 rk19，但是一车人分数在这附近。

自闭了。下午摆摆摆，晚上摆摆摆。

还是先看 T1，先随便写了个做法拿了 $20$ 分。

然后有一个思路是每个点随机若干个其他点，不过看着就很没有前途所以没仔细想。

还是得增量构造，随便写了个做法交上去 $91$？？？

然后卡了一点常数。发现有个地方可以不用询问，直接假装限制最严格（因为一定有解）。交上去直接过了？？？

开 T2，分析了一下性质，后面的计数看着要猜结论，所以先写了 $10$ 分枚举 Prufer 序列的暴力，打算用来对拍。

先做 $p=0$。一开始以为直接和每个点度数有关，写了一下不对。然后尝试树形 DP，但是前前后后换了几个 DP 和背包的式子都不对，自闭。最后交了个菊花的 $4$ 分就不管了。

去看 T3，看完题感觉似乎每个叶子都要跑一遍 dfs 序，然后发现样例 2 就不对了，分析了一下似乎可以把一个叶子绑定在相邻的点上（前提是这个点度数 $>2$），写完意识到多个叶子可以一起绑，然后就过了。

回来做 T2 的 $p=1$。画了几棵树，发现 $k=1$ 的时候相当于把度数为 $2$ 的点拆出去。交了一下过了 $14$ 分，后面 $k>1$ 就不会做了，写了几个式子都不对，拍着拍着就结束了。

$100+28+100=228$，集训队并列 rk2？？？？？

下午摆摆摆，晚上摆摆摆。

先看 T1，想到了按值域从小到大插入，然后维护一下当前的连续段个数、$R>B$ 和 $R<B$ 个数以及总分差，就是 $O(n^5)$ 的。写出来发现连续段数和分数是没必要记录的，过了 $85$。

想了想 T1 正解，感觉很难优化，所以去开了 T2。感像是个搜索的剪枝优化，不过过了一会就想到了 $O(4^n)$ DP 做法。写完过了。没加记忆化调了 15min

看看 T3，怎么又是交互？想了想发现可以以重心为根算出每个点的子树大小，后面不知道咋做。然后思考了一下如果有一堆大小 $2$ 的点和一堆叶子怎么找匹配，发现是分治，那么原问题肯定也要分治。于是就想出来了。$11:30$ 左右过了。

2h 对 15pts，优势在我！然而并没想出来。

$85+100+100=285$，集训队并列 rk1？？？？？？？？？？

总分 rk6？？？？？？？？？？？？

下午加训 Phigros。晚上学习德扑。膜拜了去年 CTT 的 rk6。

跑路。感觉这次 CTT 好梦幻。