P10719 的题解

（一）

设 \(a_{x,y}\) 为从 \((1,1)(x,y)\) 矩形中的 \(1\) 的数量。

然后通过二位前缀和可以 \(O(1)\) 算。

注意到 \(1\le n,m \le 100\)。

先确定矩形右下角，对于左上角，先确定在哪一行，再二分在哪一列。

（二）

AC 代码。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
int n,m,k,a[110][110],res=1e9;
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%1d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	if(a[n][m]<k){
		puts("0");
		return 0;
	}//注意特判
	for(int x=1;x<=n;x++)
		for(int y=1;y<=m;y++){
			if(a[x][y]<k)continue;
			for(int i=1;i<=x;i++){
				int l=1,r=y,ans=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					if(a[x][y]+a[i-1][mid-1]-a[i-1][y]-a[x][mid-1]>=k)ans=mid,l=mid+1;
					else r=mid-1;
				}
				if(ans!=-1)res=min(res,(y-ans+1)*(x-i+1));
			}			
		}
	printf("%lld\n",res);
    return 0;
}