算法基础复盘笔记Day04【数据结构】—— KMP、字典树(Tire)、并查集、堆、哈希表

举报
jyu_wy 发表于 2023/03/19 10:32:36 2023/03/19
【摘要】 第一章 KMP 一、KMP字符串 1. 题目描述给定一个字符串 SSS,以及一个模式串 PPP,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 PPP 在字符串 SSS 中多次作为子串出现。求出模式串 PPP 在字符串 SSS 中所有出现的位置的起始下标。输入格式第一行输入整数 NNN,表示字符串 PPP 的长度。第二行输入字符串 PPP。第三行输入整数 MMM,表示字符串 SSS...

第一章 KMP

一、KMP字符串

1. 题目描述

给定一个字符串 S S ,以及一个模式串 P P ,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P P 在字符串 S S 中多次作为子串出现。

求出模式串 P P 在字符串 S S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N N ,表示字符串 P P 的长度。

第二行输入字符串 P P

第三行输入整数 M M ,表示字符串 S S 的长度。

第四行输入字符串 S S

输出格式

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。

数据范围

1 N 1 0 5 1≤N≤10^5
1 M 1 0 6 1≤M≤10^6

输入样例:

3
aba
5
ababa

输出样例:

0 2

2. 思路分析

前缀数组,即 n e x t next 数组,每一个子串都有一个固定的 n e x t next 数组,它记录着字符串匹配过程中失配情况下可以向后多跳几个字符,其实也就是子串的前缀和后缀相同的最长长度。

如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:

在这里插入图片描述


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int ne[N]; //保存next数组
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
    
    //求next数组
    //j表示匹配成功的长度,i表示p数组中下标,因为p数组的下标是从1开始的,只有1个时,j一定是0,所以i从2开始
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        //匹配不成功,则换到next数组
        while (j && p[i] != p[j + 1]) j = ne[j];
        //匹配成功的话,则j加1
        if (p[i] == p[j + 1]) j ++;
        //对应其下标
        ne[i] = j;
    }
    
    //j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度是0
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        //如果匹配不成功,则切换j到next数组中的值
        while (j && s[i] != p[j + 1]) j = ne[j];
        //匹配成功,则j加1,继续后面的匹配
        if (s[i] == p[j + 1]) j ++;
        if (j == n)
        {
            //因为题目中下标从0开始所以是i - n,如果是从1开始则是i - n + 1
            printf("%d ", i - n);
            //继续切换j到next数组中值,继续匹配是否还能与后面的匹配成功
            j = ne[j];
        }
    }
    return 0;
}

第二章 字典树(Tire)

一、Tire字符串统计

1. 题目描述

维护一个字符串集合,支持两种操作:

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

共有 N N 个操作,所有输入的字符串总长度不超过 1 0 5 10^5 ,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N N ,表示操作数。

接下来 N N 行,每行包含一个操作指令,指令为 I xQ x 中的一种。

输出格式

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

每个结果占一行。

数据范围

1 N 2 1 0 4 1≤N≤2∗10^4

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

2. 思路分析

Trie树中有个二维数组 son[N][26],表示当前结点的儿子,如果没有的话,可以等于++idx。Trie树本质上是一颗多叉树,对于字母而言最多有26个子结点。所以这个数组包含了两条信息。

建字典树:
儿子数组 son[p][u] 存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母(a ~ z)对应的映射值 0 ~ 25,每个节点最多可以有26个分叉。
比如:son[1][0]=2表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0,则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

计数数组cnt[p] 存储以节点 p 结尾的单词的插入次数。

节点编号 idx 用来给节点编号。

  1. 空 Tire 仅有一个根节点,编号为0;
  2. 从根节点开始插,枚举字符串的每个字符,如果有儿子,则 p 指针走到儿子;如果没有儿子,则先创建儿子,p 指针再走到儿子;
  3. 在单词结束点记录插入次数。

3. 代码实现

//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

// son[p][26]存储子节点的位置,分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数(同时起标记作用)
// idx 表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0; //指针p,指向当前节点
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a'; //将字母映射为数字
        if (!son[p][u]) son[p][u] = ++idx; //该节点不存在,创建节点
        p = son[p][u]; //p指针指向下一个节点
    }
    cnt[p] ++; //结束时的标记,也是记录以此节点结束的字符串的个数
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; 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;
    while (n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

二、最大异对

1. 题目描述

在给定的 N N 个整数 A 1 A 2 A N A1,A2……AN 中选出两个进行 x o r xor (异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 N N

第二行输入 N N 个整数 A 1 A N A_1~A_N

输出格式

输出一个整数表示答案。

数据范围

1 N 1 0 5 1≤N≤10^5 ,
0 A i < 2 31 0≤A_i<2^{31}

输入样例:

3
1 2 3

输出样例:

3

2. 思路分析

异或: 如果a、b两个值不相同,则异或结果为1;如果a、b两个值相同,异或结果为0。

  1. 将一个整数转化为一个32位的二进制数,也就是长度为32位的二进制字符串;
  2. 从最高位开始检索,每次找与该位相反的数字,才能让异或最大,如果没有想反的数字,则选择相同的数字。
  3. 返回最大的异或数。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0; //根节点
    for (int i = 30; i >= 0; i --) 
    {
        int u = x >> i & 1; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
        if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点,创建该子节点
        p = son[p][u]; //p指针指向子节点
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) //从最大数开始找
    {
        int u = x >> i & 1;
        //如果当前层有对应的不相同的数
        if (son[p][!u])
        {
            res = res * 2 + 1; // 更新res的值,每次把旧值乘以2(这一步相当于左移一位)再加上当前值
            p = son[p][!u]; //p指针就指向不同数的地址
        }
        //如果当前层没有对应的不相同的数,则p指针指向相同的数的地址
        //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        // else
        // {
        //     res = res * 2 + 0; //对res的值没有改变,省略
        //     p = son[p][u];
        // }
        else p = son[p][u];
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        insert(a[i]);
    }
    
    int res = 0;
    for (int i = 0; i < n; i ++) res = max(res, search(a[i])); //查找a[i]最大的异或值
    cout << res << endl;
    
    return 0;
}

第三章 并查集

一、合并集合

1. 题目描述

一共有 n n 个数,编号是 1 n 1∼n ,最开始每个数各自在一个集合中。

现在要进行 m m 个操作,操作共有两种:

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

输入格式

第一行输入整数 n n m m

接下来 m m 行,每行包含一个操作指令,指令为 M a bQ a b 中的一种。

输出格式

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

每个结果占一行。

数据范围

1 n , m 1 0 5 1≤n,m≤10^5

输入样例:

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

输出样例:

Yes
No
Yes

2. 思路分析

并查集是一种树形的数据结构。

并查集支持的两个操作:

  • 合并: 将两个子集合并成一个集合。
  • 查找: 确定某个元素在哪个集合。

路径压缩的查找:
根节点是集合的代表,查找就是找到元素所在集合的根。

  1. 如果父节点等于自己,则找到了根并返回;
  2. 如果还没有找到根,则继续递归查找;
  3. 在返回的路上,顺带修改各节点的父节点为根。

合并:
把一个集合的根指向另一个集合的根。


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int p[N];

// 返回x的祖先节点 + 路径压缩
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 == 'M') p[find(a)] = find(b); 
        else
        {
            //若两个数的父节点一样,则在同一个集合
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

二、连通块中点的数量

1. 题目描述

给定一个包含 n 个点(编号为 1 n 1∼n )的无向图,初始时图中没有边。

现在要进行 m 个操作,操作共有三种:

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

输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 C a bQ1 a bQ2 a 中的一种。

输出格式

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

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

每个结果占一行。

数据范围

1 n , m 1 0 5 1≤n,m≤10^5

输入样例:

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

输出样例:

Yes
2
3

2. 思路分析

  1. 初始化:先设置每个节点的根节点为自己,刚开始是每个集合中点的数量为1;
  2. 合并集合: 把一个集合的根指向另一个集合的根,并且把该集合中点的数量加入另一个集合中;
  3. 查询:即判断两个集合的父节点是否一样。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[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;
        cnt[i] = 1;
    }
    
    while (m --)
    {
        string op;
        int a, b;
        cin >> op;
        
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

三、食物链

待完善......


第四章 堆

一、堆排序

1. 题目描述

输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

输出格式

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

数据范围

1 m n 1 0 5 1≤m≤n≤10^5
1 数列中元素 1 0 9 1≤数列中元素≤10^9

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

2. 思路分析

如何手写一个堆?

  1. 插入一个数:heap[ ++ size] = x; up(size);
  2. 求集合中的最小值: heap[1];
  3. 删除最小值:heap[1] = heap[size]; size -- ;down(1);
  4. 删除任意一个元素:heap[k] = heap[size]; size -- ;up(k); down(k);
  5. 修改任意一个元素:heap[k] = x; up(k); down(k);

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
//h[i]表示第i个结点存储的值,i从1开始,2 * i是左子节点,2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数,又表示最后一个结点的下标
int h[N], cnt;

void down(int u)
{
    int t = u; //t存储三个结点中存在的最小的结点的下标,初始化为当前结点u
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点,更新t的下标
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点,更新t的下标
    if (u != t) //如果t==u意味着不用变动,u就是三个结点中拥有最小值的结点下标,否则交换数值
    {
        swap(h[u], h[t]); 
        down(t); //交换数值后,t这个结点存储原本u的值,u存储存储t的值(三个数中的最小值)。u不用调整了,但t情况不明,可能需要调整。直到它比左右子节点都小。
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    cnt = n; //初始化cnt,表示堆中有多少个元素

    //把堆初始化成小根堆,从二叉树的倒数第二行开始,把数字大的下沉
    for (int i = n/2; i; i --) down(i);
    
    while (m --)
    {
        cout << h[1] << ' '; //输出堆顶(最小值)
        h[1] = h[cnt --]; ////删除堆顶(用最后一个数覆盖第一个数),并且长度减1
        down(1); //让覆盖好的值继续往下走
    }
    return 0;
}

二、模拟堆

1. 题目描述

维护一个集合,初始时集合为空,支持如下几种操作:

  1. I x,插入一个数 x;
  2. PM,输出当前集合中的最小值;
  3. DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
  4. D k,删除第 k 个插入的数;
  5. C k x,修改第 k 个插入的数,将其变为 x;

现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 N 行,每行包含一个操作指令,操作指令为 I xPMDMD kC k x 中的一种。

输出格式

对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。

每个结果占一行。

数据范围

1 N 1 0 5 1≤N≤10^5
1 0 9 x 1 0 9 −10^9≤x≤10^9
数据保证合法。

输入样例:

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例:

-10
6

2. 思路分析

相关思路在以下的代码注释中。


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int cnt;  //记录堆中当前数据的多少

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u *2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    int n, m = 0; //m是记录插入的数的个数,m是对应hp中应该存的值
    cin >> n;
    while (n --)
    {
        string op;
        int k, x;
        cin >> op;
        //插入一个数 x
        if (op == "I")
        {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        //输出当前集合中的最小值
        else if (op == "PM") cout << h[1] << endl;
        //删除当前集合中的最小值
        else if (op == "DM")
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        //删除第 k 个插入的数
        else if (op == "D")
        {
            cin >> k;
            k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
            heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
            cnt --;
            up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(k);
        }
        //修改第 k 个插入的数,将其变为 x
        else
        {
            cin >> k >> x;
            h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个,所以可直接传入ph[k]作为参数
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}

第五章 哈希表

一、模拟散列表

1. 题目描述

维护一个集合,支持如下几种操作:

  1. I x,插入一个数 x;
  2. Q x,询问数 x 是否在集合中出现过;

现在要进行 N 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N,表示操作数量。

接下来 N 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 xx 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1 N 1 0 5 1≤N≤10^5
109 x 1 0 9 −109≤x≤10^9

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

2. 思路分析

散列表,也叫哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

开放寻址法:

  • 如果要插入元素的映射位置没有元素,那么直接将该元素放在当前位置;
  • 如果要插入元素的映射位置已经有了元素,那么就以此往后找,如果到了数组末尾还没有找到一个空的位置,就返回数组的头接着找;
  • 为了防止整个数组都找了一遍还没有找到一个空的位置,数组大小通常要开数据范围的2~3倍。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数 
const int null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    //t表示x映射到哈希表中的位置
    //+N再%N可以避免出现负数
    int t = (x % N + N) % N;
    //冲突情况:当前位置不为空,并且不为x
    while (h[t] != null && h[t] != x)
    {
        t ++;
        if (t == N) t = 0; //如果到了末尾就从头开始
    } //while一定会结束,因为我们的数组范围是开了2~3倍的,所以整个数组不会被完全使用,因此while不会无限循环
    
    //如果x存在哈希表中,返回的t是下标;如果x不在哈希表中,返回的t是x在哈希表中要存储的位置
    return t; 
}

int main()
{
    //把哈希表的值设置成一个不可能被映射到的数,以此来判断该位置有没有被使用
    memset(h, 0x3f, sizeof h);
    
    int n;
    cin >> n;
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

二、字符串哈希

1. 题目描述

给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l 1 , r 1 , l 2 , r 2 l1,r1,l2,r2 ,请你判断 [ l 1 , r 1 ] [l1,r1] [ l 2 , r 2 ] [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m,表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。

接下来 m 行,每行包含四个整数 l 1 , r 1 , l 2 , r 2 l1,r1,l2,r2 ,表示一次询问所涉及的两个区间。

注意,字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1 n , m 1 0 5 1≤n,m≤10^5

输入样例:

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例:

Yes
No
Yes

2. 思路分析

字符串哈希,全称是字符串前缀哈希法,把 字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字。
对形如 X 1 X 2 X 3 X n 1 X n X_1X_2X_3⋯X_{n−1}X_n 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。

映射公式: ( X 1 × P n 1 + X 2 × P n 2 + + X n 1 × P 1 + X n × P 0 ) m o d Q (X_1×P^{n−1}+X_2×P^{n−2}+⋯+X_{n−1}×P^1+X_n×P^0) mod Q

注意点:

  • 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA…都映射成0的话那就无法进行比较字符串是否相同了;
  • 冲突问题:听过巧妙设置P(131 或 13331),Q( 2 64 2^{64} )的值,一般情况下可以避免发生冲突;
  • 由于需要模 2 64 2^{64} ,则可以直接用 unsigned long long来存储,它可以溢出,溢出时相当于模了一个 2 64 2^{64}

问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 h [ i + 1 ] = h [ i ] × P + s [ i ] h[i+1]=h[i]×P+s[i] i [ 0 , n 1 ] i∈[0,n−1] h为前缀和数组,s为字符串数组。
区间和公式 h [ l , r ] = h [ r ] h [ l 1 ] × P r l + 1 h[l,r]=h[r]−h[l−1]×P*{r−l+1}

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,乘上 P 2 P^2 把 ABC 变为 ABC00,再用 ABCDE - ABC00 得到 DE 的哈希值。


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

// unsigned long long 数据类型的范围是[0,2^64-1]
// 用 unsigned long long来存储h\,它可以溢出,溢出时就相当于模了一个2^64
typedef unsigned long long ULL;

//P取131或者13331,mod取2^64,在99.99%的情况下不会发生冲突
const int N = 100010, P = 131;

int n, m;
char str[N];
//h[i]表示前i个字符的hash值
ULL h[N], p[N];

//求[l, r]区间中字符串的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    cin >> n >> m;
    scanf("%s", str + 1);
    
    p[0] = 1; //p的0次方等于1
    
    for (int i = 1; i <= n; i ++)
    {
        h[i] = h[i - 1] * P + str[i]; //前缀和求以i结尾的整个字符串的哈希值
        p[i] = p[i - 1] * P;
    }
    
    while (m --)
    {
        
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        
        //如果两个区间的哈希值相同,则字符串相同;否则不同
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

创作不易,如果有帮助到你,请给文章==点个赞和收藏==,让更多的人看到!!!
==关注博主==不迷路,内容持续更新中。# 第一章 KMP

一、KMP字符串

1. 题目描述

给定一个字符串 S S ,以及一个模式串 P P ,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P P 在字符串 S S 中多次作为子串出现。

求出模式串 P P 在字符串 S S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N N ,表示字符串 P P 的长度。

第二行输入字符串 P P

第三行输入整数 M M ,表示字符串 S S 的长度。

第四行输入字符串 S S

输出格式

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。

数据范围

1 N 1 0 5 1≤N≤10^5
1 M 1 0 6 1≤M≤10^6

输入样例:

3
aba
5
ababa

输出样例:

0 2

2. 思路分析

前缀数组,即 n e x t next 数组,每一个子串都有一个固定的 n e x t next 数组,它记录着字符串匹配过程中失配情况下可以向后多跳几个字符,其实也就是子串的前缀和后缀相同的最长长度。

如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:

在这里插入图片描述


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int ne[N]; //保存next数组
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
    
    //求next数组
    //j表示匹配成功的长度,i表示p数组中下标,因为p数组的下标是从1开始的,只有1个时,j一定是0,所以i从2开始
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        //匹配不成功,则换到next数组
        while (j && p[i] != p[j + 1]) j = ne[j];
        //匹配成功的话,则j加1
        if (p[i] == p[j + 1]) j ++;
        //对应其下标
        ne[i] = j;
    }
    
    //j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度是0
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        //如果匹配不成功,则切换j到next数组中的值
        while (j && s[i] != p[j + 1]) j = ne[j];
        //匹配成功,则j加1,继续后面的匹配
        if (s[i] == p[j + 1]) j ++;
        if (j == n)
        {
            //因为题目中下标从0开始所以是i - n,如果是从1开始则是i - n + 1
            printf("%d ", i - n);
            //继续切换j到next数组中值,继续匹配是否还能与后面的匹配成功
            j = ne[j];
        }
    }
    return 0;
}

第二章 字典树(Tire)

一、Tire字符串统计

1. 题目描述

维护一个字符串集合,支持两种操作:

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

共有 N N 个操作,所有输入的字符串总长度不超过 1 0 5 10^5 ,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N N ,表示操作数。

接下来 N N 行,每行包含一个操作指令,指令为 I xQ x 中的一种。

输出格式

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

每个结果占一行。

数据范围

1 N 2 1 0 4 1≤N≤2∗10^4

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

2. 思路分析

Trie树中有个二维数组 son[N][26],表示当前结点的儿子,如果没有的话,可以等于++idx。Trie树本质上是一颗多叉树,对于字母而言最多有26个子结点。所以这个数组包含了两条信息。

建字典树:
儿子数组 son[p][u] 存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母(a ~ z)对应的映射值 0 ~ 25,每个节点最多可以有26个分叉。
比如:son[1][0]=2表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0,则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

计数数组cnt[p] 存储以节点 p 结尾的单词的插入次数。

节点编号 idx 用来给节点编号。

  1. 空 Tire 仅有一个根节点,编号为0;
  2. 从根节点开始插,枚举字符串的每个字符,如果有儿子,则 p 指针走到儿子;如果没有儿子,则先创建儿子,p 指针再走到儿子;
  3. 在单词结束点记录插入次数。

3. 代码实现

//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

// son[p][26]存储子节点的位置,分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数(同时起标记作用)
// idx 表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0; //指针p,指向当前节点
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a'; //将字母映射为数字
        if (!son[p][u]) son[p][u] = ++idx; //该节点不存在,创建节点
        p = son[p][u]; //p指针指向下一个节点
    }
    cnt[p] ++; //结束时的标记,也是记录以此节点结束的字符串的个数
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; 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;
    while (n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

二、最大异对

1. 题目描述

在给定的 N N 个整数 A 1 A 2 A N A1,A2……AN 中选出两个进行 x o r xor (异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 N N

第二行输入 N N 个整数 A 1 A N A_1~A_N

输出格式

输出一个整数表示答案。

数据范围

1 N 1 0 5 1≤N≤10^5 ,
0 A i < 2 31 0≤A_i<2^{31}

输入样例:

3
1 2 3

输出样例:

3

2. 思路分析

异或: 如果a、b两个值不相同,则异或结果为1;如果a、b两个值相同,异或结果为0。

  1. 将一个整数转化为一个32位的二进制数,也就是长度为32位的二进制字符串;
  2. 从最高位开始检索,每次找与该位相反的数字,才能让异或最大,如果没有想反的数字,则选择相同的数字。
  3. 返回最大的异或数。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0; //根节点
    for (int i = 30; i >= 0; i --) 
    {
        int u = x >> i & 1; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
        if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点,创建该子节点
        p = son[p][u]; //p指针指向子节点
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) //从最大数开始找
    {
        int u = x >> i & 1;
        //如果当前层有对应的不相同的数
        if (son[p][!u])
        {
            res = res * 2 + 1; // 更新res的值,每次把旧值乘以2(这一步相当于左移一位)再加上当前值
            p = son[p][!u]; //p指针就指向不同数的地址
        }
        //如果当前层没有对应的不相同的数,则p指针指向相同的数的地址
        //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        // else
        // {
        //     res = res * 2 + 0; //对res的值没有改变,省略
        //     p = son[p][u];
        // }
        else p = son[p][u];
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        insert(a[i]);
    }
    
    int res = 0;
    for (int i = 0; i < n; i ++) res = max(res, search(a[i])); //查找a[i]最大的异或值
    cout << res << endl;
    
    return 0;
}

第三章 并查集

一、合并集合

1. 题目描述

一共有 n n 个数,编号是 1 n 1∼n ,最开始每个数各自在一个集合中。

现在要进行 m m 个操作,操作共有两种:

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

输入格式

第一行输入整数 n n m m

接下来 m m 行,每行包含一个操作指令,指令为 M a bQ a b 中的一种。

输出格式

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

每个结果占一行。

数据范围

1 n , m 1 0 5 1≤n,m≤10^5

输入样例:

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

输出样例:

Yes
No
Yes

2. 思路分析

并查集是一种树形的数据结构。

并查集支持的两个操作:

  • 合并: 将两个子集合并成一个集合。
  • 查找: 确定某个元素在哪个集合。

路径压缩的查找:
根节点是集合的代表,查找就是找到元素所在集合的根。

  1. 如果父节点等于自己,则找到了根并返回;
  2. 如果还没有找到根,则继续递归查找;
  3. 在返回的路上,顺带修改各节点的父节点为根。

合并:
把一个集合的根指向另一个集合的根。


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int p[N];

// 返回x的祖先节点 + 路径压缩
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 == 'M') p[find(a)] = find(b); 
        else
        {
            //若两个数的父节点一样,则在同一个集合
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

二、连通块中点的数量

1. 题目描述

给定一个包含 n 个点(编号为 1 n 1∼n )的无向图,初始时图中没有边。

现在要进行 m 个操作,操作共有三种:

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

输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 C a bQ1 a bQ2 a 中的一种。

输出格式

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

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

每个结果占一行。

数据范围

1 n , m 1 0 5 1≤n,m≤10^5

输入样例:

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

输出样例:

Yes
2
3

2. 思路分析

  1. 初始化:先设置每个节点的根节点为自己,刚开始是每个集合中点的数量为1;
  2. 合并集合: 把一个集合的根指向另一个集合的根,并且把该集合中点的数量加入另一个集合中;
  3. 查询:即判断两个集合的父节点是否一样。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[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;
        cnt[i] = 1;
    }
    
    while (m --)
    {
        string op;
        int a, b;
        cin >> op;
        
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

三、食物链

待完善......


第四章 堆

一、堆排序

1. 题目描述

输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

输出格式

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

数据范围

1 m n 1 0 5 1≤m≤n≤10^5
1 数列中元素 1 0 9 1≤数列中元素≤10^9

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

2. 思路分析

如何手写一个堆?

  1. 插入一个数:heap[ ++ size] = x; up(size);
  2. 求集合中的最小值: heap[1];
  3. 删除最小值:heap[1] = heap[size]; size -- ;down(1);
  4. 删除任意一个元素:heap[k] = heap[size]; size -- ;up(k); down(k);
  5. 修改任意一个元素:heap[k] = x; up(k); down(k);

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
//h[i]表示第i个结点存储的值,i从1开始,2 * i是左子节点,2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数,又表示最后一个结点的下标
int h[N], cnt;

void down(int u)
{
    int t = u; //t存储三个结点中存在的最小的结点的下标,初始化为当前结点u
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点,更新t的下标
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点,更新t的下标
    if (u != t) //如果t==u意味着不用变动,u就是三个结点中拥有最小值的结点下标,否则交换数值
    {
        swap(h[u], h[t]); 
        down(t); //交换数值后,t这个结点存储原本u的值,u存储存储t的值(三个数中的最小值)。u不用调整了,但t情况不明,可能需要调整。直到它比左右子节点都小。
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    cnt = n; //初始化cnt,表示堆中有多少个元素

    //把堆初始化成小根堆,从二叉树的倒数第二行开始,把数字大的下沉
    for (int i = n/2; i; i --) down(i);
    
    while (m --)
    {
        cout << h[1] << ' '; //输出堆顶(最小值)
        h[1] = h[cnt --]; ////删除堆顶(用最后一个数覆盖第一个数),并且长度减1
        down(1); //让覆盖好的值继续往下走
    }
    return 0;
}

二、模拟堆

1. 题目描述

维护一个集合,初始时集合为空,支持如下几种操作:

  1. I x,插入一个数 x;
  2. PM,输出当前集合中的最小值;
  3. DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
  4. D k,删除第 k 个插入的数;
  5. C k x,修改第 k 个插入的数,将其变为 x;

现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 N 行,每行包含一个操作指令,操作指令为 I xPMDMD kC k x 中的一种。

输出格式

对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。

每个结果占一行。

数据范围

1 N 1 0 5 1≤N≤10^5
1 0 9 x 1 0 9 −10^9≤x≤10^9
数据保证合法。

输入样例:

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例:

-10
6

2. 思路分析

相关思路在以下的代码注释中。


3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int cnt;  //记录堆中当前数据的多少

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u *2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    int n, m = 0; //m是记录插入的数的个数,m是对应hp中应该存的值
    cin >> n;
    while (n --)
    {
        string op;
        int k, x;
        cin >> op;
        //插入一个数 x
        if (op == "I")
        {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        //输出当前集合中的最小值
        else if (op == "PM") cout << h[1] << endl;
        //删除当前集合中的最小值
        else if (op == "DM")
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        //删除第 k 个插入的数
        else if (op == "D")
        {
            cin >> k;
            k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
            heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
            cnt --;
            up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(k);
        }
        //修改第 k 个插入的数,将其变为 x
        else
        {
            cin >> k >> x;
            h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个,所以可直接传入ph[k]作为参数
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}

第五章 哈希表

一、模拟散列表

1. 题目描述

维护一个集合,支持如下几种操作:

  1. I x,插入一个数 x;
  2. Q x,询问数 x 是否在集合中出现过;

现在要进行 N 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N,表示操作数量。

接下来 N 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 xx 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1 N 1 0 5 1≤N≤10^5
109 x 1 0 9 −109≤x≤10^9

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

2. 思路分析

散列表,也叫哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

开放寻址法:

  • 如果要插入元素的映射位置没有元素,那么直接将该元素放在当前位置;
  • 如果要插入元素的映射位置已经有了元素,那么就以此往后找,如果到了数组末尾还没有找到一个空的位置,就返回数组的头接着找;
  • 为了防止整个数组都找了一遍还没有找到一个空的位置,数组大小通常要开数据范围的2~3倍。

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数 
const int null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    //t表示x映射到哈希表中的位置
    //+N再%N可以避免出现负数
    int t = (x % N + N) % N;
    //冲突情况:当前位置不为空,并且不为x
    while (h[t] != null && h[t] != x)
    {
        t ++;
        if (t == N) t = 0; //如果到了末尾就从头开始
    } //while一定会结束,因为我们的数组范围是开了2~3倍的,所以整个数组不会被完全使用,因此while不会无限循环
    
    //如果x存在哈希表中,返回的t是下标;如果x不在哈希表中,返回的t是x在哈希表中要存储的位置
    return t; 
}

int main()
{
    //把哈希表的值设置成一个不可能被映射到的数,以此来判断该位置有没有被使用
    memset(h, 0x3f, sizeof h);
    
    int n;
    cin >> n;
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

创作不易,如果有帮助到你,请给文章==点个赞和收藏==,让更多的人看到!!!
==关注博主==不迷路,内容持续更新中。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。