首页 > 其他分享 >二维问题转化为一维问题

二维问题转化为一维问题

时间:2024-11-03 20:31:12浏览次数:1  
标签:cnt const get int 问题 二维 mp 一维

将二维的点赋予一个编号,转化为一维的问题,然后二维建边后进行最小生成树即可。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define fi first
#define se second
#define re register 
#define pir pair<int,int>
const int inf=1e9;
const int mod=998244353;
const int N=505;
using namespace std;

int n;
int mp[N][N];

struct ss{
	int u,v,w;
}a[N*N*4];

int get(int x,int y){
	return (x-1)*n+y;
}

bool cmp(ss g,ss h){
	return g.w<h.w;
}

int fa[N*N*4];
int siz[N*N*4];
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
} 

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
	
	for(int i=1;i<=n*n;i++){
		fa[i]=i;
		siz[i]=1; 
	}
	
	int cnt=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i>1){
				a[cnt]={get(i,j),get(i-1,j),abs(mp[i][j]-mp[i-1][j])}; 
				cnt++;
			}
			if(j>1){
				a[cnt]={get(i,j),get(i,j-1),abs(mp[i][j]-mp[i][j-1])}; 
				cnt++;
			}
			if(i<n){
				a[cnt]={get(i,j),get(i+1,j),abs(mp[i][j]-mp[i+1][j])}; 
				cnt++;
			}
			if(j<n){
				a[cnt]={get(i,j),get(i,j+1),abs(mp[i][j]-mp[i][j+1])}; 
				cnt++;
			}
		}
	}
	cnt--;
	sort(a+1,a+cnt+1,cmp);
	
	for(int i=1;i<=cnt;i++){
		int x=a[i].u,y=a[i].v;
		int w=a[i].w;
		x=find(x);
		y=find(y);
		if(x!=y){
			fa[x]=y;
			siz[y]+=siz[x];
			if(siz[y]>=(n*n+1)/2){
				cout<<w;
				return 0;
			}
		}
	}	
	
	return 0;
}

标签:cnt,const,get,int,问题,二维,mp,一维
From: https://www.cnblogs.com/sadlin/p/18523916

相关文章

  • 定时任务频繁插入数据导致锁表问题 -> 查询mysql进程
    场景定时任务每10秒插入一批数据,由于过去频繁导致锁表,从而无法再插入数据解决方案具体查看博客:https://blog.csdn.net/weberhuangxingbo/article/details/88709556数据库中执行sql:SELECT*FROMinformation_schema.innodb_trxSELECT*FROMinformation_schema.innodb_lo......
  • Python 一维列表基础语法
    【Python】【基础语法】【列表】引子创建一个列表获取数据的类型输出列表获取列表的长度获取元素的值获取元素的索引遍历列表练习引子列表(list)是python的基本数据类型之一。一维列表,常常被简称为列表,亦称为向量(vector)。六大基本数据类型数字型字符串str列表list元组......
  • C++的0.3问题
    在计算机中,我们都知道0.1+0.2是不等于0.3的那等于多少呢?我们使用程序测试一下#include<iomanip>intmain(){std::cout<<std::setprecision(18)<<0.1+0.2;return0;}//out:0.30000000000000004还有一个专门以此当域名的网站FloatingPointMath在十进制系统中,10的质......
  • K-th 问题的一般思路
    是在同一个情景下,求出前\(K\)类最小的方案价值。其可以等效转化为:将每一种方案视作一个状态,并通过状态之间的大小关系连边(严格),我们求出其拓扑序的前\(k\)个节点。笔者认为,所有的优化方案本质上都是在尽可能少的边数下保留这个拓扑结构,亦或者是利用隐式建图等技巧(因为事实......
  • 解决QT5升级Creator 14.x后出现launch debugger红色报错问题-OK
       QT5升级QtCreator14.x后出现launchdebugger红色报错,QT5C++项目可以编译运行,但无法调试运行。经试验:选择DesktopQT5.15.2MinGW64-bit调试运行无法启动,红色报错。增加安装QT6.7.3后,选择DesktopQT6.7.3MinGW64-bit可以成功进行调试运行。   经过多次测试,发......
  • 关于深度学习模型不收敛问题解决办法
    1.问题重现笔者在训练Vgg16网络时出现不收敛问题,具体描述为训练集准确率和测试集准确率一直稳定于某一值,如下图所示。2.可能的原因2.1数据问题噪声数据。不平衡的数据集、含有噪声或异常值的数据可能导致模型难以学习,尝试更换数据集,出现这种问题比较难办。数据预处理......
  • 2-petalinux 问题记录-VFS: Cannot open root device "mmcblk0p2" or unknown-block(1
    前言这个问题跟前面记录的问题0和1有点类似吧,也是需要再文件树里面增加一点配置。我手上是有两块zynq,一块是xczu2cg另一块是zynq7010,也就是zynqMP和zynq,在MPSOC里面SD启动需要注意这个SD卡的读写问题。原因SD卡有两种规格,一种大的,标准的SD卡;一种小的,MicroSD卡。如果是大SD卡......
  • 函数参数问题
    位置参数必选参数,必须按照位置次序,依次传入参数。defpower(x,n):s=1whilen>0:n-=1s=s*xreturns 默认参数给参数赋予值时,就是默认参数1、是必选参数在前,默认参数在后,否则Python的解释器会报错defpower(x,n=2):......
  • 《上古卷轴3:晨风》遭遇dll丢失问题:ffmpeg.dll丢失的多种解决策略
    《上古卷轴3:晨风》(TheElderScrollsIII:Morrowind)是一款经典的RPG游戏,但在运行过程中可能会遇到各种DLL文件丢失的问题,例如ffmpeg.dll。以下是一些解决ffmpeg.dll缺失问题的多种策略:重新安装游戏最直接的方法是重新安装游戏,确保所有文件都完整无缺。•彻底卸载:•在控制......
  • C++ 创建动态二维数组
    方法一:使用vector容器1.创建整数型二维数组先建列,再建行,先创建一个包含m个元素的向量a,再创建二维向量arr,通过push_back将一维向量作为行添加到二维向量中#include<iostream>#include<vector>usingnamespacestd;intmain(){ //创建一个包含m个元素,每个元素初始值为0......