首页 > 其他分享 >最大矩形(水题)合集???

最大矩形(水题)合集???

时间:2024-07-20 11:50:56浏览次数:14  
标签:水题 min int d% up && ans 矩形 合集

前言

刷水题,被水题刷。。。

悬线法要比单调栈好写的多。

P1387 最大正方形

悬线法
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if(a[i][j]) l[i][j]=l[i][j-1]+1;
		for(int j=m;j>=1;j--)
			if(a[i][j]) r[i][j]=r[i][j+1]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i>1&&a[i][j]&&a[i-1][j])
			{
				up[i][j]=up[i-1][j]+1;
				l[i][j]=min(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			ans=max(ans,min(up[i][j]+1,r[i][j]+l[i][j]-1));
		}
	}
	printf("%d\n",ans);
}

玉蟾宫

悬线法
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)	
		{
			char c; scanf(" %c",&c);
			a[i][j]=(c=='F');
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if(a[i][j]) l[i][j]=l[i][j-1]+1;
		for(int j=m;j>=1;j--)
			if(a[i][j]) r[i][j]=r[i][j+1]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i>1&&a[i][j]&&a[i-1][j])
			{
				l[i][j]=min(l[i-1][j],l[i][j]);
				r[i][j]=min(r[i-1][j],r[i][j]);
				up[i][j]=up[i-1][j]+1;
			}
			int a=r[i][j]+l[i][j]-1;
			ans=max(ans,a*(up[i][j]+1));
		}
	}
	printf("%d\n",ans*3);
	return 0;
}

巨大的牛棚Big Barn

悬线法
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			if(!a[i][j]) l[i][j]=l[i][j-1]+1;
		for(int j=n;j>=1;j--)
			if(!a[i][j]) r[i][j]=r[i][j+1]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i>1&&!a[i-1][j]&&!a[i][j])
			{
				up[i][j]=up[i-1][j]+1;
				l[i][j]=min(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			int k=min(r[i][j]+l[i][j]-1,up[i][j]+1);
			ans=max(ans,k);
		}
	}
	printf("%d\n",ans);
	return 0;
}

最大正方形II

注意初始化。

悬线法
#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
int n,m,a[N][N],l[N][N],r[N][N],up[N][N],ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]),l[i][j]=r[i][j]=1,up[i][j]=1;
	
	for(int i=1;i<=n;i++)	
	{
		for(int j=2;j<=m;j++)
		if(a[i][j]^a[i][j-1]) l[i][j]=l[i][j-1]+1;
		for(int j=m-1;j>=1;j--)
		if(a[i][j]^a[i][j+1]) r[i][j]=r[i][j+1]+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i>1&&(a[i][j]^a[i-1][j]))
			{
				up[i][j]=up[i-1][j]+1;
				l[i][j]=min(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			ans=max(ans,min(up[i][j],l[i][j]+r[i][j]-1));
		}
	}
	printf("%d\n",ans);
} 

棋盘制作

悬线法
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n,m,l[N][N],r[N][N],up[N][N],a[N][N];
int ans1,ans2;
int main()
{
	scanf("%d%d",&n,&m)	;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			l[i][j]=r[i][j]=j;
			up[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=2;j<=m;j++)
			if(a[i][j]!=a[i][j-1])
				l[i][j]=l[i][j-1];
		for(int j=m-1;j>=1;j--)
			if(a[i][j]!=a[i][j+1])
				r[i][j]=r[i][j+1];						
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i>1&&a[i-1][j]!=a[i][j])
			{
				l[i][j]=max(l[i-1][j],l[i][j]);
				r[i][j]=min(r[i-1][j],r[i][j]);
				up[i][j]=up[i-1][j]+1;
			}
			int a=r[i][j]-l[i][j]+1;
			int b=min(up[i][j],a);
			ans1=max(ans1,b*b);
			ans2=max(ans2,a*up[i][j]);
		}
	}
	printf("%d\n%d",ans1,ans2);
	return 0;
}

领地选择

二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m,c,a[N][N],x,y;
long long s[N][N],ans=-1e18;
int main()
{
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	for(int i=c;i<=n;i++)
	{
		for(int j=c;j<=m;j++)
		{
			if(s[i][j]-s[i-c][j]-s[i][j-c]+s[i-c][j-c]>ans)
			{
				ans=s[i][j]-s[i-c][j]-s[i][j-c]+s[i-c][j-c];
				x=i-c+1,y=j-c+1;
			}
		}
	}
	printf("%d %d\n",x,y);
} 

KUP-Plot purchase

乱入

单调栈
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
#define LL long long
int n,rb[N][N],lb[N][N],s[N][N];
LL a[N][N],k,sum[N][N];
bool mp[N][N];
int main()
{
//	freopen("matrix.in","r",stdin);
//	freopen("matrix.out","w",stdout);
	scanf("%lld%d",&k,&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&a[i][j]);
			if(a[i][j]>=k&&a[i][j]<=2ll*k)
			{
				printf("%d %d %d %d\n",j,i,j,i);
				return 0;
			}
			else if(a[i][j]<k) mp[i][j]=1;
			else if(a[i][j]>2*k) mp[i][j]=0;
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]) s[i][j]=s[i-1][j]+1;
			else s[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		stack<int> st;
		for(int j=1;j<=n+1;j++)
		{
			while(!st.empty()&&s[i][j]<s[i][st.top()])
			{
				rb[i][st.top()]=j-1;
				st.pop();
			}
			st.push(j);
		}
		while(!st.empty()) st.pop();
		for(int j=n;j>=0;j--)
		{
			while(!st.empty()&&s[i][j]<s[i][st.top()])
			{
				lb[i][st.top()]=j+1;
				st.pop();
			}
			st.push(j);
		}
		for(int j=1;j<=n;j++)
		{
			LL ss=sum[i][rb[i][j]]-sum[i-s[i][j]][rb[i][j]]-sum[i][lb[i][j]-1]+sum[i-s[i][j]][lb[i][j]-1];
			if(ss>=k)
			{
				if(ss<=2ll*k)
				{
					printf("%d %d %d %d\n",lb[i][j],i-s[i][j]+1,rb[i][j],i);
					return 0;
				}
				else
				{
					for(int h=lb[i][j]+1;h<=rb[i][j];h++)
					{
						int g=sum[i][h]-sum[i][lb[i][j]-1];
						if(g>=k&&g<=2*k) 
						{
							printf("%d %d %d %d\n",lb[i][j],i,h,i);
							return 0;
						}
					}
				}
			}
		}
	}
	printf("NIE\n");
	return 0;
}

标签:水题,min,int,d%,up,&&,ans,矩形,合集
From: https://www.cnblogs.com/ppllxx-9G/p/18312925

相关文章

  • Vue常用组件安装命令合集
    qs是一个流行的查询参数序列化和解析库。可以将一个普通的object序列化成一个查询字符串,或者反过来将一个查询字符串解析成一个object,帮助我们查询字符串解析和序列化字符串。npminstallqsnpminstallaxios-Selementuiui组件库npmielement-ui-Snpmielement-ui@2......
  • 【视频讲解】PCA主成分分析原理及R语言2实例合集|附代码数据
    原文链接:https://tecdat.cn/?p=37034原文出处:拓端数据部落公众号 分析师:RuoyiXu在数据分析的浩瀚宇宙中,我们时常面对多变量的数据海洋。这些变量虽然信息丰富,却也给处理带来了巨大挑战:工作量激增,而关键信息却可能淹没在繁杂的数据之中。为了有效减少指标数量同时尽可能保留原......
  • qt 创建一个可以拖拽的矩形,简单实践
    1.概要需求,一个可以拖拽的矩形,鼠标接近边线点击变成可拖拽形状。2.代码#include<QApplication>#include<QGraphicsView>#include<QGraphicsScene>#include<QGraphicsRectItem>#include<QMouseEvent>#include<QGraphicsSceneMouseEvent>#include<QLa......
  • 郑州轻工业大学zzulioj1071~1090合集
    郑州轻工业大学zzulioj1071~1090合集本人小趴菜一颗,写博客是为了监督自己的学习以及分享学习资源给需要的人,欢迎大家评论区指出问题。同时由于本人比较懒,注释就不再写了,当然一些自己经常犯迷糊的地方还是会标注的,大家有什么问题也可以指出来,大家一起学习进步。郑州轻......
  • LeetCode 363. 矩形区域不超过 K 的最大数值和
    363.矩形区域不超过K的最大数值和给你一个 mxn 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。题目数据保证总会存在一个数值和不超过 k 的矩形区域。示例1:输入:matrix=[[1,0,1],[0,-2,3]],k=2输出:2解释:蓝色边......
  • 【专题】2024年中国AIGC行业应用价值研究报告合集PDF分享(附原数据表)
    原文链接:https://tecdat.cn/?p=36570原文出处:拓端数据部落公众号大模型的发展标志着AIGC时代的来临,没有大模型支撑的AI已成为旧时代产物,缺乏竞争力。技术的突破始终是AI发展的关键,而商业应用则是推动其迅速发展的加速器。AI的持久繁荣依赖于其商业化的成功。展望2024年,我们有......
  • 调试合集(内含VS快捷键)
    目录一、BUG二、调试什么是调试?调试过程调试工具和技术三、VS常用快捷键四、VS中的常用调试功能(附快捷键)监视窗口自动窗口和局部变量内存窗口调用堆栈五、Debug实例求n的阶乘之和一、BUG在当今互联网盛行的时代无论你是否从事IT相关的行业或者学习,都应该听说过bug......
  • 闲话 718:1x2 骨牌的矩形覆盖计数
    注:以下的\(i\)不在下标时均代表虚数单位,\([n]=\{1,2,...,n\}\)。首先把格子当成点,连一个图出来:上下格子连向上的边,左右格子交替连向左/向右的边。这样求完美匹配方案数即可。这样假设搞出来的邻接矩阵是\(S\)。那么\(ans=Pf(S)=\sqrt{\detS}\)。通过对行的缩放操作(即初等变......
  • 暑期成绩表合集
    暑假集训CSP提高模拟1#使用者总分#1Start#2mine#3小凯的疑惑#4春节十二响1wang54321345451001001002GGrun22020100100-3xrlong21010100100030x7f2101001001003Ishar-zdl210-10010100......
  • leetcode 1459 矩形面积(postgresql)
    需求表:Points±--------------±--------+|ColumnName|Type|±--------------±--------+|id|int||x_value|int||y_value|int|±--------------±--------+id是该表主键每个点都用二维坐标(x_value,y_value)表示写一个SQL语句,报告由表......