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

目录

 前言

一、并查集

1、并查集的合并（带路径压缩）

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

3、例题

二、前缀和

1 、前缀和是什么

2、经典题目

三- 字符串处理

1、字符串的插入

2、字符串转化为int类型

3、字符反转

 前言

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

一、并查集

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

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

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

其他支持：

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

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

1、并查集的合并（带路径压缩）

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

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

3、例题

代码

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

二、前缀和

1 、前缀和是什么

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

2、经典题目

输入一个长度为 n的整数序列。 接下来再输入 m个询问，每个询问输入一对 l,r。 对于每个询问，输出原序列中从第 l个数到第 r 个数的和。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数，表示整数数列。 接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。 输出格式 共 m 行，每行输出一个询问的结果。

输入样例：

输出样例：

代码

三- 字符串处理

字符串题目考察频率也还行，学会简单的几个字符串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()

代码

3、字符反转

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

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