专栏文章
题解 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 条评论,欢迎与作者交流。
正在加载评论...