专栏文章

题解 P1369 【矩形】

P1369题解参与者 13已保存评论 16

文章操作

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

当前评论
16 条
当前快照
1 份
快照标识符
@mm97rwuw
此快照首次捕获于
2026/03/02 21:27
6 天前
此快照最后确认于
2026/03/02 21:27
6 天前
查看原文

P1369 【矩形】

这一题是可以用矩阵的前缀和写的,二维数组G[M][M]用来表示它左边和上边乃至左上方的点数,这么说可能很抽象,可以用下面的例子来表示这个思想:

输入

4
1 2
2 4
3 2
4 3

则现在的图像为:

0 1 0 0
0 0 0 1
0 1 0 0
0 0 1 0

转化成前缀矩形后图象为:

0 1 1 1
0 1 1 2
0 2 2 3
0 2 3 4

还有一个要注意的就是如何计算矩形边上的点数

一个点的前缀和,再减去矩形左下角左边一个点的前缀和,两次减法中都减去了矩形左上角左上方那个点的前缀和,所以要加上那个点的前缀和(具体如何实现需要自己动动脑子哦~ ..qwq,可以用我上面举得那个例子自己动笔画一下图哦~,语文不好请谅解QAQ)

-----------------------------------这里是代码分割线----------------------------

CPP
#include<bits/stdc++.h>			//蒟蒻常用的万能头文件 QAQ
using namespace std;
int n,G[1005][1005],maxx=-1,maxy=-1,x,y,maxn=0;
int fff(int i,int j,int ii,int jj){		//fff函数返回矩形左上角为(i,j)、右下角为(ii,jj)矩形内部(包括边上)的点数 
	if(i>=ii||j>=jj)					//在挖空矩形时可能矩形没有“心”,要判断一下,要返回0,因为此时挖不到东西 
		return 0;
	int sum;							
	sum=G[ii][jj]-G[i-1][jj]-G[ii][j-1]+G[i-1][j-1];	//sum用于计算当前矩形中的点数,具体如何实现看上面解析哦QAQ 
	return sum;											//返回矩形上的点数 
}

int main(){                    //这里是主函数qwq 
	scanf("%d",&n);
	for(int i=1;i<=n;i++){           //这里读入各个点的坐标,将其赋为1 
		scanf("%d%d",&x,&y);         //因为各点的横、纵坐标在1~100范围内,所以不会为负数 
		if(x>maxx)                   //但是如果每次都是100*100的找效率很慢 
			maxx=x;					 //所以用maxx、maxy表示此矩形做多能达到的地方 
		if(y>maxy)
			maxy=y;
		G[x][y]=1;
	}
	for(int i=1;i<=maxx;i++)		 //核心1:建立前缀和矩形的图像 
		for(int j=1;j<=maxy;j++)	 //此处用递推写的 qwq 
			G[i][j]=G[i-1][j]+G[i][j-1]-G[i-1][j-1]+G[i][j];		//表示(i,j)点上方、左方和左上方的点数 
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<=maxy;j++)
			for(int ii=2;ii<=maxx;ii++)				//矩形左上角坐标为(i,j),右下角坐标为(ii,jj) 
				for(int jj=2;jj<=maxy;jj++){		//暴力枚举一下所有可能生成的矩形 
					if(i>=ii||j>=jj)				//如果这个矩形不合法则continue 
						continue;
					int ans=fff(i,j,ii,jj);			//这里可以看一下上面fff函数的解析 
					ans-=fff(i+1,j+1,ii-1,jj-1);	//把矩形实心部分挖掉,ans变成四条边上的点数 
					maxn=max(maxn,ans);				//比较一下在矩形边上可以得到的最大点数 
			}
	printf("%d",maxn);					//输出可以得到的最多的点数 
	return 0;							//完美结束QWQ 
} 
不要复制代码哦,自己在不看我代码的情况打一遍,脑子中模拟一下是怎么样实现的,效果最佳哦qwq~

评论

16 条评论,欢迎与作者交流。

正在加载评论...