矩形的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求统计一个 $n \times n$ ~n \times n~ 的黑白矩阵中全为白格的矩形个数。核心解法是枚举矩形的上下两条边界，把「每一列在这两条边界之间是否全为白格」压缩成一个布尔数组并逐行增量维护，再把二维计数化归为一维的连续白段计数。

分析

核心观察

一个矩形由上下两条边界行与左右两条边界列唯一确定，它全为白格当且仅当其中的每个格子都是白格。固定行区间 $[t, b]$ ~[t, b]~ 之后，每一列能否被选为矩形的组成部分是彼此独立的：只要该列在 $t$ ~t~ 到 $b$ ~b~ 行之间没有出现黑格，它就可以参与；于是二维的判定退化为一维的连续段计数。

思路

枚举行区间的上边界 $t$ ~t~，让下边界 $b$ ~b~ 从 $t$ ~t~ 起逐行向下扩展。维护一个布尔数组，其中 $w_j$ ~w_j~ 表示第 $j$ ~j~ 列在第 $t$ ~t~ 行到第 $b$ ~b~ 行之间是否全为白格。当 $b$ ~b~ 从 $b-1$ ~b-1~ 下移到 $b$ ~b~ 时，只有新加入的这一行会带来信息，更新规则是：第 $b$ ~b~ 行第 $j$ ~j~ 列为黑格时把 $w_j$ ~w_j~ 置为假，否则 $w_j$ ~w_j~ 保持原值。这样每组上下边界只需 $O(n)$ ~O(n)~ 时间更新，而不必重新扫描整个行区间。

固定 $(t, b)$ ~(t, b)~ 后，左右边界可以在连续的全白列中自由选取。若某一段极长全白列的长度是 $len$ ~len~，则左右端点都取自该段的矩形共有

$\displaystyle \binom{len+1}{2} = \frac{len(len+1)}{2}$

个，相当于在 $len+1$ ~len+1~ 个列间隙中选两条分别作为左右边界。把数组里所有极长全白段按该式累加，就是行区间 $[t, b]$ ~[t, b]~ 贡献的矩形数。

正确性来自一一对应：每个全白矩形被且仅被一组 $(t, b, l, r)$ ~(t, b, l, r)~ 描述，程序枚举了全部 $(t, b)$ ~(t, b)~，并在每组 $(t, b)$ ~(t, b)~ 上通过极长连续段无重无漏地枚举全部 $(l, r)$ ~(l, r)~，因此累加值恰好是答案。

朴素做法枚举四个边界并对内部逐格检查，需要 $O(n^4)$ ~O(n^4)~ 甚至更高；上述做法把它降到 $O(n^3)$ ~O(n^3)~， $n = 150$ ~n = 150~ 时约为 $3.4 \times 10^6$ ~3.4 \times 10^6~ 次基本操作。另有基于悬线法（柱状图高度 + 单调栈）的 $O(n^2)$ ~O(n^2)~ 做法：把每列向上连续的白色格子数当作柱高，逐行统计以该行为底边的矩形数，此处不再展开。

具体示例

以样例 $n = 4$ ~n = 4~ 为例，矩阵的四行依次是 WWBW、BBWB、WBWW、WBWB。

取行区间为第 $1$ ~1~ 行到第 $1$ ~1~ 行（只有串 WWBW）：第 $3$ ~3~ 列是黑格，其余列全白，于是极长全白列段为 $[1,2]$ ~[1,2]~ 与 $[4,4]$ ~[4,4]~，长度分别是 $2$ ~2~ 与 $1$ ~1~，贡献 $\frac{2 \times 3}{2} + \frac{1 \times 2}{2} = 3 + 1 = 4$ 个矩形。

取行区间为第 $3$ ~3~ 行到第 $4$ ~4~ 行（串 WBWW 与 WBWB）：第 $2$ ~2~ 列两行都是黑格，第 $4$ ~4~ 列在第 $4$ ~4~ 行是黑格，只有第 $1$ ~1~ 列与第 $3$ ~3~ 列在两行之间全白，两段长度都是 $1$ ~1~，各贡献 $1$ ~1~ 个，合计 $2$ ~2~ 个。

全部 $\binom{5}{2} = 10$ ~\binom{5}{2} = 10~ 个行区间的贡献依次为 $4, 0, 0, 0, 1, 1, 1, 4, 2, 2$ ~4, 0, 0, 0, 1, 1, 1, 4, 2, 2~，总和 $15$ ~15~，与样例输出一致。

算法步骤

读入 n，再读入 $n$ ~n~ 行字符串存入 grid。
令计数变量 ans 为 $0$ ~0~。
枚举上边界 top：每开始一个新的 top，都把长度为 $n$ ~n~ 的布尔数组 white 全部置为真。
枚举下边界 bottom 从 top 到 $n-1$ ~n-1~：扫描第 bottom 行，凡是字符为 B 的列 j，把 white[j] 置为假。
线性扫描 white，用 run 累计当前连续为真的列数；每遇到假值或扫描到末尾时，把 run * (run + 1) / 2 累加进 ans，并把 run 清零。
输出 ans。

复杂度分析

时间： $O(n^3)$ ~O(n^3)~。行区间共 $\frac{n(n+1)}{2}$ ~\frac{n(n+1)}{2}~ 组，每组更新与扫描各 $O(n)$ ~O(n)~； $n = 150$ ~n = 150~ 时约 $3.4 \times 10^6$ ~3.4 \times 10^6~ 次操作。
空间： $O(n^2)$ ~O(n^2)~。矩阵本身占 $n^2$ ~n^2~ 个字符，工作数组 white 只需 $O(n)$ ~O(n)~。

实现注意事项

计数变量必须使用 $64$ ~64~ 位整型。全白 $150 \times 150$ ~150 \times 150~ 时答案为 $\binom{151}{2}^2 = 11325^2 = 128255625$ ，约 $1.28 \times 10^8$ ~1.28 \times 10^8~；该值虽仍落在 $32$ ~32~ 位有符号整数（约 $2.15 \times 10^9$ ~2.15 \times 10^9~）范围内，但已占去可观额度，一旦实现中出现任何中间量的放大——例如先把段长取平方再累加、或按面积而非个数统计——就会溢出。统一用 long long 计数可以彻底避开这类隐患。
段贡献公式先乘后除： $run \le n \le 150$ ~run \le n \le 150~，run * (run + 1) 最大为 $22650$ ~22650~，不会溢出，且两个相邻整数之积必为偶数，整除一定成立。
每开始一个新的上边界，都必须把 white 整体重置为真，否则会残留上一组行区间的信息。
更新时只把黑格所在的列置为假，不要拿当前整行覆盖 white，否则会丢掉更长行区间上累积的结果；等价地写作 $w_j \leftarrow w_j \wedge [\text{该格为白}]$ 。
输入每行是连续的 W / B 字符、之间没有空格，用 cin >> string 或按整行读入都可以，列数恰为 $n$ ~n~，无需再切分。
$n = 1$ ~n = 1~、全黑、全白等退化情形都被同一套逻辑覆盖：全黑时 run 恒为 $0$ ~0~，答案为 $0$ ~0~。

源代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// 枚举矩形的上下边界，维护每一列在这两条边界之间是否全为白格，
// 再对连续全白的列段计数：长度为 len 的段提供 len*(len+1)/2 个矩形。
// 时间 O(n^3)，空间 O(n^2)（矩阵存储）。
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    long long ans = 0;
    std::vector<char> white(n, 0);

    for (int top = 0; top < n; ++top) {
        std::fill(white.begin(), white.end(), 1);  // 尚未排除任何一列
        for (int bottom = top; bottom < n; ++bottom) {
            for (int j = 0; j < n; ++j) {
                if (grid[bottom][j] == 'B') {
                    white[j] = 0;  // 这一列在 [top, bottom] 内出现黑格
                }
            }

            long long run = 0;
            for (int j = 0; j < n; ++j) {
                if (white[j]) {
                    ++run;
                } else {
                    ans += run * (run + 1) / 2;
                    run = 0;
                }
            }
            ans += run * (run + 1) / 2;
        }
    }

    std::cout << ans << '\n';
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    grid = [data[1 + i].decode() for i in range(n)]

    ans = 0
    for top in range(n):
        white = [True] * n
        for bottom in range(top, n):
            row = grid[bottom]
            for j in range(n):
                if row[j] == 'B':
                    white[j] = False

            run = 0
            for j in range(n):
                if white[j]:
                    run += 1
                else:
                    ans += run * (run + 1) // 2
                    run = 0
            ans += run * (run + 1) // 2

    sys.stdout.write(str(ans) + "\n")


main()

目前没有评论。