几个题

· 浏览次数 : 0

小编点评

题目分析 PKUWC 2024 D1T2题中,通过构建笛卡尔树统计信息,可以使用区间DP来解决。将原序列f建立笛卡尔树,遍历树时会计算出f',即f数组中对应区间内的子树代表的区间最小值位置k。通过区间DP,设dp(l,r,x)表示[l,r]内所有f'全局减x后能否构造出对应的f。转移方程为dp(l,r,x)=∨k dp(l,k,x+f_k×(r-l))∧dp(k+1,r,x+f_k×(r-l))。最后枚举x和f_k,时间复杂度为O(n^2V^2)。但可以通过观察发现,对于每个x模(r-l),只需要知道x的最大值即可。 PKUWC 2024 D2T3题是一道套路题,操作差分下来,问题变成在线扫描n。可以考虑分块维护,支持单点修。询问时需要二分的块分配得好的话可以做到O(n√n+nlogn)。关于segt beats做法不会,不了解。 PKUSC 2024 D2T2题实际上不会出现一个人在排与不排之间反复横跳的情况,所以直接维护即可,过程比较无聊。 gym103260H Excluded Min题比较难,需要找到一个神仙trick才能解决。题面转化后可以发现,从大到小扫描x,每次看一下哪些询问满足条件,如果满足就记一下答案然后把它踢出去。这个过程不好维护,但是发现当[l1,r1]被[l2,r2]包含时,Ans([l1,r1])≤Ans([l2,r2])。每次看哪些询问满足条件时只需要看没被其他区间包含的询问区间即可。这个时候发现区间之间不包含可以直接线段树维护区间加全局max了。复杂度就是O(nlogn)。 总结 综上所述,通过构建笛卡尔树统计信息,使用区间DP解决PKUWC 2024 D1T2题;通过分块维护和单点修解决PKUWC 2024 D2T3题;直接维护线段树解决PKUSC 2024 D2T2题;找到一个神仙trick解决gym103260H Excluded Min题。

正文

PKUWC 2024 D1T2

很牛的题,想到了在笛卡尔树上统计,没想到可以做区间 dp。

把原序列 \(f\) 建一个笛卡尔树,会发现有 \(f'=\sum_{j} f_j\times(sz_j-1)\)。具体而言,遍历这棵笛卡尔树,当前节点的子树代表的区间为 \([l,r]\),最小值位置在 \(k\)。发现 \(f_k\)\([l,r]\) 里的每个 \(f'\) 分别有贡献 \(f_k\times(r-l)\)\([l,r]\) 里的 \(f'\) 全局减去这个贡献后,会发现 \(f'_{[l,k]}\) 会只与 \(f_{[l,k-1]}\) 有关,\(f'_{[k+1,r]}\) 会只与 \(f_{[k+1,r]}\) 有关,然后继续往下递归算贡献,一种合法的 \(f\) 构造方案会让所有 \(f'\) 都在遍历完毕后被减成 \(0\)

考虑将这棵笛卡尔树自下往上遍历,这是一个区间合并的过程,所以考虑区间 dp。设 \(dp(l,r,x)\) 表示 \([l,r]\) 内的所有 \(f'\) 全局减 \(x\) 后是否能构造出对应的 \(f\) 方案。转移也可以写出来:\(dp(l,r,x)=\bigvee_{k} dp(l,k,x+f_k\times (r-l)) \wedge dp(k+1,r,x+f_k\times (r-l))\)。需要枚举 \(x\)\(f_k\),时间复杂度 \(O(n^2V^2)\)

显然是过不去的,注意到 \(dp(l,r,x)\) 成立时,\(dp(l,r,x-(r-l))\) 时直接把 \(dp(l,r,x)\)\(f_k+1\) 代成 \(f_k\) 就成立,所以我们对于每个 \(x \bmod (r-l)\) 只需要知道 \(x\) 的最大值即可。不妨重设状态 \(dp(l,r,x)\) 表示 \([l,r]\) 内的所有 \(f'\) 全局减 \(y\equiv x\pmod {(r-l)}\) 后能构造出对应的 \(f\) 方案的最大 \(y\)。经过一些数论操作后可以做到 \(O(n^5)\),由于常数很小就过了。

PKUWC 2024 D2T3

套路题,在周末返校的路上想明白了。

操作差分下来,离线扫描 \(n\)。问题变成现在有操作序列,每次询问进行一个前缀的操作后(在原题中即在时间轴上的前缀),栈里某个区间的和。

对于一段操作序列的信息,只需要存进行完当前这一段的操作过后,这一段操作剩下的栈长啥样,以及需要删这一段操作的之前的操作的栈里多少个数。要维护一个 vector 一个 int,线段树维护有点过于复杂了,考虑分块。要支持单点修,每次单点修时暴力重构即可。询问时需要二分的块分配得好的话可以做到 \(O(n\sqrt n+n\log n)\)。关于 segt beats 做法,我不会。

PKUSC 2024 D2T2

扫描线,事实上并不会出现一个人在排与不排之间反复横跳的情况,所以直接维护即可,很没意思。

gym103260H Excluded Min

做不来啊,这个 trick 真是神仙。

题面转化就不说了。从大到小扫描 \(x\),每次看一下哪些询问满足条件,如果满足就记一下答案然后把它踢出去。

这个是不好维护的,然而发现当 \([l_1,r_1]\)\([l_2,r_2]\) 包含时,\(\mathrm{Ans}([l_1,r_1])\le \mathrm{Ans}([l_2,r_2])\)。每次看哪些询问满足条件时只需要看没被其他区间包含的询问区间即可。这个时候发现区间之间不包含可以直接线段树维护区间加全局 \(\max\) 了。复杂度就是 \(O(n\log n)\)

与几个题相似的内容: