3.31 acwing算法基础课 数据结构 trie 并查集 堆

一、

835. Trie字符串统计

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 xx；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作，输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 NN，表示操作数。

接下来 NN 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2?1041≤N≤2?104

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

trie树：

思路：看完之后有几个点容易搞乱，需要注意

1.idx是个很神奇的标记符号，当输入一个字符时，只有唯一对应的idx标记对应这个字符，将此时的idx标记放在cnt数组中就可以知道哪个已经存在哪个没有存在；当该字符已经在该位置存在时，idx不会++，顺着走看看是否存在该字符串，如果存在，idx一次都不++，但凡不存在一次都会++，idx递增的特性致使他的唯一对应性

2.如果该结点是没有东西的，赋予此时的a[p][t]一个值，该值决定下一行走向，如果已经有东西，则顺着原来的走到下一个结点；直到遍历成功

3.复做易错：应该是cnt[p]++,而我经常写成cnt[idx]++;

#include<iostream>
using namespace std;
#include<vector>
#include<bits/stdc++.h>
#define N 1000010
int a[N][26],cnt[N],idx;
void Insert(string str)
{int p=0;for(int i=0;str[i];i++){int t=str[i]-'a';if(!a[p][t])a[p][t]=++idx;p=a[p][t];}cnt[p]++;
}
int query(string str)
{int p=0;for(int i=0;str[i];i++){int t=str[i]-'a';if(!a[p][t])return 0;p=a[p][t];}return cnt[p];
}
int main()
{int n;cin>>n;while(n--){char a;cin>>a;string op;cin>>op;if(a=='I'){Insert(op);}else if(a=='Q'){cout<<query(op)<<endl;}}return 0;
}

---------------------------------------------------------------------------------------------------------------------------------

二、

836. 合并集合

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

一共有 nn 个数，编号是 1?n1?n，最开始每个数各自在一个集合中。

现在要进行 mm 个操作，操作共有两种：

1. M a b，将编号为 aa 和 bb 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 aa 和 bb 的两个数是否在同一个集合中；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

并查集：

 

 

 注意点：记住Find函数

1.只有当p[x]=x时，x才是根节点

2.开始操作前先将所有节点作为根结点

#include<iostream>
using namespace std;
#include<vector>
#include<bits/stdc++.h>
#define 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]=='M'){p[Find(a)]=Find(b);}else{if(Find(a)==Find(b))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}}return 0;
}

---------------------------------------------------------------------------------------------------------------------------------

三、

837. 连通块中点的数量

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定一个包含 nn 个点（编号为 1?n1?n）的无向图，初始时图中没有边。

现在要进行 mm 个操作，操作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

注意点：sizes相加时记得加Find，讲sizes存在每个并查集的头节点

#include<iostream>
using namespace std;
#include<vector>
#include<bits/stdc++.h>
#define N 1000010
int p[N],sizes[N];
int Find(int x)
{if(p[x]!=x)p[x]=Find(p[x]);return p[x];
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){p[i]=i;sizes[i]=1;}while(m--){char str[5];int a,b;scanf("%s",str);if(str[0]=='C'){scanf("%d%d",&a,&b);if(Find(a)==Find(b))continue;sizes[Find(b)]+=sizes[Find(a)];p[Find(a)]=Find(b);}else if(str[1]=='1'){scanf("%d%d",&a,&b);if(Find(a)==Find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}else{scanf("%d",&a);cout<<sizes[Find(a)]<<endl;}}return 0;
}

---------------------------------------------------------------------------------------------------------------------------------

小根堆：

1.插入一个数：将其放在最后一位一直向上即可

2.求最小值 ：第一个数时小根堆最小值

3.删除最小值：将第一个数与最后一个数互换，然后向下维护即可

4.删除任意元素：将其与最后一个数呼唤，同时执行向下向上操作，如果较大，则会执行down不执行up，反之

5.修改任意元素：和4同理

---------------------------------------------------------------------------------------------------------------------------------

四、

838. 堆排序

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

输入一个长度为 nn 的整数数列，从小到大输出前 mm 小的数。

输入格式

第一行包含整数 nn 和 mm。

第二行包含 nn 个整数，表示整数数列。

输出格式

共一行，包含 mm 个整数，表示整数数列中前 mm 小的数。

数据范围

1≤m≤n≤1051≤m≤n≤105，
1≤数列中元素≤1091≤数列中元素≤109

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

思路：明天补充。 

#include<iostream> 
#include<algorithm>using namespace std;const int N = 100010;int h[N], mySize;int n, m;void down(int u)
{int t = u;if (2 * u <= mySize && h[t] > h[2 * u])t = 2 * u;if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])t = 2 * u + 1;if (u != t){swap(h[u], h[t]);down(t);}
}int main()
{cin >> n >> m;mySize = n;for (int i = 1; i <= n; i++)scanf("%d", &h[i]);for (int i = n / 2; i; i--)down(i);while (m--){cout << h[1] << " ";h[1] = h[mySize--];down(1);}return 0;
}