noip2024游记

Day 0

赛前一天更新出了多人决斗，很好玩。

Day 1

比赛开始，先看 T1，这不是直接贪心就做完了？写，20min 通过样例。

看 T2，想到可以直接算概率，于是只用考虑相邻之间的影响，然后推推式子，30min 时过了小样例，样例 2 只有一个数是错的？

咋回事？

调了很久才发现我 (v-1)*\dots 的时候没强转 long long，v=2 刚好不会错。

哈哈哈，改完考试已经过去 1h 了。

然后双开 T3,T4。

T3 咋做？不会啊。

T4 咋做？不会啊。

冷静一下，T4 是 DS，先想 T4，想不出来的话之后再会做也写不完了，于是想，没思路，连 A 性质都不会。

于是再想 T3，发现其实就是把点看成方点，边看成圆点的圆方树，那么从一个点开始的答案就是 \prod_{x\in 方点} (deg_x-1)!。

再手模一些 k=2 的情况，发现好像可以容斥，斥掉对于两个起始点都可行的树。

画几个样例发现这个贡献其实是在两个点路径上的方点变成 (deg_x-2)。

然后大胆猜测选出来一个集合的点贡献是 \prod_{x\in 方点}(deg_x-x周围有几条路有标记点)。

当时感觉就很对啊。

于是就有一个 O(n^2) 的 dp 做法。

写写写。

还挺难写。。。

3h 时终于写完，欸我怎么过了 k=1,k=2 过不了其他？

这咋办？

瞪不出错误，只剩 1.5h 了，我 T4 一点没写，T3 只有个不知道对不对的东西，怎么办？？？

于是强迫自己静下心写一个 O(n\times 2^k) 的暴力。

怎么也这么难写？

写完调调过了 k=1,k=2。

欸我怎么还是过不去 k>2？

急了啊！！！

手画了点情况，发现如果一个方点出现“三叉”的情况，那么就没有 dfs 树能满足要求了，于是在暴力里面加了这个特判，瞬间就过了 n\le 500,k\le 8。

于是把正解里面一大堆没用的东西删掉，一下通过了所有大样例。此时只剩下 40min+ 了。

硬冲 T4 部分分，写了刚才就会的 O(n^2+nq) 暴力和 O(n\log n+q\log ^2n) 的 B 性质，此时剩下 20min。

哎呀 B 性质没有样例，太邪恶了。把小样例搞上去手搓几组询问，没问题就不管了。

努力想一下 A 性质咋做？

发现可以建一棵笛卡尔树，然后向下递归，单次询问复杂度 O(\frac{n}{k})。

于是直接考虑根号分治，k 大就往下递归，k 小就对于每种 k 再建立 ST 表区间查询。

然后狂暴写，最后 3min 写完过编，于是检查以下其他题的文件，交了这个题就没时间了。

我比赛时根本就没测样例 3，赛后待在那的时候，我测了一下，发现直接过样例了！！！

于是就估分 100+100+100+48。

Day 出分

实际得分 100+100+100+32。

不是 32 是怎么来的？？？

我挂了性质 B 应该是 36 才对啊。

于是自测，发现 A 性质全部 MLE 了。

？？？

哦原来我 k=1 递归到叶子会寄。

改了，过样例，怎么又全 WA 了？？？

这就是 T4 样例强度吗？