[蓝桥杯][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

智能推荐

使用vue-pdf 给pdf加水印_vue pdf加水印-程序员宅基地

文章浏览阅读2.2k次。代码】使用vue-pdf 给pdf加水印。_vue pdf加水印

「 LaTex 」写论文,修改公式内行距的方法_\vspace设置段落行距-程序员宅基地

文章浏览阅读3.4k次。一.前言在官网给的LaTex模板里作业,有时会遇到带有分式或大括号的公式顶端重叠的问题,下面给出解决方法。二.技术实现使用临时修改行距指令\vspace{0.5ex}*{0.5ex}中的数字可以任意调整。三.实例展示修改前如图:修改后如图:*亲测有效..._\vspace设置段落行距

eclipse jsEclipse javascript编辑器-程序员宅基地

文章浏览阅读7.2k次,点赞17次,收藏15次。Eclipse JavaScript插件前言一、JsEclipse是什么?二、使用步骤1.下载2.安装插件总结前言免费下载jseclipse插件,看不惯那些赚积分的。关键字:eclipse、eclipse插件、eclipse js插件、eclipse js编辑器、eclipse jsEclipse、jseclipse、JavaScript编辑器、好用的JavaScript编辑器一、JsEclipse是什么?当然是*.js的编辑器了,代码提示,关键字高亮,重要是好湿,啊不,好使。二、使用步骤_jseclipse

02.Web安全基础、第二章常见Web漏洞解析、第二节CSRF-程序员宅基地

文章浏览阅读68次。目录: 01 CSRF是什么 02 CSRF原理分析 03 漏洞演示 view-source:网址 查看源代码 ..._web漏洞深度剖析第二章的javascript

Filter Concatenation理解_filter conca- tenation-程序员宅基地

文章浏览阅读9.6k次,点赞13次,收藏19次。学习深度学习,有几篇论文大多数人都会读到。其中一篇就是《Going deeper with convolutions》,google在这片论文中提到了一个inception模型(示意版,简单模式):对于我这种基础知识不牢靠,学习时间非常短的人来说,对深度神经网络的理解还没到位,经常看论文一知半解,很多概念搞不清楚。看到上面这个图,我就产生了一个疑问:上图中的Filter C_filter conca- tenation

MyBatis注解方式批量插入操作_mapper批量插入注解-程序员宅基地

文章浏览阅读1.7k次。转载自:https://blog.csdn.net/u011974797/article/details/81873384 @Insert({ "<script>", "insert into table_name(column1, column2, column3) values ", "<foreach collection='t..._mapper批量插入注解

随便推点

Linux系统编程_信号_linux开发板发送ctl+d信号当前终端-程序员宅基地

文章浏览阅读249次。1 信号的概念基本属性信号4要素2 产生信号5种方法kill函数alarm函数setitimer函数3 信号集操作函数信号屏蔽字未决信号集4 信号的捕捉注册信号捕捉函数_linux开发板发送ctl+d信号当前终端

ip层本机接受数据包处理_对于递交给本机的数据包-程序员宅基地

文章浏览阅读514次。当数据包的目的地址是本机是,Ip_rcv_finish函数就会将skb-&gt;dst-&gt;input函数指针初始化为ip_local_deliver,ip层本地发送数据包也分为两个阶段分配分别有两个处理函数:ip_local_deliver和ip_local_deliver_finish。本地转发数据包的首要任务是重组数据包,前送的数据包可以不要重组,前送可以转发每个分片数据包。一、本地..._对于递交给本机的数据包

打开cmd的四种方式和管理员运行以及常用Dos基本命令_资源管理器的地址栏前面加上cmd路径-程序员宅基地

文章浏览阅读2.3k次。1.打开cmd的方式1.开始--系统--命令提示符2.Win + R 键,输入cmd 打开控制台3.在电脑桌面任意的空白处,按住shift键 + 鼠标右键点击-->在此处打开Powershell命令行窗口4.资源管理器的地址栏前面加上cmd路径5.管理员身份运行:开始--系统--命令提示符--右键选择管理员身份运行2.常用的Dos命令#切换盘符 直接输入: D: 或 E: (英文:),即可跳转到D盘或E盘#查看当前目录..._资源管理器的地址栏前面加上cmd路径

002,Jquery对象和Js对象的区别与转换_jquery包装集对象和lavascript对象有什么不一样,它们二者怎么实现转换?-程序员宅基地

文章浏览阅读103次。Jquery对象和js对象的区别与转换V哥教育QQ群:673215016官网:http://www.vgxit.com1,什么是Jquery我们通过jquery的$方法获取到的对象,和我们原生的js代码获取到的对象,是有一些区别的。当然,他们之前也有一些联系,可以相互转换。<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <tit..._jquery包装集对象和lavascript对象有什么不一样,它们二者怎么实现转换?

SystemVerilog之时序块的采样与驱动_时钟块 提前采样延后驱动-程序员宅基地

文章浏览阅读793次。由于时钟偏移等因素的存在,用某个时钟clk驱动信号d1,在实际测试中总是会出现信号d1相对于clk总是会有一个无限小的延时(delta-cycle),为解决这一实际问题可采用本文的几种方法。_时钟块 提前采样延后驱动

16.【进阶】特征提升之特征筛选----feature_selection_corth-features-causal-feature-selection-via-orthog-程序员宅基地

文章浏览阅读1.3k次。#-*- coding:utf-8 -*-#特征筛选的目标:一句话来说就是去冗余特征;与PCA不同,不会修改特征值,而是寻找那些对模型性能提升较大的少量特征#使用Titanic数据集,通过特征筛选的方法一步步提升决策树的预测性能import pandas as pdtitanic = pd.read_csv('http://biostat.mc.vanderbilt.edu/wiki..._corth-features-causal-feature-selection-via-orthogonal-search