前言
蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十六讲：疑难杂题
本篇博客所包含习题有：
👊修改数组
👊倍数问题
👊距离
👊模拟散列表
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
修改数组
来源： 第十届蓝桥杯省赛C++A/研究生组,第十届蓝桥杯省赛JAVAA/研究生组
题目要求
题目描述：
输入格式：
输出格式：
数据范围：
输入样例：
5 2 1 1 3 4
输出样例：
2 1 3 4 5
思路分析
代码
#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; }
倍数问题
来源： 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组
题目要求
题目描述：
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。
数据保证一定有解。
输入格式：
输出格式：
输出一行一个整数代表所求的和。
数据范围：
输入样例：
4 3 1 2 3 4
输出样例：
9
思路分析
优化：
代码
#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; }
