2、算法练习专栏——牛客练习——天梯备赛03

A

题目描述

对输入的字符串进行排序后输出

打开以下链接可以查看正确的代码

1	`https://ac.nowcoder.com/acm/contest/5657#question`

输入描述:

1
2
3

输入有两行，第一行n

第二行是n个字符串，字符串之间用空格隔开

输出描述:

1	`输出一行排序后的字符串，空格隔开，无结尾空格`

示例1

输入

复制

1 2	`5 c d a bb e`

输出

复制

1	`a bb c d e`

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int n;

int main()
{
    int n;
    cin >> n;
    string s[N];
    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n);
    for (int i = 0; i < n; i++) cout << s[i] << " ";

    return 0;
}

B

大雄喜欢二进制。

大雄面前有一个 nnn 个数的序列 aaa，对于一个区间 [l,r][l,r][l,r]，设

ans=(al and al+1 and……and ar−1 and ar)+(al or al+1 or……or ar−1 or ar)ans=(a_l\ \text{and}\ a_{l+1}\ \text{and}……\text{and}\ a_{r-1}\ \text{and}\ a_r ) +(a_l\ \text{or}\ a_{l+1}\ \text{or}……\text{or}\ a_{r-1}\ \text{or}\ a_r)ans=(al and al+1 and……and ar−1 and ar)+(al or al+1 or……or ar−1 or ar)

输出最大的 ansansans 值。

输入描述:

1
2
3

第一行一个正整数 n (1≤n≤105)n\ (1\leq n\leq 10^5)n (1≤n≤105)。

接下来一行 nnn 个非负整数 aia_iai (0≤ai≤109)\ (0\leq a_i\leq 10^9) (0≤ai≤109)。

输出描述:

1	`一个数表示答案。`

示例1

输入

复制

1 2	`5 4 8 2 3 1`

输出

复制

代码

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, Num;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (Num < x) {
            Num = x;
        }
    }
    cout << Num * 2;
    return 0;
}

C

题目描述

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。

ZZT 需要在这个队列上执行 P 次操作，操作分两种：
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。

在 P 次操作之后，ZZT 想知道队列中的元素的排列方式，由于他最近很忙，因此需要请你帮他解决这个问题。

输入描述:

第一行输入一个正整数 N，表示队列的大小。
第二行输入 N 个正整数，Q1, Q2, Q3, ... ..., QN，Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。
第三行输入一个正整数 P，表示接下来要进行的操作次数。

接下来 P 行，第 i 行输入一个字符串 Si 以及一个正整数 Xi，表示一次操作。
1 ≤ N ≤ 105.
1 ≤ Qi ≤ N.
1 ≤ P ≤  105.
Si ∈\in∈ { “FIRST”, “LAST” }.
1 ≤ Xi ≤ 105.

输出描述:

1	`输出 N 个正整数，表示 P 次操作之后的队列。`

示例1

输入

复制

4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1

输出

复制

4 3 2 1

代码

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII q[N];
int n, p;
 
bool cmp(PII a,PII b){
    return a.second < b.second;
}
 
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        q[x] = {x, i};
    }
    int l = 0, r = n + 1;
    cin >> p;
    while (p--) {
        int x;
        string s;
        cin >> s >> x;
        if (s == "FIRST") {
            q[x].second = l--;
        } else {
            q[x].second = r++;
        }
    }
    sort(q + 1,q + n + 1, cmp);
   for (int i = 1; i <= n; i++) cout << q[i].first << " ";
    return 0;
}

D

题目描述

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：

l 根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；

l 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；

l 在满足上述条件下，该单词查找树的节点数最少。

例：图一的单词列表对应图二的单词查找树

对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）

输入描述:

为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据。

输出描述:

1	`该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。`

示例1

输入

复制

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

输出

复制

代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, ans;
int son[N][26], idx;
void Tire(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'A';
        if (!son[p][u]) 
        {
            son[p][u] = ++idx;
        }
        p = son[p][u];
    }
    
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    char op[N];
    while (cin >> op) {
        Tire(op);
    }
    
    cout << idx + 1;
    return 0;
}

E

链接：https://ac.nowcoder.com/acm/contest/75962/E
来源：牛客网

题目描述

给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们

输入描述:

1 2	`第一行一个数表示n 之后n行每行一个字符串表示给定的字符串`

输出描述:

1
2
3

第一行输出一个数x表示可行的字符串个数
之后输出x行，每行输出一个可行的字符串
输出的顺序和输入的顺序一致

示例1

输入

复制

6
mcfx
ak
ioi
wen
l
a

输出

复制

5
mcfx
ioi
wen
l
a

备注:

1
2
3

对于100%的数据，
n <= 30000 , 字符串总长<= 300000
字符集为小写字符

代码

扩展

一、模拟散列表（简单+）

维护一个集合，支持如下几种操作：

I x，插入一个整数 x；
Q x，询问整数 x 是否在集合中出现过；

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

输入格式

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

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

输出格式

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

每个结果占一行。

数据范围

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

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

1
2

Yes
No

思路

思路一（无脑）： 使用< map > 或者 < unordered_map>
思路二（哈希）： 使用拉链法的思想
思路三（哈希）： 使用寻址法的思想

代码

思路一答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
#include < unordered_map>
using namespace std;
const int N = 1e5 + 10;
map Map;
int n;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    while (n--)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if (op[0] == 'I') 
        {
            Map[x] = x;
            if (x == 0) Map[x] = 1;
        }
        else if (Map[x] == 0) cout << "No\n";
        else cout << "Yes\n";
    }  
    return 0;
}

思路二答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
#include < cstring>
using namespace std;
const int N = 100003;
int arr[N], e[N], ne[N], idx;
int n;
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = arr[k];
    arr[k] = idx++;
}
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = arr[k]; ~i; i = ne[i])
    {
        if (e[i] == x) return true;
    } 
    return false;
}
int main()
{   
    cin >> n;
    memset(arr, -1, sizeof arr);
    for (int i = 0; i < n; i++)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);        
        if (op[0] == 'I') insert(x);
        else 
        {
            if (find(x)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

思路三答案（请自己先思考一下再参考）

        
#include < iostream>
#include < algorithm>
#include < cstring>
using namespace std;
const int null = 0x3f3f3f3f;
const int N = 200003;
int h[N];
int n;
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (N == k) k = 0;
    }
    return k;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    memset(h, 0x3f, sizeof h);
    while (n--)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if (*op == 'I') {
            int k = find(x);
            h[k] = x;
        }
        else {
            if (h[find(x)] != null) cout << "Yes\n";
            else cout << "No\n";
        }
    }    
    return 0;
}

二、哈希字符串

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

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

输入格式

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

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

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

注意，字符串的位置从 11 开始编号。

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤10^5^

输入样例：

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

输出样例：

1
2
3

Yes
No
Yes

思路

求哈希值

代码

答案（请自己先思考一下再参考）

        
#include < iostream> 
#include < algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131;
char str[N];
ULL p[N], h[N];
int n, m;
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> str + 1;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] += h[i - 1] * P + str[i];
    }    
    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;
}