G5007 [GESP202406 五级] 黑白格 题解

知识点：二维枚举、双指针、滑动窗口。

解题思路

枚举矩形上下边界，累计各列黑格数，再对非负列和使用双指针，寻找黑格数至少k的最窄区间，更新面积最小值。

为什么正确

固定上下边界后，扩大右端不会减少黑格数，收缩左端可找到该右端最小合法宽度，枚举所有边界覆盖最优。

易错点

无法找到时按题目输出0；每次更换上边界要清空列累计。

复杂度

时间O(n²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,k;
    cin>>n>>m>>k;
    vector<string>a(n);
    for(auto &s:a)cin>>s;
    int ans=n*m+1;
    for(int x=0;x<n;x++) {
        vector<int>v(m);
        for(int y=x;y<n;y++) {
            for(int j=0;j<m;j++)v[j]+=a[y][j]-'0';
            int l=0,sum=0;
            for(int h=0;h<m;h++) {
                sum+=v[h];
                while(l<=h&&sum>=k) {
                    ans=min(ans,(y-x+1)*(h-l+1));
                    sum-=v[l++];
                }
            }
        }
    }
    cout<<(ans>n*m?0:ans);
}

说明

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