冲击蓝桥杯-并查集,前缀和,字符串

目录

 前言

一、并查集

1、并查集的合并(带路径压缩)

2、询问是否为同一个集合

3、例题

二、前缀和

1 、前缀和是什么

2、经典题目

三- 字符串处理

1、字符串的插入

2、字符串转化为int类型

3、字符反转


 前言

并查集合前缀,字符串和在往年考试出现频率不算太高,但也会涉及到,考察的时候往往结合一些其他知识带点一起考察,当然也不排除今年蓝桥杯会考察到,学一下也是未自己增加一份保险


一、并查集

并查集,类似于树的组合,俩个数如何以最短的时间复杂度,实现合并,就是把一个树的根连到另一个树上去,时间复杂度近乎为1;

维护n个元素,刚开始每个元素自己一个集合,支持两个操作。

  • 合并两个元素所在的集合
  • 询问两个元素是否在相同的集合内

其他支持:

  • 维护每个元素和同一个集合内的其他元素的关系
  • 每个元素所在的集合的大小

并查集这个算法,他有自己的模板操作

1、并查集的合并(带路径压缩)

int find (int x)
{
    if(p[x]  != x )   p[x] = find(p[x]);   //父节点等于祖宗节点
    return p[x];
}

p[find(a)] = find(b);  //使a的祖宗节点的父节点等于b的父节点实现转接

2、询问是否为同一个集合

if(find(a) == find(b)) 

3、例题

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int n,m;
int p[N];
int find (int x)
{
    if(p[x]  != x )   p[x] = find(p[x]);   //父节点等于祖宗节点
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n; i ++)  p[i] = i;    //根据题目要求使得每个数各自在一个集合
    while(m--)
    {
        char op[2];
        int a,b; 
        scanf("%s%d%d",op,&a,&b);  //输入字符串,因为scanf常常读入一些空格之类,使用字符串类型比较保险
    
        if(op[0] == 'M')   p[find(a)] = find(b);  //使a的祖宗节点的父节点等于b的父节点实现转接
        else 
        {   
           if(find(a) == find(b)) puts("Yes");
           else puts("No");
        }
    }
    return 0;
}

 2020蓝桥杯b组第四题考到DFS和并查集的内容,感兴趣可以尝试做一下真题


二、前缀和

1 、前缀和是什么

一维数组的前缀和很简单可以通过下面的例题来理解

2、经典题目

输入一个长度为 n的整数序列。

接下来再输入 m个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中从第 l个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。

输出格式

共 m 行,每行输出一个询问的结果。

输入样例:

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例:

3
6
10

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int main()
{
    int n,m;
    int a[N],s[N] ;
    cin>>n>>m;
    for(int i =1;i <= n;i++) cin>>a[i];
    for(int i =1;i <= n;i++) s[i]= s[i-1] +a[i];
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r] - s[l-1]<<endl;
    }
} 

三- 字符串处理

字符串题目考察频率也还行,学会简单的几个字符串STL的函数,可以帮助我们解决复杂的问题,

下面介绍几个
 

1、字符串的插入

string  s = "abcdef"

s1 =  s.substr (2)  //从下标为2的字符开始截取到结尾,s1 = "cdef";

s2 =  s.substr(2,3)  //从下标为2的2字符截取长度为3的字符串 s2 = "cde";

      

2、字符串转化为int类型

string 类型转化为int 型  stol()

string 类型转化为long long型 stoll()

代码

 string s = "12345";
 int t = stol(s);
 printf("%d\n",t);
    
 long long m = stoll(s);
 printf("%lld",m);

3、字符反转

输入一个字符串,想使其反转过来

    string s;
    reverse(s.begin(),s.end());

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/3207.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python让ChatGPT全自动改写生成文章教程

ChatGPT是一个在自然语言处理领域非常先进的文本生成模型&#xff0c;它能够产生高质量、连贯的文章。它受到了广泛的关注&#xff0c;因为它可以自动生成大量的文本&#xff0c;从而减轻了人工写作的负担。怎么使用chatgpt批量改写文章&#xff1f;最简单的方式就是找到一家接…

「Vue面试题」vue要做权限管理该怎么做?如果控制到按钮级别的权限怎么做?

文章目录一、是什么二、如何做接口权限路由权限控制菜单权限方案一方案二按钮权限方案一方案二小结参考文章一、是什么 权限是对特定资源的访问许可&#xff0c;所谓权限控制&#xff0c;也就是确保用户只能访问到被分配的资源 而前端权限归根结底是请求的发起权&#xff0c;…

刷题之最长公共/上升子序列问题

目录 一、最长公共子序列问题&#xff08;LCS&#xff09; 1、题目 2、题目解读 ​编辑 3、代码 四、多写一题 五、应用 二、最长上升子序列问题&#xff08;LIS&#xff09; 1、题目 2、题目解读 3、代码 四、多写一道 Ⅰ、题目解读 Ⅱ、代码 一、最长公共子序列问题&…

刷题训练营之栈与队列

文章目录前言一、用队列实现栈1.题目介绍2.思路3.代码二、用栈实现队列1.题目介绍2.思路3.代码前言 本题是在栈与队列的基础上&#xff0c;为巩固两者而出的题&#xff0c;所以基本是在实现了栈与队列的基础上做的&#xff0c;如果没有栈与队列的基础&#xff0c;请看我之前的…

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…

数据结构中的堆

一、树的重要知识点 节点的度&#xff1a;一个节点含有的子树的个数称为该节点的度&#xff08;有几个孩子&#xff09;叶节点或终端节点:度为0的节点称为叶节点&#xff1b;如上图&#xff1a;B、C、H、I...等节点为叶节点&#xff08;0个孩子&#xff09;非终端节点或分支节点…

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…

一本通 3.2.1 队列的基本应用

1332&#xff1a;【例2-1】周末舞会 【题目描述】 假设在周末舞会上&#xff0c;男士们和女士们进入舞厅时&#xff0c;各自排成一队。跳舞开始时&#xff0c;依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同&#xff0c;则较长…

【数据结构】树和二叉树的介绍

文章目录前言一、树1.1 树的概念1.2 树的相关概念1.3 树的表示1.4 树的用途二、二叉树2.1 二叉树的概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储方式总结前言 树是一种让程序员们既爱又恨的数据结构。它就像是一棵大树&#xff0c;让你可以轻松地摘取其中的果实…

【10】核心易中期刊推荐——模式识别与机器学习

🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…

【C++进阶】C++11(中)左值引用和右值引用

文章目录左值引用左值引用的概念左值引用的使用右值引用右值引用的概念右值引用的使用左右值相互引用左值引用对右值进行引用右值引用对左值进行引用右值引用使用场景和意义左值引用的优势左值引用的短板右值引用的优势完美转发模板万能引用完美转发实际运用场景左值引用 左值…

vue3+ts 开发效率提升

1、vite pnpm项目初始化 pnpm&#xff1a; 比npm或yarn快10倍 pnpm与其他包管理器&#xff08;如npm和Yarn&#xff09;的不同之处在于它使用一种称为“硬链接”的独特安装方法。当你使用PNPM安装一个包时&#xff0c;它并不会将包的文件复制到每个项目的node_modules目录中&a…

图形视图界面 图形效果

Qt的标准图形效果类&#xff1a; QGraphicsBlurEffect提供模糊效果QGraphicsColorizeEffect提供染色效果QGraphicsDropShadowEffect提供阴影效果QGraphicsOpacityEffect提供透明效果 QGraphicsBlurEffect&#xff08;模糊效果&#xff09; 模糊效果会模糊源。此效果对于减少细…

VS Code工作区用法

背景VS Code可以通过"文件/打开文件夹"来打开本地项目&#xff0c;但是想要打开多个项目便需要来回切换&#xff0c;比较费劲。此时就可以使用工作区功能&#xff0c;将不同的项目放置到同一个工作区中&#xff0c;这样切换项目的时候就会非常方便。操作方法打开其中…

免费搭建个人博客

免费搭建个人博客,并发布到公网 利用hexo搭建个人博客&#xff0c;通过gitee的pages发布到公网 1 前置准备 安装git、安装node.js&#xff08;尽量选择长期支持的版本) node.js官网&#xff1a;https://nodejs.org/en/ git官网&#xff1a;https://git-scm.com/book/zh/v2 安装…

如何衡量你的Facebook广告活动的成功

投入大量资金和资源在Facebook广告上并不总能带来预期的回报&#xff0c;这很可能是由于缺乏恰当的衡量广告活动成功的方法。在这篇文章中&#xff0c;我们将介绍一些关键的指标&#xff0c;帮助你更好地了解如何衡量你的Facebook广告活动的成功。1.费用每次点击&#xff08;CP…

Spring和IDEA都不推荐用的@Autowired注解,为什么还有那么多人用?

Autowired的默认装配 我们都知道在spring中Autowired注解&#xff0c;是用来自动装配对象的。通常&#xff0c;我们在项目中是这样用的&#xff1a; package com.sue.cache.service;import org.springframework.stereotype.Service;Service public class TestService1 {publ…

你是否了解AR技术?AR技术就在我们身边

文章目录专栏导读1、前言2、AR技术原理3、游戏领域应用4、教育领域应用5、医疗领域应用6、零售领域应用专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN Python领域新星创作者&#xff0c;专注于分享python领域知识。 ✍ 本文录入于《数据分析之道》&#xff0c;本专栏…

C/C++每日一练(20230325)

目录 1. 搜索插入位置 &#x1f31f; 2. 结合两个字符串 &#x1f31f; 3. 同构字符串 &#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 搜索插入位置 给定一个排序数…
最新文章