游记 PKUWC 2024

2024 北京大学全国优秀中学生信息学冬季体验营 1.25~1.27

重庆市育才中学校

1.26

13:00

网络卡顿挂了 5 分钟。但没事，因为在写 ntt 板子。还写挂了。然后看了题目，T1 应该可以做出来，T2 被吓到了，T3 可以想一下。T1 -> T2 -> T3。

T1 首先写了个区间 dp 交上去。目测是一个 dp 优化，把决策点输出一下看看。首先有结论是 L__ 或 __R 是先手必胜，其中 _ 是任何字符串。然后其它 R__L 的好像没啥规律。然后随机了几个数据，输出了一下先手必败的，发现 RLRLRLRL 是必败的，然后还有一个 RLRRLRLLRL 怎么也是合法的？怎么像括号匹配？真的！40 分钟就过了。

定理。将 R 视作左括号，L 视作右括号，则先手必败当且仅当字符串为空或括号序列合法。

证明。仿照 nim 游戏的思路，证明以下三点。

• 终态是必败态。
• 一个必败态，无论如何操作都是必胜态。你大概考虑一下，一个合法的前缀，刚好下一个字符是 R，切不到。
• 一个必胜态，存在方案能到达必败态。左括号看作 +1，右括号看作 -1，那么序列中如果存在前缀和是 -1，那么说明出现了右括号，直接保留右括号左边（L）的部分。否则将序列翻转，左右括号互换，必然有 -1，否则你这是合法括号串。

13:40

T3。首先怎么做原来的题目，怎么做啊，把询问一玩了一下，感觉影响很大，对整个堆影响很大（过程中几次把堆画成小根堆），所以肯定是要对一个点做分析。根据题目结论，堆形态是固定的，想象它为什么是固定的啊？

回想起堆排序干的事情，首先你把所有数扔一起建大根堆，然后拿出堆顶放在最后，pop 掉；拿出堆顶放在次后，pop 掉；……。pop 了 \(k\) 次以后，堆顶就是第 \(k\) 大。pop 和放一个 \(0\) 是一样的，pop 就是主动置零或者零从父亲下去。所以放 \(k\) 次零之后这个节点的值就是子树第 \(k\) 大，最大是第 \(0\) 大。

对于节点 \(u\)。当我已经通过某种方法确定了左右儿子后，那么我自己的值，则要大于两个儿子，而且尽量小，相当于两个儿子的 \(\max\) 在子树中的后继。一下就可以转移了！但是有一个问题就是 \(0\)，\(0\) 就是原神，如果将叶子的两个儿子当作 \(0\)，那么，当这个点不是关键点（\(\not \in S\)，下文同）时，这个点可以直接取 \(0\)，否则还是 \(0\) 的后继即最小值。其它情况都是 \(\max\) 的后继，分讨在这里严重的出现了！然后知道了询问一为什么不是 \(2^3\) 了。会了这个就可以配合爆搜 \(S\) 过掉 subtask 1, 2, 3 共 40 分。然后观察到一个点的最终值只和两个儿子有关，在修改 \(x\) 后暴力跳父亲到根就能过掉 subtask 5，\(O(n\log^2 n)\)，需要实现好一点，写个二分，有一点卡常。

15:00（大概）

急了，写了 T2 的 11 分暴力。

然后 subtask 4。回归到这个题原本的题意，要求 \(f[x]=z\)（\(f\) 是这样操作后的最终的值）的方案数，首先不在 \(x\) 子树内的点就线性乱搞。设计 dp 状态，暴力，\(dp(u, =z)\) 表示 \(f[x]=z\) 的方案数，根据 subtask 1, 2, 3, 5 的 dp 式子，需要满足 \(\max(f[2p], f[2p+1])\) 是 \(z\) 的前驱（\(z\) 的前驱记为 \(y\)），进一步发现是形如一个儿子固定 \(=y\)，另一个儿子 \(<y\)，\(y\) 在前者的子树中的东西。所以又会有 \(dp(u, <z)\) 表示 \(f[x]<z\) 的方案数，拆成两个儿子都 \(<y\) 的方案数的乘积。这里就有 \(0\) 的问题，太恶心了，忘了怎么分讨的，就是对着 \(z,y\) 是否为 \(0\) 以及是否关键是否叶子分类一大堆，还要注意不要重复递归保证复杂度正确。反正最后是写出来过了 subtask 4 的 20 分。注意有一个基本事实是如果 \(f[x]=0\)，那么整个子树的 \(f\) 都是 \(0\)。\(O(nq\log n)\) 可以通过。

后面是动态 dp 的东西，看上去并不好写。不写了。

16:00

怎么分数是 191 啊。看看 T2 性质？subtask 1 过掉以后就和值域没啥关系了，没有判断出来是个什么类型的题目。首先枚举大小关系，然后做高斯消元的时候有自由元，推了一下是 excrt 形式（\(a_ix\equiv b_i\pmod c_i\) 也是 excrt，望周知。如果 \(\gcd(a,c)\neq 1\)，记为 \(d\)，则变成 \((a_i/d)x\equiv b_i/d\pmod{c_i/d}\) 直接整除，\(b_i\) 不能除直接无解，然后就有逆元了，然后就 excrt 了，要最小的整数解）。谁写啊？而且还有相同的方程，矩阵直接不满秩，难受。这个问题的关键是我们要求整数解，不是有理数解，自由元可能通过调整可以调成整数，甚至不止一个自由元。

然后就沉默了。

17:00

\(100+11+80=191\)。好像还可以。

T2 大家都过了（好一个“大家”）。说什么 \(a\) 数组（原题的 \(f\)）区间加一，则 \(f\) 数组（原题的 \(f'\)）的那一个区间加上区间长度相关的东西，其它不确定。这个 \(n-1\) 是点边互换的。然后 dp，然后不知道怎么做。

大家 dà jiā
2. [great master]∶犹言大作家，大专家。　　艺苑品题有大家之目，自论诗者推李杜始。—— 王夫之《夕堂永日绪论外编》
5. [polymath]∶知识渊博者，博学的人。
——摘自百度百科 https://baike.baidu.com/item/大家/32746