专栏文章

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

CCircle_Table
P11752题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miq5a4un
此快照首次捕获于
2025/12/03 23:11
3 个月前
此快照最后确认于
2025/12/03 23:11
3 个月前
查看原文
题目传送门
看到这题的第一想法是用前缀和。用数组 aa 记录 a[i][j]a[i][j]左上方的钉子数量之和，先抽象出以下图形：
以 S(ABCD)S(ABCD)代表矩形 ABCDABCD 中的钉子数量。那么，在图中，如果需要求 S(PHCF)S(PHCF) ，易知：
S(PHCF)=S(ABCD)−S(EBHP)−S(GPDF)−S(AEPG)S(PHCF)=S(ABCD)-S(EBHP)-S(GPDF)-S(AEPG)
那么我们在上式中间两项分别加上 S(AEPG)S(AEPG)，得：
S(PHCF)=S(ABCD)−S(ABHG)−S(AEDF)+S(AEPG)S(PHCF)=S(ABCD)-S(ABHG)-S(AEDF)+S(AEPG)
译为中文，就是：左上角为 a[i1][j1]a[i_1][j_1] 右下角为 a[i2][j2]a[i_2][j_2] 的矩形中,有a[i2][j2]−a[i1−1][j2]−a[[i2][j1−1]+a[i1−1][j1−1]a[i_2][j_2]-a[i_1-1][j_2]-a[[i_2][j_1-1]+a[i_1-1][j_1-1] 个钉子。
然后就这么做了，于是 38分 。
发现超时的那个测试点全部是没钉子，回到样例 #1 后，发现只要钉子数不超过 1 ，那么挂的画在任何位置都可以。
显然，每行 mm 个中有 m+(m−1)+...+2+1=m(m+1)2m+(m-1)+...+2+1=\frac{m(m+1)}{2} 排列组合方式，每一列同理。
故一共有 m×(m+1)×n×(n+1)4\frac{m \times (m+1) \times n \times (n+1)}{4} 种排列组合方式
遂 AC 。
代码如下
CPP
#include <bits/stdc++.h>
#define ll long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
ll n,m,ans;
string s;
ll a[514][514];//存的是左上的钉子数
//思路是前缀和，但是这题用的二维
int main(){
	ios;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=1;j<=m;j++){
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
			if(s[j-1]=='#')a[i][j]++;
		}
	}
	if(a[n][m]<=1){
		cout<<n*m*(n+1)*(m+1)/4;
		return 0;
	}
	int f;
	for(int i1=1;i1<=n;i1++){
		for(int j1=1;j1<=m;j1++){
			for(int i2=i1;i2<=n;i2++){
				for(int j2=j1;j2<=m;j2++){
					f=a[i2][j2]-a[i1-1][j2]-a[i2][j1-1]+a[i1-1][j1-1];
					if(f<=1)ans++;
					if(f>1)break;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}
感谢阅读。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...