自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:00:35，当前版本为作者最后更新于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$ 分。