THUWC2024游记

RP ++

Day 1

T1 看了一会儿居然没思路。看到数据范围 \(n\le 15\) 想到可以状压，但怎么也想不出来，只好先打掉 \(m=16\) 和 \(n=4\) 两档暴力。

然后脑子好一点了，枚举前 \(i\) 个人确定了集合 \(S\)，发现要枚举子集，预处理了一下做到了 \(O(3^nm)\)，喜提 \(77\)。

然后脑子锈掉了。这个预处理可以不要预处理一个嘛，预处理 \(\max\) 然后不用枚举前 \(i\) 个人，直接 \(O(2^nm+3^n)\) 搞定了嘛。

T2 发现 \(m=10^9\)，由于最近矩阵的题做得比较多，一眼矩阵快速幂优化。

交换 \(i\) 次后 \(j\) 位置的期望可以枚举这一轮 \(j\) 和 \(k\) 交换，求其概率。记圆上两个位置距离为 \(d\)，发现概率只和 \(d\) 有关。

推了一下式子，然后半个小时之后发现式子推错了。

改对了，然后 \(O(n^3\log m)\) 加上 \(n=2048,m=1\) 的点喜提 \(70\)。

T3 有点 adhoc 了。前两个 Subtask 送分，但为啥我少了一分。

第三个 Subtask 试了很多方法，一开始一行一行二分，后来两行两行搞到 \(2\times 2\) 的，再后来先找最大行，最多就 \(43\) 分。知道应该是跟对角线有关，但不太会做，感觉 \(>2\) 的都是假的。

T4 写了个 \(15\) 分暴力，\(21\) 分的 Kruskal 重构树也没写。赛后听说 T4 LCT, T2 NTT。

pretest \(77+70+43+15=205\)，还好上 \(200\) 了。suisdavid \(100+52+53+36=241\)，比我高 \(36\) 分，差不多两个 Subtask。不知道过没过线，明天加油。