蓝桥杯速成刷题清单（上）

一、1.排序 - 蓝桥云课

（快速排序）算法代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int a[N];int main() {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;for (int i = n - 1; i >= 0; i--) {cout << a[i] << " ";}cout << endl;/*reverse(a,a+n);for (int i = 0; i < n; i++) {cout << a[i] << " ";}*/return 0;
}

---

二、2.走迷宫 - 蓝桥云课

（BFS）算法代码：

#include <bits/stdc++.h>
using namespace std;int n, m; // 地图大小
int start_x, start_y, end_x, end_y; // 起始点和终点（1-based）
vector<vector<int>> mp; // 地图（0-based）
vector<vector<int>> path_len; // 记录路径长度
typedef pair<int, int> PII;// 四个方向偏移量
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};int main() {cin >> n >> m;mp.resize(n, vector<int>(m));path_len.resize(n, vector<int>(m, -1)); // 初始化为-1// 输入地图（按行优先顺序，1-based转换为0-based）for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> mp[i][j];}}// 输入起始点和目标点坐标（1-based）cin >> start_x >> start_y >> end_x >> end_y;// 转换为0-basedstart_x--; start_y--; end_x--; end_y--;queue<PII> q;q.push({start_x, start_y});path_len[start_x][start_y] = 0; // 起点算作1个格子while (!q.empty()) {PII tmp = q.front();q.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = tmp.first + dx[i];int ny = tmp.second + dy[i];// 检查边界if (nx < 0 || ny < 0 || nx >= n || ny >= m) {continue;}// 检查障碍物和是否已访问if (mp[nx][ny] == 0 || path_len[nx][ny] != -1) {continue;}path_len[nx][ny] = path_len[tmp.first][tmp.second] + 1;q.push({nx, ny});}}// 输出结果（若无法到达则输出-1）cout << path_len[end_x][end_y] << endl;return 0;
}

---

三、3.小明的背包1 - 蓝桥云课

算法代码：

贪心、但只能通过18.2%：

#include <iostream>
#include <algorithm>
using namespace std;struct Item {int w, v;
};// 定义结构体的比较规则
bool cmp(const Item& a, const Item& b) {if (a.v == b.v) {return a.w < b.w;}return a.v > b.v;
}int main() {int n, V;  // 注意这里改为大写的V表示背包容量cin >> n >> V;  // 必须先读取n和V的值Item items[105];for (int i = 0; i < n; i++) {cin >> items[i].w >> items[i].v;}// 按价值从大到小来排列sort(items, items + n, cmp);// 从价值最大的物品放入int sum = 0;int remaining = V;  // 剩余容量for (int i = 0; i < n; i++) {if (remaining >= items[i].w) {sum += items[i].v;remaining -= items[i].w;}}cout << sum << endl;return 0;
}

 动态规划：

#include<bits/stdc++.h>
using namespace std;const int MAXN = 110;
const int MAXV = 1010;int N, V;
int w[MAXN], v[MAXN];
int f[MAXN][MAXV];int main() {cin >> N >> V;for (int i = 1; i <= N; i++) {cin >> w[i] >> v[i];}memset(f, 0, sizeof(f));for (int i = 1; i <= N; i++) {for (int j = 0; j <= V; j++) {f[i][j] = f[i - 1][j];//不放if (j >= w[i])// 背包还有空间{f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);}}}cout << f[N][V] << endl;return 0;
}

---

四、4.蓝桥公园 - 蓝桥云课

（Floyd）算法代码： 

#include<bits/stdc++.h>
using namespace std;
using ll =long long;
const int N=500;
ll inf=1e18;
ll n,m,q;
ll d[N][N];
int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=inf;}}for(int i=1;i<=n;i++)d[i][i]=0;while(m--){ll u,v,w;cin>>u>>v>>w;d[u][v]=min(d[u][v],w);d[v][u]=min(d[v][u],w); }for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}while(q--){int st,ed;cin>>st>>ed;cout<<(d[st][ed]>=inf ? -1 : d[st][ed])<<endl;}return 0;
}

---

五、5.回文判定 - 蓝桥云课

（字符串、模拟、双指针）算法代码： 

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;cin>>s;int left=0;int right=s.size()-1;while(left<right){if(s[left]!=s[right]){cout<<"N"<<endl;return 0;}left++;right--;}cout<<"Y"<<endl;return 0;
}

---

六、6.小明的彩灯 - 蓝桥云课

（差分）算法代码： 

#include <iostream>
#include <vector>
#define int long long 
using namespace std;signed main() {int n, q;cin >> n >> q;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> d(n + 1, 0);  // 差分数组，长度为 n+1for (int i = 0; i < q; i++) {int l, r, x;cin >> l >> r >> x;d[l] += x;if (r < n) {d[r + 1] -= x;}}// 对差分数组进行前缀和操作，即可得到每个彩灯的最终亮度for (int i = 1; i <= n; i++) {d[i] += d[i - 1];a[i - 1] += d[i];if (a[i - 1] < 0) {a[i - 1] = 0;}}for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;return 0;
}

---

七、7.解立方根 - 蓝桥云课

（二分）算法代码：（只能25%，这个题有问题） 

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;const double eps = 1e-8;double cube_root(double x) {double l = 0, r = x;while (r - l > eps) {double mid = (l + r) / 2;if (mid * mid * mid < x) {l = mid;} else {r = mid;}}return l;
}int main() {int T;cin >> T;while (T--) {int x;cin >> x;double ans = cube_root(x);printf("%.3f\n", ans);}return 0;
}

---

八、10.蓝桥骑士 - 蓝桥云课

（LIS）算法代码： 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> S;for (int i = 0; i < n; i++) {if (S.empty() || a[i] > S.back()) {S.push_back(a[i]);} else {auto it = lower_bound(S.begin(), S.end(), a[i]);*it = a[i];}}cout << S.size() << endl;return 0;
}

---

九、8.蓝桥幼儿园 - 蓝桥云课

（并查集）算法代码：

#include <iostream>
#include <vector>using namespace std;const int MAXN = 2e5 + 5;int fa[MAXN];// 并查集的查找操作
int find(int x) {if (fa[x] != x) {fa[x] = find(fa[x]);}return fa[x];
}int main() {int n, m;cin >> n >> m;// 初始化每个人的父亲为自己for (int i = 1; i <= n; ++i) {fa[i] = i;}// 处理操作while (m--) {int op, x, y;cin >> op >> x >> y;if (op == 1) {int fx = find(x), fy = find(y);// 将两个人所在的连通分量合并if (fx != fy) {fa[fx] = fy;}} else {int fx = find(x), fy = find(y);// 判断两个人是否在同一个连通分量中if (fx == fy) {cout << "YES" << endl;} else {cout << "NO" << endl;}}}return 0;
}

---

十、9.蓝桥王国 - 蓝桥云课

（Dijkstra）算法代码： 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 3e5 + 2;struct Edge {int from, to;long long weight;Edge(int u, int v, long long w) : from(u), to(v), weight(w) {}
};vector<Edge> edges[MAXN];struct Node {int id;long long dis;Node(int i, long long d) : id(i), dis(d) {}bool operator<(const Node& other) const {return dis > other.dis;}
};int n, m;
long long dist[MAXN];void dijkstra() {int start = 1;bool visited[MAXN] = {false};for (int i = 1; i <= n; i++) {dist[i] = INF;visited[i] = false;}dist[start] = 0;priority_queue<Node> pq;pq.push(Node(start, dist[start]));while (!pq.empty()) {Node u = pq.top();pq.pop();if (visited[u.id])continue;visited[u.id] = true;for (int i = 0; i < edges[u.id].size(); i++) {Edge e = edges[u.id][i];if (visited[e.to])continue;if (dist[e.to] > e.weight + u.dis) {dist[e.to] = e.weight + u.dis;pq.push(Node(e.to, dist[e.to]));}}}
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {edges[i].clear();}while (m--) {int u, v, w;cin >> u >> v >> w;edges[u].push_back(Edge(u, v, w));}dijkstra();for (int i = 1; i <= n; i++) {if (dist[i] >= INF) {cout << "-1" << " ";} else {cout << dist[i] << " ";}}return 0;
}