题解：P10719 [GESP202406 五级] 黑白格

cff_0102 · 2024-07-09 15:05:02 · 题解

注意到数据范围很小（n,m\le 100），所以可以直接枚举左上和右下的端点，计算出中间矩形中 1 的数量，然后比较并取最小值。

那么主要任务就变成快速计算两个点之间矩形中所有数字之和了。不难想到二维前缀和。每个点 (x,y) 存储的是 (1,1) 作为左上端点，(x,y) 作为右下端点，得到的矩形中所有数的和，这样就可以利用容斥原理线性计算出任意一个矩形中所有数的和。

下面的 AC 代码枚举的 (x_1,y_1) 实际上并不是矩形的左上端点 (x,y)，而是 (x-1,y-1)。因为数组在主函数外定义，所以不用担心第 0 行或第 0 列出现随机数的问题。

#include<iostream>
using namespace std;
bool a[114][514];// 存储输入
int b[1919][810];// 存储二维前缀和
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin>>c;
            a[i][j]=c-'0';
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];// 利用容斥原理计算出 b[i][j]
        }
    }
    int mn=0xcff0102;// 一个足够大的数
    for(int x1=0;x1<n;x1++){// 注意这里的范围 
        for(int y1=0;y1<m;y1++){// 注意这里的范围 
            for(int x2=x1;x2<=n;x2++){
                for(int y2=y1;y2<=m;y2++){
                    int tmp=b[x2][y2]-b[x2][y1]-b[x1][y2]+b[x1][y1];// 左上端点为 (x1+1,y1+1)，右上端点为 (x2+1,y2+1) 的矩形中 1 的数量
                    if(tmp>=k)mn=min(mn,(x2-x1)*(y2-y1));
                }
            }
        }
    }
    cout<<((mn==0xcff0102)?0:mn);// 注意判断无解
    return 0;
}

注意：bits/stdc++.h 头文件中包含函数 y1，类似的函数还有 y0，yn，j0，j1，jn。如果使用万能头文件，需要避免把变量名命名为这些名字。

吐槽一句：本题数据有点弱，我把循环中的 m 误写为 n 居然只 WA 了 4 个点，还能获得 60 分。