2026 多校 杂题选记

发表于 分类于

吃到大份了．

牛客多校 3 I

发现相邻交换和包含 1,n1, n 的交换的 Δ\Delta 形式复杂，所以先将形如 (1,i),(i,n),(i,i+1)(1, i), (i, n), (i, i + 1) 的交换贡献到答案上．然后考虑 1<j<i<n1 < j < i < n 且 i−j>1i - j > 1 的交换 (i,j)(i, j) 的贡献．

考察交换后序列价值和原序列价值的差 Δ\Delta．记 li=ai−1,ri=ai+1,oi=∣li−ai∣+∣ri−ai∣l_i = a_{i - 1}, r_i = a_{i + 1}, o_i = |l_i - a_i| + |r_i - a_i|，有

Δ=∣li−aj∣+∣ri−aj∣+∣lj−ai∣+∣rj−ai∣−oi−oj\Delta = |l_i - a_j| + |r_i - a_j| + |l_j - a_i| + |r_j - a_i| - o_i - o_j

考虑枚举绝对值的符号，有

Δ=max⁡s1,s2,s3,s4∈{−1,1}[s1(li−aj)+s2(ri−aj)+s3(lj−ai)+s4(rj−ai)−oi−oj]\Delta = \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [s_1(l_i - a_j) + s_2(r_i - a_j) + s_3(l_j - a_i) + s_4(r_j - a_i) - o_i - o_j]

分离 ii 和 jj，有

Δ=max⁡s1,s2,s3,s4∈{−1,1}[(s1li+s2ri−s3ai−s4ai−oi)+(s3lj+s4rj−s1aj−s2aj−oj)]\Delta = \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]

先枚举 ii，考虑如何计算最大的 Δ\Delta．有

Δmax=max⁡1<j<i{max⁡s1,s2,s3,s4∈{−1,1}[(s1li+s2ri−s3ai−s4ai−oi)+(s3lj+s4rj−s1aj−s2aj−oj)]}=max⁡s1,s2,s3,s4∈{−1,1}{max⁡1<j<i[(s1li+s2ri−s3ai−s4ai−oi)+(s3lj+s4rj−s1aj−s2aj−oj)]}=max⁡s1,s2,s3,s4∈{−1,1}[(s1li+s2ri−s3ai−s4ai−oi)+max⁡1<j<i(s3lj+s4rj−s1aj−s2aj−oj)]\begin{aligned} \Delta_{\mathrm{max}} &= \max_{1 < j < i} \{\max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]\} \\ &= \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} \{\max_{1 < j < i} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]\} \\ &= \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + \max_{1 < j < i} (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)] \end{aligned}

枚举 s1,s2,s3,s4s_1, s_2, s_3, s_4 的所有可能取值，对每个取值预处理第二项即可快速计算．

牛客多校 3 J

我操我真想不到这个．

考察如何确定一个点 uu 的父亲．若 uu 没有任何被要求的祖先，直接连到 11 上显然是最优的．考察 uu 的祖先约束集合 ancu\mathrm{anc}_u，一个简单的想法是直接连到 arg max⁡v∈ancudepv\argmax_{v \in \mathrm{anc}_u} \mathrm{dep}_v 上．不妨设该策略选择的点为 pup_u，若存在 ww 满足 u∈ancwu \in \mathrm{anc}_w，且存在 x∈ancw,x∉ancu,deppu<depx<depux \in \mathrm{anc}_w, x \not \in \mathrm{anc}_u, \mathrm{dep}_{p_u} < \mathrm{dep}_x < \mathrm{dep}_u，问题就出现了：uu 的父亲至少应该是 xx，不然 ww 的祖先约束无法被全部满足．

这启发我们按照深度降序确定节点在新树中的父亲．对于叶子节点 uu，此问题不存在，直接选择 ancu\mathrm{anc}_u 中深度最深的点 vv．选择后，为使 uu 的其他祖先约束被满足，这些点必须成为 vv 的祖先，即将 ancu\mathrm{anc}_u 中除 vv 外的点加入 ancv\mathrm{anc}_v．写一个启发式合并堆模拟该过程即可．