[蓝桥杯][2019年第十届真题]修改数组_深夜面包的博客-程序员宅基地

技术标签: 题解  并查集  蓝桥杯  

题目链接:修改数组



解题思路:用并查集思路,如果一个数的父节点就是当前数的位置,如果标记下一个数值一样的数的位置+1

#include<bits/stdc++.h>
#define x first
#define y second
#define mem1(h) memset(h,-1,sizeof h)
#define mem0(h) memset(h,0,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
    
	inline LL read(){
    
		LL o=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}
		while(c>='0'&&c<='9'){
    o=o*10+c-'0';c=getchar();}
		return o*f;
	}
}using namespace IO;
//#############以上是自定义技巧(可忽略)########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+7,P=131;
int n;
int fa[N];
int find(int x){
    
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    
	cin>>n;
	for(int i=0;i<=n;i++)fa[i]=i;
	for(int x,i=1;i<=n;i++){
    
		scanf("%d",&x);
		x=find(x);
		printf("%d ",x);
		fa[x]=x+1;
	}
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43738764/article/details/109100414

智能推荐

搭建STM32开发环境——STM32CubeMX,Keil5实现流水灯_xxx-Tention的博客-程序员宅基地_keil5 stm32cubemx

一、实验工具STMCubeMX,用来生成代码 keil5,编译代码生成hex文件 flymcu,将代码烧录到板子里 板子为STM32103C8二、STM32CUBEMX生成代码1.安装完成之后,点击help,下载依赖包2.选择自己的芯片,选上前面的复选框就可以下载了,前面是绿色就代表已经下载好了3.包下载好之后就可以了,后面回到home界面,创建新项目4.在part name那输入自己的芯片,这里以STMC8T6举例,然后在中间回出现一列信息,点击之后再点击star.

WIN10安装SQL Server2017_Be Lady的博客-程序员宅基地

前言小编前段时间需要用到SQL Server,于是将具体的安装步骤记录下来,希望能有所帮助数据库引擎安装下载SQL Server 2017,具体的下载不再赘述接下来以图片展示SQL Server Management Studio安装结束语本人大三学生一枚,学识尚浅,不喜勿喷,希望今日能抛砖引玉,请各位大佬一定不吝赐教!!!...

HTML连载75-3D转换模块之正方体_睿里睿气的博客-程序员宅基地

一、正方体核心要点就是:使用3D转换模块,以及平移、旋转的在X、Y、Z轴上的应用 &lt;style&gt; *{ margin:0; padding:0; } ul{ width: 200px; height: 200px; ...

QT定时器QTimer和系统时间QTime的使用_康立志的博客-程序员宅基地

QTimer和QTime的使用程序效果展示程序继承QLCDNumber类重新定义鼠标点击和鼠标移动事件。//.h#ifndef DIGICLOCK_H#define DIGICLOCK_H#include&lt;QLCDNumber&gt;class DigiClock : public QLCDNumber{ Q_OBJECTpublic: DigiCloc...

关于JQuery的单选框的全选问题解决—prop()方法和attr()的区别_菲儿啊的博客-程序员宅基地

由于attr()只是针对一般属性,不适合checked、selected、readonly这种的,所以需要用另一种方法来写checked属性的事件。这种方法就是用prop():一、定义和用法prop() 方法设置或返回被选元素的属性和值。当该方法用于返回属性值时,则返回第一个匹配元素的值。当该方法用于设置属性值时,则为匹配元素集合设置一个或多个属性/值对。注意:prop() 方法应该用...

随便推点

JDBC基础篇(MYSQL)——使用statement执行DML语句(insert/update/delete)_五彩世界的博客-程序员宅基地

注意:其中的JdbcUtil是我自定义的连接工具类:代码例子链接:package day02_statement;import java.sql.Connection;import java.sql.SQLException;import java.sql.Statement;import util.JdbcUtil;/** * 使用Statement对象执行DML语句(inser...

cockroach官方文档翻译--3.2 产品的推荐设置_莫薇的博客-程序员宅基地

3.2 产品的推荐设置3.2.1 硬件最小推荐:--对于一个复制集群,使用至少3个节点保证可用性,如果一个节点失败,详见集群策略--每个节点需要有足够的CPU,RAM,网络,存储能力处理你的工作负载,最少1个CPU和2GB RAM每个节点,对于更复杂的工作负载,更高的并发,更快的性能需要额外的资源。最高性能:--使用超过HDDs的SSDs--使用更大的更多的节点,添

【NetWorkX实例(1)】基础操作_LotusQ的博客-程序员宅基地

文章目录1. 读写Graph数据2. lollipop网络特性探索1. 读写Graph数据import sysimport matplotlib.pyplot as pltimport networkx as nxG = nx.grid_2d_graph(5, 5) #生成2d网格图像#打印邻接列表for line in nx.generate_adjlist(G): ...

webstorm用create-react-app脚手架快速构建React开发环境_祥哥的说的博客-程序员宅基地_webstorm 新建react

使用Facebook的create-react-app脚手架快速构建React开发环境(ant.design,redux......) 编程领域中的“脚手架(Scaffolding)”指的是能够快速搭建项目“骨架”的一类工具。例如大多数的React项目都有src,public,webpack配置文件等等,而src目录中又包含components目录等等。每次在新建项目时,手动创建这些固定的文件目录...

JavaOOP面试题01_水巷石子的博客-程序员宅基地

JavaOOP面试题011、什么是B/S架构?什么是C/S架构B/S(Browser/Server),浏览器/服务器程序C/S(Client/Server),客户端/服务端,桌面应用程序2、Java都有那些开发平台?JAVA SE:主要用在客户端开发JAVA EE:主要用在web应用程序开发JAVA ME:主要用在嵌入式应用程序开发3、什么是JDK?什么是JRE?JDK:java development kit:java开发工具包,是开发人员所需要安装的环境JRE:java r

TiDB 整体架构、TiDB 集群主要分为哪几个组件?_Alwaysdazz的博客-程序员宅基地_tidb 组件

TiDB 整体架构、TiDB 集群主要分为哪几个组件?TiDB 集群主要分为三个组件:TiDB ServerTiDB Server 负责接收 SQL 请求,处理 SQL 相关的逻辑,并通过 PD 找到存储计算所需数据的 TiKV 地址,与 TiKV 交互获取数据,最终返回结果。 TiDB Server 是无状态的,其本身并不存储数据,只负责计算,可以无限水平扩展,可以通过负载均衡组件(如L...

推荐文章

热门文章

相关标签