算法专栏

算法专栏"/>

算法专栏

 trie树 

#include <iostream>
using namespace std;
const int N = 1000010;
int son[N][26],cnt[N],idx;
//明确前面两个数组以及idx的含义
//我们把son这个二维数组看成一个字典树
//本题要求26个字母，所以我们每个节点里面最多有26个儿子节点
//而我们本题要求字符串长度是100000个，所以son数组的N代表有100000层，对应的就是字符串长度
//为什么这样就可以呢，因为我们查找的字符串（只有26个字母）在查找的时候想象成树
//每次面临26种选择（26个字母）(也有点组合的意思)，选择一种和当前匹配的，没有就说明没有匹配的
//idx是什么呢，我们怎么用数组来模拟的呢，我们怎么算是创建过这个节点了，我们son数组的元素为1
//就代表我们创建了这个节点，如果遇到这个节点之后我们就可以直接往下走，如果没有遇到，我们就
//不往下走,先创建在走，创建的过程就是idx++,就是走到当前元素为1时说明创建过了
//cnt数组表示以当前节点的值为终点的字符串个数char str[N];
void insert(char str[])
{int p = 0;//p代表我们当前走到哪个位置了（把数组抽象成一棵树）for(int i = 0; str[i] != '\0';i++)//枚举插入的字符串，枚举的字符串抽象成路径{int u = str[i] - 'a';//映射到数组里，son数组一维数组的下标0代表的是a，1是bif(son[p][u] == 0) son[p][u] = ++idx;//每次进入判断是否创建过当前值的节点p = son[p][u];//走到下一层}cnt[p]++;//当前下标为终点的字符串个数++
}
int  inquire(char str[])
{int p = 0;for(int i = 0; str[i] != '\0';i++){int u = str[i] - 'a';if(!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}
int main()
{int n;cin>>n;for(int i = 0;i < n;i++){char chose[2];cin>>chose>>str;if(chose[0] == 'I'){insert(str);}else{printf("%d\n",inquire(str));}}return 0;
}

并查集

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
//本题是模板题，所以我们先理解这道题的模板是什么
//本题的模板是并查集，那什么是并查集呢，其实你可以想象成一个树
//我们的字符串都是通过递归去搜索的，跟字典树类似
//但是并查集强在归并和询问的操作近乎O(1)的时间复杂度,可以快速将两个集合
//合并和快速查两个集合是否在同一个集合//并查集的基本原理是什么呢，基本原理就是每个集合我们看成一颗小树，一颗大树里可能包含小树
//比方说一个字符串是一个集合，那么这棵大树可能就有好多字符串集合，
//那我们并查集是怎么快速实现合并和查询的呢，这就要说到并查集的编号了
//我们怎么去查找到这个集合呢，我们肯定得让他的根节点跟孩子节点编号不一样，我们才能找到
//我们的集合，在此我们设置P[x]为节点的编号，而p[x] == x 是根节点的编号
//我们的p[x]代表的是当前节点的父节点
//1.如何判断根节点 if(p[x] == x)
//2.如何从孩子节点求根节点的编号while(p[x]!=x) x = p[x];
//3.如何合并两个集合，假设编号是p[X],P[Y],前面提到过的我们抽象成一颗树，这棵树
//合并只需要把一个根节点作为另一个根节点的父节点即可
//在此，我们还需要优化一下，路径压缩法,等于说第一次查询过这个集合之后下次查询就是O（1)的
//时间复杂度,为什么呢，想象一下一棵树的高度只有2，根节点只有1个，这时我们查询集合的所以元素的话
//我们就只需要遍历这个集合就元素就行，不需要再去递归好几层了//并查集模板最关键的点是在于写出find操作
const int N = 1000010;
int p[N];
int  find(int x)//返回要查找的元素的集合,递归查找
{if(p[x] != x)  p[x] = find(p[x]);//如果父节点不是根节点，那么就把接力棒给父节点//让父亲节点去找return p[x];//找到了就返回
}
int main()
{int n, m;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);if (op[0] == 'Q'){if (find(a) == find(b)) printf("Yes\n");else printf("No\n");}else if(op[0] == 'M'){p[find(a)] = find(b);//找到a集合的根节点，把a集合的根节点查到b集合的根节点}}return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510000;
int p[N],d[N];
int n,m;
int find(int x)//路径压缩
{if(p[x] != x)//不是根节点的话{int t = find(p[x]);d[x] += d[p[x]]; p[x] = t;}return p[x];
}int main()
{cin>>n>>m;for(int i = 1;i <= N;i++){p[i] = i;}int cnt = 0;for(int i = 1;i <= m;i++){int op,a,b;cin>>op>>a>>b;if(a > n || b > n){cnt++;continue;}int pa = find(a);int pb = find(b);if(op == 1){if(pa == pb && (d[a] - d[b]) % 3){//是在同一个集合的话，判断是否是同类//不是同类res++，是同类不用管cnt++;}else if(pa != pb){//不在同一个集合，判断是否同类//先建立两个集合的集合关系，为什么建立两个呢//因为能find找到说明必有根节点//本题根节点肯定存在，就算只有两个节点//我们也看成两个集合p[p[a]] = pb;//让x集合的根节点作为y集合的根节点的孩子//节点//建立之后还得更新一下距离关系，第一次进入的话其实//并没有建立集合，也就是刚好是说了第一句话的时候//第一句不同的x和y或者两个相同的x或者y我们默认为真话，//默认为x和y同类并且建立关系（同类关系）//所以x和y分别到当前建立好集合关系//的根节点的距离一定要相等，所以距离//就是d[x] + ？= d[y]，这个问好是根节点到px的距离d[pa] = d[b] - d[a];}}else{if(pa == pb && (d[a] - d[b] -1) %3){//在同一个集合//并且不是x 吃 y的关系//c++中-n % n等于0cnt++;}else if(pa != pb){//不是同一个集合的话，那么我们默认为//真话，x能吃掉yp[p[a]] = pb;//维护距离使得x能吃掉yd[pa] = d[b] - d[a] + 1;}}}cout<<cnt<<endl;return 0;
}