东莞建设网官方网站,模板网站多少钱一个,无极网站无极城市在线,私人网站建设步骤目录 前言
一、并查集
1、并查集的合并#xff08;带路径压缩#xff09;
2、询问是否为同一个集合
3、例题
二、前缀和
1 、前缀和是什么
2、经典题目
三- 字符串处理
1、字符串的插入
2、字符串转化为int类型
3、字符反转 前言
并查集合前缀#xff0c;字符串…目录 前言
一、并查集
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.husing 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()
{cinnm;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] ;cinnm;for(int i 1;i n;i) cina[i];for(int i 1;i n;i) s[i] s[i-1] a[i];while(m--){int l,r;cinlr;couts[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());
