PKUWC2024

Terry2022 · 2024-01-28 11:03:45 · 生活·游记

PKUWC2024

因为【数据删除】的一些要求，所以凭空生成了一篇游记。

Day -11 ~ Day -1

七场模拟赛，中间 4 场连下 4 场，实力！

Day 0

复习模板，学习了多叉半在线卷积，实现了一下 \exp。

Day 1

早上报道，试机，二十核，16GB，\exp 1e6 只需要 1s，育才机子真nb，比【数据删除】快了将近一倍，育才食堂好评！

下午一试：

先花了 10 分钟把每一个题目都看了一遍，第一感觉是 \mathrm{T1} 结论，\mathrm{T2} 奇怪构造，看着像区间 \mathrm{dp}，\mathrm{T3} 性质加数据结构。

先开 \mathrm{T1}：

$T$ 组询问，$\sum |s|\le 10^6$。

考场大致是这样做 \mathrm{T1} 的：首先，如果开头是 \mathrm{L} 或结尾是 \mathrm{R}，此时先手必胜；否则 \mathrm{L/R} 会形成 \mathrm{R/L} 交替的连续段；到这里就不会了；后来想了一些归纳，就是这到此时可以进行操作的位置，发现这些位置在两个相邻 \mathrm{R/L} 段中呈现前缀或后缀，且 \mathrm{R/L} 只能选择一种，所以直接会缩掉一半的状态，只会迭代 O(\log n) 轮，直接写了 O(n\log n) 就过了。这里时间大概是 40 分钟，去上了一个厕所。

下考场过后才知道答案就是判断是否是括号序，感觉小丑了。

然后是 \mathrm{T2}，题意：

$n\le 80,1\le g_{i}\le 10^8$。

前 10 分钟看错题了：把 g 的定义看成了 \sum_{j=1}^{i-1}v(j,i)+\sum_{j=i}^{n-1}v(i,j)，然后发现可以直接 O(n) 构造，很迷惑，看样例才发现看错题了。

想了将近 30 分钟，没有正解思路，所以尝试拼暴力：有一个包是 n\le 50 且在有解的情况下存在 \max f\le 50 的解：从小到大枚举值域，设 f(l,r,s) 表示区间 [l,r]，外面的值对里面 [l,r] 的 g 的贡献均为 s，由于存在 \le 50 的解，所以 s 是 nV 级别，可以接受，转移直接枚举区间最小值以及位置就可以了，时间复杂度为 O(n^6)，但是常数很小，可以直接跑过这个包

前面的暴力分 n\le 14 应该可以直接搜笛卡尔树，但是有点难写，所以考虑乱搞：前面跑的慢的部分是枚举 \min，这样会导致状态数很大且时间与值域强相关；发现很多状态都是有解的，也就是说，直接顶到 \min 的上界是大概率有解的；所以将 \min 值的上界以及下界计算出来，然后让搜索时下界对上界 -10 取 \max，交上去直接把 n\le 14 的包冲过去了。

到这里大概是 120 分钟，由于还有一半的时间，所以决定对 \mathrm{T2} 继续乱搞一下：将 -10 改为 -4，把 n\le 50 的包冲过去了；然后我以为这个就是正解，直接把下界取到上界，交上去只有 n\le 80 的包 \mathrm{WA} 了，没有 \mathrm{T}；继续乱搞，改为在长度 >50 的时候取到上界 -1，否则直接取上界，然后就直接过了。

很激动阿，现在才 140 分钟，还剩 100 分钟做 \mathrm{T3}，又去上了厕所。

最后是 \mathrm{T3}：

$S$ 操作定义为：进行若干次操作，每次选择一个 $a_i\neq 0$，将其变为 $0$，然后调整使其仍然满足二叉堆；要求操作后最小化 $\sum a_i$，且 $S$ 中的每一个元素都不为 $0$。不加证明的给出 $S$ 操作的方式唯一。 $h\le 18,q\le 5\times 10^5$。

想了 30 分钟，打了一个暴力以及表，不会，拼暴力：考虑 s_2 恒为 \varnothing，此时只需要判断 s_1 是否合法。发现一个性质：a_x 只和 x 的子树有关；所以只要 x 子树中 \le y 的值保留下来合法，且 <y 的保留下来的值不合法，且 \le y 的值保留下来的情况下 a_x=y，则合法，然后就可以 O(\sum size_xh) 进行判断了，写出来大概结束前 20 分钟过了，不仅过了 h\le 9,q\le 5000 的包，后面一个特殊性质也过了。我直接 ？？，出题人的数据怕不是随的。

最后 20 分钟摆烂了，随手将 \mathrm{T3} 的暴力优化了一个常数，发现最后一个包貌似也可以跑。

下考场，260 挺好的，主要是 \mathrm{IOI} 赛制使得 \mathrm{T2} 可以进行乱搞，否则 \mathrm{T2} 不可能过。

先写了一个暴力，\mathrm{shell}(n)n!。可以过 n\le 8；打表，什么也没看出来。然后就开始坐牢，尝试 m=2，写了一个 O(n^3) 的 \mathrm{dp}，假了。这时候是 120 分钟，\mathrm{T2} 18\mathrm{pts}。

跳题，看 \mathrm{T3}。