蓝桥杯第十六讲--疑难杂题
前言
蓝桥杯官网:蓝桥杯大赛——全国大学生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} Ai−1 中出现过。
如果出现过,则小明会给 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} Ai−1 中出现过。
当 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, 1≤N≤105,
1 ≤ A i ≤ 1 0 6 1≤A_i≤10^6 1≤Ai≤106
输入样例:
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, 1≤n≤105,
1 ≤ K ≤ 1 0 3 , 1≤K≤10^3, 1≤K≤103,
给定的 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 i−1 层,于 j − 1 j - 1 j−1 严格小于 j j j,并且需要用到上一轮的数据,因此需要 j j j 从大到小遍历到 1 1 1,因此可以优化到二维
2.贪心:余数相同时取数组较大的数,因此分别将余数是 0 0 0 到 k − 1 k - 1 k−1 的最大 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 n−1 行,每行三个整数 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, 2≤n≤104,
1 ≤ m ≤ 2 × 1 0 4 , 1≤m≤2×10^4, 1≤m≤2×104,
0 < k ≤ 100 , 0<k≤100, 0<k≤100,
1 ≤ x , y ≤ n 1≤x,y≤n 1≤x,y≤n
输入样例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
模拟散列表
题目要求
题目描述:
维护一个集合,支持如下几种操作:
I x
,插入一个数 x x x;Q x
,询问数 x x x 是否在集合中出现过;
现在要进行 N N N 次操作,对于每个询问操作输出对应的结果。
输入格式:
第一行包含整数 N N N,表示操作数量。
接下来 N N N 行,每行包含一个操作指令,操作指令为 I x
,Q x
中的一种。
输出格式:
对于每个询问指令 Q x
,输出一个询问结果,如果 x x x 在集合中出现过,则输出 Y e s Yes Yes,否则输出 N o No No。
每个结果占一行。
数据范围:
1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105
− 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 −109≤x≤109
输入样例:
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
- 点赞
- 收藏
- 关注作者
评论(0)