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,再枚举 i1i2,分别对应 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,则对于所有的非负整数 kdp[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_2f_{x,i}=z 的点数为 pf_{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)