蓝桥杯第十六讲--疑难杂题

举报
辰chen 发表于 2022/06/15 00:23:46 2022/06/15
【摘要】 文章目录 前言修改数组题目要求思路分析代码 倍数问题题目要求思路分析代码 距离题目要求思路分析代码 模拟散列表题目要求思路分析代码 前言 蓝桥杯官网:蓝桥杯大赛——全国大学...

前言

蓝桥杯官网:蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识,此博客为第十六讲:疑难杂题

本篇博客所包含习题有:
👊修改数组
👊倍数问题
👊距离
👊模拟散列表

博客内容以题代讲,通过讲解题目的做法来帮助读者快速理解算法内容,需要注意:学习算法不能光过脑,更要实践,请读者务必自己敲写一遍本博客相关代码!!!


修改数组

来源: 第十届蓝桥杯省赛C++A/研究生组,第十届蓝桥杯省赛JAVAA/研究生组

题目要求

题目描述:

给定一个长度为 N N N 的数组 A = [ A 1 , A 2 , ⋅ ⋅ ⋅ A N ] A=[A_1,A_2,⋅⋅⋅A_N] A=[A1,A2,AN],数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 A 2 , A 3 , ⋅ ⋅ ⋅ , A N A_2,A_3,⋅⋅⋅,A_N A2,A3,,AN

当修改 A i A_i Ai 时,小明会检查 A i A_i Ai 是否在 A 1 A_1 A1 A i − 1 A_{i−1} Ai1 中出现过。

如果出现过,则小明会给 A i A_i Ai 加上 1 1 1;如果新的 A i A_i Ai 仍在之前出现过,小明会持续给 A i A_i Ai 1 1 1,直到 A i A_i Ai 没有在 A 1 A_1 A1 A i − 1 A_{i−1} Ai1 中出现过。

A N A_N AN 也经过上述修改之后,显然 A A A 数组中就没有重复的整数了。

现在给定初始的 A A A 数组,请你计算出最终的 A A A 数组。

输入格式:

第一行包含一个整数 N N N

第二行包含 N N N 个整数 A 1 , A 2 , ⋅ ⋅ ⋅ , A N A_1,A_2,⋅⋅⋅,A_N A1,A2,,AN

输出格式:

输出 N N N 个整数,依次是最终的 A 1 , A 2 , ⋅ ⋅ ⋅ , A N A_1,A_2,⋅⋅⋅,A_N A1,A2,,AN

数据范围:

1 ≤ N ≤ 1 0 5 , 1≤N≤10^5, 1N105,
1 ≤ A i ≤ 1 0 6 1≤A_i≤10^6 1Ai106

输入样例:

5
2 1 1 3 4

  
 
  • 1
  • 2

输出样例:

2 1 3 4 5

  
 
  • 1

思路分析

考察并查集的一道题目,关于并查集的算法讲解详见博客:并查集

单链表式并查集,用 p [ i ] p[i] p[i] 表示值为 i i i 指向哪一个数,若 p[i] == i; 表示是第一次出现,否则就是用递归,从 j j j 开始找到 p[i] == i; ,并使 p[i] += 1;

代码

#include <cstdio>

const int N = 1100010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 1; i < N; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        x = find(x);
        printf("%d ", x);
        p[x] = x + 1;
    }

    return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

倍数问题

来源: 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组

题目要求

题目描述:

众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。

但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。

现在小葱给了你 n n n 个数,希望你从这 n n n 个数中找到三个数,使得这三个数的和是 K K K 的倍数,且这个和最大。

数据保证一定有解。

输入格式:

第一行包括 2 2 2 个正整数 n ,   K n, K n,K

第二行 n n n 个正整数,代表给定的 n n n 个数。

输出格式:

输出一行一个整数代表所求的和。

数据范围:

1 ≤ n ≤ 1 0 5 , 1≤n≤10^5, 1n105,
1 ≤ K ≤ 1 0 3 , 1≤K≤10^3, 1K103,
给定的 n n n 个数均不超过 1 0 8 10^8 108

输入样例:

4 3
1 2 3 4

  
 
  • 1
  • 2

输出样例:

9

  
 
  • 1

思路分析

在这里插入图片描述
优化:

1.由于第 i i i 层只用到第 i − 1 i - 1 i1 层,于 j − 1 j - 1 j1 严格小于 j j j,并且需要用到上一轮的数据,因此需要 j j j 从大到小遍历到 1 1 1,因此可以优化到二维

2.贪心:余数相同时取数组较大的数,因此分别将余数是 0 0 0 k − 1 k - 1 k1 的最大 3 3 3 个数挑出来处理即可,最多挑出 3 × 1000 3 \times1000 3×1000 个数进行处理

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n, m;
vector<int> a[N];
int f[4][N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        a[x % m].push_back(x);
    }

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i < m; i ++ )
    {
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end());

        for (int u = 0; u < 3 && u < a[i].size(); u ++ )
        {
            int x = a[i][u];
            for (int j = 3; j >= 1; j -- )
                for (int k = 0; k < m; k ++ )
                    f[j][k] = max(f[j][k], f[j - 1][(k - x % m + m) % m] + x);
        }
    }

    printf("%d\n", f[3][0]);

    return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

距离

题目要求

题目描述:

给出 n n n 个点的一棵树,多次询问两点之间的最短距离。

注意:

  • 边是无向的。
  • 所有节点的编号是 1 , 2 , … , n 1,2,…,n 1,2,,n

输入格式:

第一行为两个整数 n n n m m m n n n 表示点数, m m m 表示询问次数;

下来 n − 1 n−1 n1 行,每行三个整数 x , y , k x,y,k x,y,k,表示点 x x x 和点 y y y 之间存在一条边长度为 k k k

再接下来 m m m 行,每行两个整数 x , y x,y x,y,表示询问点 x x x 到点 y y y 的最短距离。

树中结点编号从 1 1 1 n n n

输出格式:

m m m 行,对于每次询问,输出一行询问结果。

数据范围:

2 ≤ n ≤ 1 0 4 , 2≤n≤10^4, 2n104,
1 ≤ m ≤ 2 × 1 0 4 , 1≤m≤2×10^4, 1m2×104,
0 < k ≤ 100 , 0<k≤100, 0<k100,
1 ≤ x , y ≤ n 1≤x,y≤n 1x,yn

输入样例1:

2 2 
1 2 100 
1 2 
2 1

  
 
  • 1
  • 2
  • 3
  • 4

输出样例1:

100
100

  
 
  • 1
  • 2

输入样例2:

3 2
1 2 10
3 1 15
1 2
3 2

  
 
  • 1
  • 2
  • 3
  • 4
  • 5

输出样例2:

10
25

  
 
  • 1
  • 2

思路分析

T a r j a n Tarjan Tarjan – 离线求 L C A LCA LCA
在线做法:读一个询问,处理一个,输出一个
离线做法:读完全部询问,再全部处理完,再全部输出

在深度优先遍历时,将所有点分成三大类

2 2 2 号点:代表已经访问并结束回溯

1 1 1 号点:代表正在访问

0 0 0 号点:代表还没有访问过

其中所有 2 2 2 号点和正在搜索的 1 1 1 号点路径中已经通过并查集合并成一个集合

在这里插入图片描述

1.先求出所有点到根结点的距离 d e p t h depth depth,设 x x x 号点和 y y y 号点的最近公共祖先是 p p p,则 x x x y y y 的最近距离等于 d e p t h [ x ] + d e p t h [ y ] − 2 × d e p t h [ p ] depth[x] + depth[y] - 2 \times depth[p] depth[x]+depth[y]2×depth[p]

2.在深度优先遍历 1 1 1 号点中的 u u u 点的时候,需要把 u u u 的查询的另外一个点的最短距离进行计算并存储,最后把 u u u 点合并到上一结点的集合

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M * 2];
int st[N];
vector<PII> query[N];   // first存查询的另外一个点,second存查询编号

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }

    for (auto item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    st[u] = 2;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);
    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99

模拟散列表

题目要求

题目描述:

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

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

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

输入格式:

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

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

输出格式:

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

每个结果占一行。

数据范围:

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

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

输出样例:

Yes
No

  
 
  • 1
  • 2

思路分析

板子题,需要对代码关键部分进行背诵,详细的代码逻辑解释见博客:哈希表

代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

文章来源: chen-ac.blog.csdn.net,作者:辰chen,版权归原作者所有,如需转载,请联系作者。

原文链接:chen-ac.blog.csdn.net/article/details/122794627

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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