目录
并查集合前缀,字符串和在往年考试出现频率不算太高,但也会涉及到,考察的时候往往结合一些其他知识带点一起考察,当然也不排除今年蓝桥杯会考察到,学一下也是未自己增加一份保险
并查集,类似于树的组合,俩个数如何以最短的时间复杂度,实现合并,就是把一个树的根连到另一个树上去,时间复杂度近乎为1;
维护n个元素,刚开始每个元素自己一个集合,支持两个操作。
其他支持:
并查集这个算法,他有自己的模板操作
int find (int x)
{
if(p[x] != x ) p[x] = find(p[x]); //父节点等于祖宗节点
return p[x];
}
p[find(a)] = find(b); //使a的祖宗节点的父节点等于b的父节点实现转接
if(find(a) == find(b))
代码
#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和并查集的内容,感兴趣可以尝试做一下真题
一维数组的前缀和很简单可以通过下面的例题来理解
输入一个长度为 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的函数,可以帮助我们解决复杂的问题,
下面介绍几个
string s = "abcdef" s1 = s.substr (2) //从下标为2的字符开始截取到结尾,s1 = "cdef"; s2 = s.substr(2,3) //从下标为2的2字符截取长度为3的字符串 s2 = "cde";
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);
输入一个字符串,想使其反转过来
string s; reverse(s.begin(),s.end());