PKUWC2024 Day1 简要题解

· · 题解

T2

题面

给定长度为 n 的序列 f'，构造长度为 n-1 的非负整数序列 f 使得对于任意 1\le i\le n，都有 f'_i=\sum\limits_{j=1}^{i-1}d_{j,i-1}+\sum\limits_{j=i}^{n-1}d_{i,j}。其中 d_{i,j}=\min\limits_{k=i}^jf_k。

n\le 80,f'_i\le 10^8

题解

设 f 序列的最小值是 f_k，记其为 c（有多个则任意）。考虑将 f 中每个元素减去 c，此时 f' 发生的变化是 f' 中的每个元素都减去了 c\cdot(n-1)。

注意到此时有 f_k=0，观察 f' 的定义式，可以发现 f'_1\sim f'_k 此时只与 f_1\sim f_{k-1} 有关，f '_{k+1}\sim f'_n 只与 f_{k+1}\sim f_{n-1} 有关，因此可以使用区间 dp 解决。

具体地，令 dp[l][r][k] 表示：

转移时，先枚举最小值的位置 i，再枚举最小值的值 j，则 dp[l][r][k] 可行当且仅当 dp[l][i][k+j*(r-l)] 和 dp[i+1][r][k+j*(r-l)] 均可行。

此时的 dp 状态是 O(n^2V) 的，考虑优化。注意到我们如果给 dp[l][r][k] 对应区间中 f 的每个元素加 1，那么 f' 的每个元素会增加 r-l。这意味着，如果 dp[l][r][k] 可行，则 dp[l][r][k-(r-l)] 一定可行。

因此可以修改 dp 状态，令 dp_[l][r][k] 表示最大的 p\equiv k\pmod{r-l} 满足 dp[l][r][p] 可行但 dp[l][r][p+r-l] 不可行，则此时的 dp 状态降为 O(n^3)。

考虑转移，对于 dp[l][r][*]，枚举最小值位置 i，再枚举 i1 和 i2，分别对应 dp[l][i][i1] 和 dp[i+1][r][i2]。将 dp[l][i][i1] 和 dp[i+1][r][i2] 合并，即找到最小的 x 使得 x\equiv dp[l][i][i1]\pmod{l-i}，x\equiv dp[i+1][r][i2]\pmod{r-i-1}，以及 x\ge\max(dp[l][i][i1],dp[i+1][r][i2])。求 x 可以通过简易数论推导完成，此处略去。令 \operatorname{lcm}(i-l,r-i-1)=t，则对于所有的非负整数 k，dp[l][r][(x+t*k)%(r-l)] 会对 x+t*k 取 \max，使用同余最短路处理即可。总复杂度 O(n^5)。

T3

题面（先鸽了）

称原题面中满足点集 S 存在且 \sum a_i 最小的那棵唯一的树叫原树的最终形态。

动态修改 S_1,S_2，查询此时的最终形态是否有点 x 的点权为 z。

题解

观察一

对于给定的原树和集合 S，该树的最终形态可以通过以下过程得到：

本人水平有限，无法给出严谨证明，据说 Nz 有严谨证明。

直观理解：对于一个点，pop 该点大儿子产生的树必然不优于 pop 该点产生的树，pop 该点小儿子只是调换了操作顺序，仍然不优。

观察二

对于一个查询 x,z，当前集合 S 只有 x 子树中的点是有效的，其他点可以在 S 中任意增删而不改变答案。

证明：对观察一的过程进行一些思考即可得出，先鸽了。

观察三

对于一个查询 x,z，假设集合 S 只包含 x 子树中的点。如果对该树进行观察一的操作，但在 pop 完根之后就停止，不递归 pop 子树。此时的 x 的值即为最终形态的 x 的值。

证明：考虑在 pop 完根后停止时的状态，假设再对根进行一次 pop 后被弹出的点是 y。那么此时 y 到根的链均为不可 pop 状态，即 x 点权不再改变。

观察四

对于一个查询 x,z，假设集合 S 只包含 x 子树中的点。则 x 在最终形态下的点权，等于，对于所有 i\in S，将 S 变为 \{i\} 后的答案的 \max。其中答案指该情况下 x 在最终形态下的点权。

证明：考虑过程三中的 y，集合 S 的答案即为集合 \{y\} 的答案，其它 S 中元素对应的答案不会大于该值。

记 S=\{i\} 时点 x 的答案为 f_{x,i}。

做法

对于点 x 处的修改，在 x 的所有祖先处加入该修改（根据观察二，其他点不用考虑）。对于点 x 处的查询 x,z，考虑集合 S_1 中所有点 i 对应的 f_{x,i} 的最大值，令其为 t。如果 t\ge z 则无解。令 S_2 中 f_{x,i}=z 的点数为 p，f_{x,i}<z 的点数与无效点数（不在 x 子树中的点）的和为 q。则当 t=z 时，答案等于 2^{p+q}；当 t<z 时，答案等于 2^q(2^p-1)。

可以离线遍历 x，用堆维护 S_1，树状数组维护 S_2，复杂度 O(n\log^2n)。