自动搬运

查看原文

来自洛谷，原作者为

	niuniudundun 天禄

搬运于2025-08-24 23:09:58，当前版本为作者最后更新于2025-02-19 21:37:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

upd 2025/3/5：关于 $38$ 号数据，改一个 . 变成 #，导致做法卡掉，可以将代码中 s[n][m]==0 换成 s[n][m]<=1 即可。

题目大意

一个 $n$ 行 $m$ 列的 $c$ 中，有多少个矩形使得 # 数量 $\le 1$。

题目解法

暴力 $O(n^3m^3)$ 显然不能过。

一眼的前缀和（不会搜百度）。

思路如下：

如果 $c_{i,j}$ 是 # 则令 $s_{i,j}=1$。随后再跑一遍 $s$，让 $s_{i,j}$ 加上以 $(i,j)$ 为左下角的矩阵和 $s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}$。然后使用四重循环计算 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的和：$s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_{1}-1}$，如果和 $\le 1$ 则答案 $ans$ 加一。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='#'){
				s[i][j]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
		}
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=m;y1++){
			for(int x2=x1;x2<=n;x2++){
				for(int y2=y1;y2<=m;y2++){
					int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
					if(sum==1||sum==0){
						ans++;
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
3 3
...
...
..#
*/

然后你就得了 $38$ 分，link。

复杂度有 $O(nm+n^2m^2)$，对于 $5\times 10^2$ 的数据显然不行。

考虑优化。可以优化的有：

1. 将单独跑 $s$ 的与上面合并，减少 $O(nm)$ 复杂度。
2. 如果 $(x_1,y_1)$ 到 $(x_2,y_2)$ 和大于一，那么 $(x_1,y_1)$ 到 $(x_2,y_2+1)$、$(x_1,y_1)$ 到 $(x_2,y_2+2)$、$(x_1,y_1)$ 到 $(x_2,y_2+3)$ 等也大于一，可以结束循环，剪枝。

得到：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='#'){
				s[i][j]++;
			}
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
		}
	}	
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=m;y1++){
			for(int x2=x1;x2<=n;x2++){
				for(int y2=y1;y2<=m;y2++){
					int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
					if(sum==1||sum==0){
						ans++;
					}else{
						break;
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
3 3
...
...
..#
*/

可以得到 $38$ 的分数，只 TLE 一个点，link。

然后寄出一招——卡常小技巧：

1. 在变量前加 register。
2. cin、cout 改 scanf、printf。
3. 去掉多余变量。

然后得到：

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n,m;
int s[maxn][maxn];
int ans;
signed main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='#'){
				s[i][j]++;
			}
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
		}
	}	
	for(register int x1=1;x1<=n;x1++){
		for(register int y1=1;y1<=m;y1++){
			for(register int x2=x1;x2<=n;x2++){
				for(register int y2=y1;y2<=m;y2++){
					if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=1){
						ans++;
					}else{
						break;
					}
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
/*
3 3
...
...
..#
*/

可是问题没有解决，link。

当下载了数据点 #38 你会发现 $500\times 500$ 个 .，上面做法会被卡成 $O(n^2m^2)$。

可以加一个特判 $s_{n,m}=0$ 时，说明没有一个 .，可以动用数学：

我们可以将这个问题转成：

在一个 $n\times m$ 的矩阵中有多少个子矩阵。

一个矩阵由左上角和右下角组成，枚举左上角有 $nm$ 个情况，右下角有 $(n+1)(m+1)$ 个情况，随后再抛出重复的矩阵 ${\div}4$，然后就是正确答案 $\dfrac{nm(n+1)(m+1)}{4}$。具体的可以自己推一推。

总 AC 代码

#include<bits/stdc++.h>
using namespace std;
const long long maxn=501;
long long n,m,s[maxn][maxn],ans;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='#'){
				s[i][j]++;
			}
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
		}
	}
	if(s[n][m]==0){
		printf("%lld",n*m*(n+1)*(m+1)/4);
		return 0;
	}
	for(register int x1=1;x1<=n;x1++){
		for(register int y1=1;y1<=m;y1++){
			for(register int x2=x1;x2<=n;x2++){
				for(register int y2=y1;y2<=m;y2++){
					if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=1){
						ans++;
					}else{
						break;
					}
				}
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*
3 3
...
...
..#
*/