目录
前言
一、并查集
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 32 1 3 6 41 21 32 4输出样例：
3610代码
#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());