Cut a Strip
题目简述: 给定 $n \times m$ 的矩阵 $a[][]$, 要求选择一个 $x \times 1(1 \leq x \leq k)$ 的 (连续) 子矩阵并清零后, 找到最大和的 (连续) 子矩阵
数据范围:$1 \leq n, m, k \leq 380$
题解:
子矩阵可以用四个参数表示 $(x_1, y_1, x_2, y_2)$, 其中 $(x_1, y_1)$ 是其左上角,$(x_2, y_2)$ 是其右上角
我们枚举子矩阵的 $y_1$ 和 $y_2(1 \leq y_1 \leq y_2 \leq m)$, 令 $c[i] = a[i][y_1]+\dots+a[i][y_2](1 \leq i \leq n)$
接着枚举子矩阵经过的某行 $x(1 \leq x \leq n)$, 则经过第 $x$ 行的子矩阵的最大和为
($c[1], \dots, c[x-1]$ 的最大后缀和)+($c[x+1], \dots, c[n]$ 的最大前缀和)+(把 $a[x][y_1], \dots, a[x][y_2]$ 中连续不超过 $k$ 个值清零的最大和)
前两个可以预处理得到, 关键在于第三个部分
注意到
(把 $a[x][y_1], \dots, a[x][y_2]$ 中连续不超过 $k$ 个值清零的最大和)=c[x]-($a[x][y_1], \dots, a[x][y_2]$ 中连续不超过 $k$ 个的最小和)
后者可以利用单调队列求得
时间复杂度 $O(n^3)$
注: 单调队列求数组 $a[1], \dots, a[n]$ 的长度不超过 $k$ 的连续子数组最小和令 $s[i] = a[1]+\dots+a[i]$ 表示其前缀和
即需依次对每个 $1 \leq i \leq n$, 求
$$ \min_{i-k \leq j \leq i} \{s[i]-s[j]\} = s[i] - \max_{i-k \leq j \leq i} \{s[j]\} $$
从而维护区间 $[i-k, i]$ 的最大值即可
Expert Computation
题目简述: 依次给出 $n$ 个二维点 $(x[i], y[i])$ 以及 $1 \leq z[i] \leq i$, 且 $x[i] < x[i+1]$ 严格递增强制在线依次回答
$$ \max_{1 \leq j \leq z[i]} {x[j]*y[i]-y[j]*x[i]} $$
数据范围:$1 \leq n \leq 1,000,000.$
题解:
先不考虑强制在线, 即允许离线回答, 则可把询问按照 $z[i]$ 从小到大排序, 然后依次维护下凸壳, 回答询问时, 由于下凸壳斜率单调递增, 二分答案即可
若强制在线, 则可持久化维护下凸壳即可但 $n$ 很大, 常数以及空间复杂度承受不了, 只能另辟蹊径
注意到 $x[i]$ 严格单调增, 故所维护的下凸壳的各个历史版本 (history version) 中, 每个点 (如果这个点在当前下凸壳上的话) 在下凸壳上的前驱是固定的
对每个点, 倍增地维护这个点的 $2^k$ 次前驱, 如 $pre[i][k]$ 就可表示第 $i$ 个点的 $2^k$ 次前驱
二分答案时利用倍增特点, 可在 $O(\log n)$ 复杂度内解决
时间空间复杂度均为 $O(n \log n)$
来源: http://www.bubuko.com/infodetail-2496793.html