NOIP2024 随便写写

· · 生活·游记

8:26 才进考场，结果是没听到解压密码，还没发到草稿纸，太抽象了。

开题先看 A ，虽然感觉不太会，但是看大家都开始敲代码了，我也开始写了。先用 5min 左右调环境。A 一眼先分段，然后能相等就相等，然后不会了。想了会发现贪心方案不多，觉得一段匹配一部分后留给以后的总数固定，0 个数是一段区间，合并就直接暴力。大概在 9:20 过了大样例，然后去了厕所，回来时候发现贪心方案是唯一的，感觉自己很蠢。

然后看了 B ，发现随便做一下就好了，9:30 左右过了大样例。心想还好 B 简单，也是在 60min 解决了签到，前期打的还行。

看了 C ，发现树形态只和第一次进入和最后出去的边有关，那么感受一下就是 k\prod (deg_i-1)! 减去什么东西。

想了一会儿去看 D 了。想了会了若干 O(n\log^2n) ，发现了若干结论，最后卡在了求出有用区间后要三维偏序，结果发现直接按长度扫描线就好了，有用区间是互不相交的，于是开写。大概 10:10 左右过了大样例。

然后去看 C ，发现直接钦定两起点得到的树相等，只要让中间没有出发点，容斥系数就是对的。然后发现可能有很多个连通块，那么容斥系数需要复杂一点，写了写发现过不了样例。结果想了一下发现根本不可能，相等一定在一条链上，那么随便 DP 即可。于是 11:30 过了大样例。

最后拍了 A 和 D ，然后玩了下 Arbiter ，想试试用这个测大样例，但是怎么也搞不好，直到结束。

感觉可能这场 A 对我来说是最难的，或者说其实是最绝望的，好在最后过了。最后出来感觉所有人都 AK 了，结果 AK 的人意外的少啊。

突然发现我没看过任何一个题的部分分？我也是神人，高二还敢这么打。