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

加一。

代码：

CPP

#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

的数据显然不行。

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

将单独跑 $s$ 的与上面合并，减少 $O(nm)$ 复杂度。
如果 $(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)$ 等也大于一，可以结束循环，剪枝。

得到：

CPP

#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。

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

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

然后得到：

CPP

#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 代码

CPP

#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
...
...
..#
*/

题解：P11752 [COCI 2024/2025 #5] 挂画 / Zid

文章操作

题目大意

题目解法

总 AC 代码

相关推荐

评论

题解：P11752 [COCI 2024/2025 #5] 挂画 / Zid