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
using namespace std;
#include
#include
#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<

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

Yes
No
Yes

#include
using namespace std;
#include
#include
#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"<

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

Yes
2
3

#include
using namespace std;
#include
#include
#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"<

5 3
4 5 1 3 2

1 2 3

#include 
#include

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;
}