题目分析

给定 $S$ 个 $N$ 行的拼图块，每个拼图块宽度为 $W_i$，总宽度 $M = \sum W_i$。每个格子为黑色(1)或白色(0)。可以重新排列拼图块的顺序，求能得到的最大全白子矩形面积。

解题思路

核心思想

枚举矩形的高度区间 $[x, y]$，对于每个高度区间，计算最大的连续全白宽度，两者相乘得到面积。

关键技术

1. 二维前缀和：快速判断任意子矩形是否全白
2. 分块处理：按原始拼图块记录每块的前缀和后缀连续白列
3. 拼接优化：考虑不同块的组合形成更大的全白宽度
4. 扫描线：根据数据形状选择行优先或列优先扫描

算法步骤

1. 读入数据并建立二维数组
2. 计算二维前缀和
3. 根据数据形状选择扫描方向
4. 对每个高度区间计算最大全白宽度
5. 考虑拼图块之间的拼接可能性

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, s, w[N], st[N], ed[N];

// 将二维坐标转换为一维索引
int id(int x, int y) {
    if (x < 1 || y < 1)
        return 0;
    return x + (y - 1) * n;
}

// 计算子矩形中黑色格子数
int get(int x1, int y1, int x2, int y2) {
    return w[id(x2, y2)] - w[id(x1 - 1, y2)] - w[id(x2, y1 - 1)] + w[id(x1 - 1, y1 - 1)];
}

// 计算在行区间[x,y]内的最大全白矩形面积
int calc(int x, int y) {
    int l = 0;  // 完全全白的块的总宽度
    int ml = 0, sl = 0, mr = 0, sr = 0;  // 最大和次大的前缀、后缀白列长度
    int pml = 0, pmr = 0;  // 记录对应块的编号
    int ans = 0;
    
    // 扫描整个宽度找连续全白列
    int L = 1;
    for (int i = 1; i <= m; i++) {
        if (get(x, i, y, i))  // 如果这一列不是全白
            L = i + 1;
        else
            ans = max(ans, i - L + 1);
    }
    
    // 按拼图块处理
    for (int i = 1; i <= s; i++) {
        int nl = 0, nr = 0;  // 当前块的前缀和后缀白列长度
        
        // 计算前缀连续白列
        int j;
        for (j = st[i]; j <= ed[i]; j++) {
            if (get(x, j, y, j))  // 遇到黑色格子
                break;
        }
        nl = j - st[i];
        
        // 计算后缀连续白列
        for (j = ed[i]; j >= st[i]; j--) {
            if (get(x, j, y, j))  // 遇到黑色格子
                break;
        }
        nr = ed[i] - j;
        
        // 如果整个块都是白的
        if (nl == ed[i] - st[i] + 1) {
            l += nl;
        } else {
            // 更新最大和次大的前缀长度
            if (nl > ml) {
                sl = ml;
                ml = nl;
                pml = i;
            } else if (nl > sl) {
                sl = nl;
            }
            
            // 更新最大和次大的后缀长度
            if (nr > mr) {
                sr = mr;
                mr = nr;
                pmr = i;
            } else if (nr > sr) {
                sr = nr;
            }
        }
    }
    
    // 考虑拼接情况
    if (pml == pmr) {
        // 最大前缀和最大后缀来自同一块，取次优组合
        ans = max(ans, l + max(ml + sr, sl + mr));
    } else {
        // 来自不同块，可以直接拼接
        ans = max(ans, l + ml + mr);
    }
    
    // 返回面积
    return ans * (y - x + 1);
}

int Main() {
    memset(w, 0, sizeof(w));
    int ans = 0;
    char c;
    
    // 读入S和N
    scanf("%d%d", &s, &n);
    m = 0;  // 总列数
    
    // 读入每个拼图块
    for (int i = 1; i <= s; i++) {
        int ww;
        scanf("%d", &ww);  // 当前块宽度
        st[i] = m + 1;     // 起始列
        m += ww;           // 更新总列数
        ed[i] = m;         // 结束列
        
        // 读入当前块的矩阵
        for (int j = 1; j <= n; j++) {
            for (int k = st[i]; k <= ed[i]; k++) {
                cin >> c;
                w[id(j, k)] = c - '0';  // 存储到一维数组
            }
        }
    }
    
    // 计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            w[id(i, j)] += w[id(i - 1, j)] + w[id(i, j - 1)] - w[id(i - 1, j - 1)];
        }
    }
    
    // 根据数据形状选择扫描策略
    if (n < m) {
        // 行数较少，枚举所有行区间
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                ans = max(ans, calc(i, j));
            }
        }
    } else {
        // 列数较少，使用列扫描
        for (int j = 1; j <= m; j++) {
            int u = 1;  // 当前连续白行的起始行
            for (int i = 1; i <= n; i++) {
                if (get(i, j, i, j)) {  // 当前格子是黑色
                    u = i + 1;
                } else {
                    ans = max(ans, calc(u, i));
                }
            }
        }
    }
    
    printf("%d\n", ans);
    return 0;
}

int main() {
    int t;
    scanf("%d", &t);  // 测试数据组数
    
    while (t--) {
        Main();
    }
    
    return 0;
}

代码说明

关键函数

1. id(x, y): 将二维坐标映射到一维数组
2. get(x1, y1, x2, y2): 计算子矩形中黑色格子数
3. calc(x, y): 计算在行区间 $[x, y]$ 内的最大全白矩形面积

算法特点

1. 二维前缀和优化: 用 $O(1)$ 时间判断任意子矩形是否全白
2. 分块处理: 记录每块拼图的前缀和后缀白列信息
3. 智能拼接: 考虑不同块的最优组合方式
4. 自适应扫描: 根据数据形状选择最优扫描方向

复杂度分析

• 时间复杂度: 最坏 $O(n^2 \cdot m)$，但数据约束 $n \cdot \sum W_i \leq 10^5$ 保证可接受
• 空间复杂度: $O(n \cdot m)$