G4009 [GESP202406 四级] 黑白方块 题解

知识点：二维枚举、前缀和、计数。

解题思路

黑格记1、白格记-1，枚举上下边界并压缩为列和。扫描前缀和，两个相同前缀之间的列段和为0，利用最早位置得到最大宽度。

为什么正确

矩形黑白数量相等等价于压缩区间和为0；保留同前缀最早下标使相同右端的宽度最大，枚举行区间覆盖全部矩形。

易错点

当前实现对每对边界重新累计行，不能误写成已优化的O(n²m)；空前缀下标设为-1。

复杂度

本代码时间O(n³m+n²m log m)，空间O(nm+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<string>a(n);
    for(auto &s:a)cin>>s;
    int ans=0;
    for(int x=0;x<n;x++)for(int y=x;y<n;y++) {
        vector<int>v(m);
        for(int i=x;i<=y;i++)for(int j=0;j<m;j++)v[j]+=a[i][j]=='1'?1:-1;
        map<int,int>pos;
        pos[0]=-1;
        int s=0;
        for(int j=0;j<m;j++) {
            s+=v[j];
            if(pos.count(s))ans=max(ans,(y-x+1)*(j-pos[s]));
            else pos[s]=j;
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。