【ZROI】提高组Day9题解

发表于

【ZROI】提高组Day9题解

A

和前几天刚做过的一道题【ZJOI2012】小蓝的朋友差不多，只不过换了换数据范围。

先考虑一个暴力的做法：枚举合法矩形的下边界 $a$，再枚举左右边界 $l, r$，则上边界的取值范围是 $(\max_a(l, r), a]$，其中 $\max_a(l, r)$ 表示只考虑横坐标小于等于 $a$ 的点时，第 $l$ 到第 $r$ 列最大的横坐标是多少。此时对答案的贡献是 $a - \max_a(l, r)$。

考虑如何优化这个暴力。

$a$ 可以先拿出来一起进行计算：

$$\sum_{i=1}^n{i \sum_{l=1}^m\sum_{r=l}^m1} = \sum_{i=1}^n{i\sum_{l=1}^m{m-l+1} = \sum_{i=1}^n{i \sum_{l=1}^ml = \frac{n(n+1)m(m+1)}{4}}}$$

现在只需要考虑后面如何计算。

可以考虑对于每一列，只保留横坐标最大的点，然后考虑有多少矩形上边界被这个位置限制住。即固定一列，求左右第一个更大的数的位置，这个可以用单调栈实现，排序之后每次加入横坐标相等的点即可。注意实现的时候为了不漏，应该一边是大于，另一边是大于等于。

最后需要解决的问题是坐标的取值范围非常大的问题。显然只关心有点的那些列，因此这个问题可以通过离散化解决。

复杂度瓶颈在于单调栈，复杂度为 $O(k^2)$。

B

设 $f_{l, r}$ 表示把区间 $[l, r]$ 的矩形乘起来的最小代价，转移中间点即可做到 $O(n^3)$，已经可以通过本题。套用四边形不等式可以优化到 $O(n^2)$。

通过一些神奇转化可以做到 $O(n \log n)$，笔者并不会。

这里还是留一份论文链接吧：

Part1

Part2

C

状态设计比较套路的一道树形 $dp$，但是转移较多，需要大力分类讨论。

设 $f_{i, j=0/1, k=0/1}$ 表示以 $i$ 为根的子树，颜色变成 $j$，存在不存在一条连到根的反色的链时的最小步数。

设 $i$ 的颜色为 $c$，$r=c\ \text{xor} 1$。

$ss$ 表示子树颜色都为 $c$ 的代价和。

$s_{j=0, 1, 2}$ 表示子树中颜色为 $r$，且有 $i$ 条反色的链的代价。

转移见代码。

1
2
3
4
5
6
7
8
9
10
11
for (auto v: E[u]) if (v != pre) {
        dfs(v, u);
        ss += f[v][c][0];
        s[2] = std::min(s[1] + f[v][r][1], s[2] + f[v][r][0]);
        s[1] = std::min(s[0] + f[v][r][1], s[1] + f[v][r][0]);
        s[0] += f[v][r][0];
    }
f[u][c][0] = std::min(ss, 2 + std::min(s[2], std::min(s[1], s[0])));
f[u][c][1] = 1 + std::min(s[1], s[0]);
f[u][r][0] = 1 + std::min(ss, std::min(s[2], std::min(s[1], s[0])));
f[u][r][1] = f[u][c][1] - 1;