算法题目优选（蓝桥杯备战）--3

Ne0inhk

27 Feb 2026 — 17 min read

💗博主介绍：计算机专业的一枚大学生来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏推荐订阅👇🏻
点击进入🌌作者专栏🌌：
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！

前言

这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
注：第一道题洛谷无法提交 Codeforces跳转点击登录（或注册）即可，具体操作在结尾。

深夜调代码的你，可能会觉得此刻的努力像丢进大海的石子，没有回响。

但请相信：你敲下的每一行，都在为未来的自己“存钱”。

这不是简单的重复，而是经验的复利——今天的每个bug、每道难题，都在沉淀为你的“算法直觉”。当某天面对复杂系统时，这种直觉会让你一眼看穿本质。

真正的成长没有捷径，就像好算法需要优化时间复杂度，你的积累也需要通过长期坚持来降低未来学习的“认知成本”。那些反复推敲的深夜，那些想放弃又继续的时刻，正在悄然壮大你解决问题的能力。

别急于求成，要相信细水长流的力量。你现在的坚持，正在编写你未来技术生涯中最关键的底层逻辑。

继续敲下去。时间会证明，这一切都算数。

题目清单

1.Fixed Points

题目：CF347B Fixed Points

解法：分类讨论
假设在正确位置上的数字个数为 cnt ，扫描所有数：

如果所有数字都在正确的位置上，也就是 cnt = n，可以直接输出(cnt) n；

如果有 2 个数字交换位置，可以将这两个数字交换位置，所以答案为cnt + 2；

如果没有 2 个数字交换位置，最好的⽅案是让其中 1 个数回到正确位置，答案为cnt + 1。

代码：

#include<iostream>usingnamespace std;int n;constint N =1e5+10;int a[N];intmain(){ cin >> n;int cnt =0;for(int i =0; i < n; i++){ cin >> a[i];if(a[i]== i) cnt++;}if(cnt == n) cout << n << endl;else{for(int i =0; i < n; i++){if(i != a[i]&& i == a[a[i]]){ cout << cnt +2<< endl;return0;}} cout << cnt +1<< endl;}return0;}

2.能量项链

题目：P1063 [NOIP 2006 提高组] 能量项链

解法：区间dp
1.状态表示：f[i] [j]表示：合并区间 [i, j] 的项链，最多能释放多少的能量。max（f[i] [n + i]）就是最终结果。

2.状态转移⽅程：

根据区间的分割点k(i < k < j) ,将区间分成 [i, k] 以及 [k, j] ，注意这道题k的取值范围

以及分割的区间的结果。项链每次需要两个元素，区间长度度最少是2。左边区间合并之后，剩余的元素是a[i]和a[k] ，右边的区间

合并之后必须是a[k]开头才能继续合并。

分割之后再合并的最⼤能量为max(f[i] [k] + f[k] [j] + a[i] * a[k] * a[j])。要的是最⼤能

量，状态转移方程就是所有k变化过程中的最大值。

3.初始化：长度len = 0, 1, 2都不合法，默认0。

4.填表顺序：从3开始枚举区间长度。

代码：

#include<iostream>usingnamespace std;constint N =210;int n;int a[N];int f[N][N];//f[i][j]：合并区间[i,j]项链，最多能释放的能量intmain(){ cin >> n;for(int i =1; i <= n; i++){ cin >> a[i]; a[i + n]= a[i];//处理环形,倍增区间 }//区间dp for(int len =3; len <= n +1; len++){for(int i =1; i + len -1<= n + n; i++)//右端点范围 {int j = i + len -1;for(int k = i +1; k < j; k++)//i < k < j{//[i,k] [k,j] f[i][j]=max(f[i][j], f[i][k]+ f[k][j]+ a[i]* a[k]* a[j]);}}}int ret =0;for(int i =1; i <= n; i++){ ret =max(ret, f[i][i + n]);} cout << ret << endl;return0;}

3.最长路

题目：P1807 最长路

解法：1.转化为最短路 + bellman-ford算法/spfa算法(通解)

时间复杂度：O（nm）

用于对负边权，dijkstra出错。

这里不存在负环。

可以读入的时候转化为相反数，将题目转化为有负边权的单源最短路问题。

注意结果要取相反数。

bf:不断尝试对图上每⼀条边进行松弛(更新最短路)，直到所有的点都无法松弛为止。

spfa: ⽤队列对 bf算法做优化。

bf:

//bf算法#include<iostream>#include<queue>#include<vector>usingnamespace std;typedef pair<int,int> PII;constint N =5e4+10, INF =1e9;int n, m; vector<PII> edges[N];int dist[N];//起点到该点的路径长度bool st[N];//标记哪些结点在队列中int s =1;//起点 voidspfa(){for(int i =1; i <= n; i++) dist[i]= INF; queue<int> q; q.push(s); dist[s]=0; st[s]=true;while(q.size()){auto u = q.front(); q.pop(); st[u]=false;for(auto& t : edges[u]){int v = t.first, w = t.second;if(dist[u]+ w < dist[v]){ dist[v]= dist[u]+ w;if(!st[v]){ q.push(v); st[v]=true;}}}}if(dist[n]==1e9) cout <<-1<< endl;////注意这里用1e9else cout <<-dist[n]<< endl;//相负数}intmain(){ cin >> n >> m;for(int i =1; i <= m; i++){int u, v, w; cin >> u >> v >> w; edges[u].push_back({v,-w});}spfa();return0;}

spfa:

//spfa算法#include<iostream>#include<queue>#include<vector>usingnamespace std;typedef pair<int,int> PII;constint N =5e4+10, INF =1e9;int n, m, s =1; vector<PII> edges[N];int dist[N];voidbf(){for(int i =1; i <= n; i++) dist[i]= INF; dist[s]=0;bool flag =false;for(int i =1; i <= n; i++){ flag =false;for(int u =1; u <= n; u++){if(dist[u]== INF)continue;//防溢出 for(auto& t : edges[u]){int v = t.first, w = t.second;if(dist[u]+ w < dist[v]){ dist[v]= dist[u]+ w; flag =true;}}}if(flag ==false)break;}if(dist[n]==1e9) cout <<-1<< endl;//注意这里用1e9else cout <<-dist[n]<< endl;//相负数}intmain(){ cin >> n >> m;for(int i =1; i <= m; i++){int u, v, w; cin >> u >> v >> w; edges[u].push_back({v,-w});}bf();return0;}

2.拓扑排序 + 动态规划（妙解）
时间复杂度： O（n + m）
边是按点顺序指向的，对于任意⼀条边 u->v，u 都是小于 v 的。因此，1 绝对是入度为 0 的点，n

绝对是出度为 0 的点。并且图中没有环形结构，是⼀个拓扑图。在拓扑图中，可以看做 1 为起点，n 为

终点。那么就可以利用拓扑排序的过程，更新出最长路。

可以用动态规划进行更新结点路径长度。

细节：可能还有其他入度为0的点，要对其后点进行删边，减入度处理，之后的点也可能会有这种情况。

动态规划的逻辑：

1.状态表示： f[i] 表示从 1 走到 i 位置的最长路。结果：f[n]。

2.状态转移方程： f[i] = max(f[prev] + w) ，其中 prev 为 i 结点的前驱结点，w 为 i->prev

的权值。

3.初始化，全部0即可；f[1] = 0;

4.更新顺序：按照拓扑排序的处理顺序。

注意：memset(f, 0x3f, sizeof f) == 0x3f3f3f3f, 但是memset(f, -0x3f, sizeof f) == -0x3f3f3f3f。这里涉及到数据存储的问题。记住既要初始化为负无穷，又要用它就用 -1e9。

#include<iostream>#include<queue>#include<vector>usingnamespace std;constint N =5e4+10;typedef pair<int,int> PII; vector<PII> edges[N];int in[N];//入度 int f[N];//int n, m;intmain(){ cin >> n >> m;for(int i =1; i <= m; i++){int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); in[v]++;} queue<int> q;//1.先处理除了结点 1外，入度为 0的结点，删边for(int i =2; i <= n; i++){if(in[i]==0) q.push(i); f[i]=-1e9;//有负数，用于比较大小，求max }while(q.size())//类似层序遍历的逻辑 {auto u = q.front(); q.pop();for(auto& t : edges[u]){int v = t.first; in[v]--;//删除点u,连在u后面的边入度全部 -1 if(in[v]==0) q.push(v);//如果删边后入度也为0，进行同样的处理 }}//2.拓扑排序  q.push(1);while(q.size()){auto u = q.front(); q.pop();for(auto& t : edges[u]){int v = t.first, w = t.second; f[v]=max(f[v], f[u]+ w); in[v]--;if(in[v]==0) q.push(v);}}if(f[n]==-1e9) cout <<-1<< endl;else cout << f[n]<< endl;return0;}

4.均分纸牌

题目：P1031 [NOIP 2002 提高组] 均分纸牌

解法：贪心 + 分类讨论
1.先求出全部均分后的平均数x, 移动次数为cnt.

移动顺序：从左往右，不够的打上欠的个数。这种贪心策略能达到最优解。

分类讨论：（1）a[i] = x, 不需要调整;

（2）a[i] < x, 需要加 x - a[i] 张纸牌， a[i + 1] -= x - a[i], cnt++;

（3）a[i] > x, 需要减a[i] - x, a[i + 1] += a[i] - x, cnt++。

代码：

#include<iostream>usingnamespace std;constint N =110;int n, x;int a[N];intmain(){ cin >> n;for(int i =1; i <= n; i++){ cin >> a[i]; x += a[i];} x /= n;int ret =0;for(int i =1; i <= n; i++){if(a[i]== x)continue; ret++; a[i +1]-= x - a[i];} cout << ret << endl;return0;}

5.扫雷游戏

题目：P2670 [NOIP 2015 普及组] 扫雷游戏

解法：模拟
遍历方式，用于八连通问题的技巧，八个方向的遍历，两层for循环, 细节： 去掉本身位置；通用的是设方向向量。

代码：

#include<iostream>usingnamespace std;constint N =110;int n, m;char a[N][N];//1.设置方向向量int dx[]={0,-1,0,1,-1,1,-1,0,1};int dy[]={0,1,1,1,0,0,-1,-1,-1};intmain(){ cin >> n >> m;for(int i =1; i <= n; i++)for(int j =1; j <= m; j++) cin >> a[i][j];for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(a[i][j]=='*') cout <<'*';else{int cnt =0;for(int k =1; k <=8; k++){int x = dx[k]+ i, y = dy[k]+ j;if(a[x][y]=='*') cnt++;}// int cnt = 0;// for(int dx = -1; dx <= 1; dx++) //2.用于八连通问题的遍历方式 // {// for(int dy = -1; dy <= 1; dy++)// {// if(!dx && !dy) continue; // int x = i + dx, y = j + dy;// if(a[x][y] == '*') cnt++;// }// } cout << cnt;}} cout << endl;}return0;}

6.Decrease

题目：P6070 『MdOI R1』Decrease

解法：二维差分

对二维区间进行修改，首先想到二维差分（差分矩阵）。要把原来的矩阵（二维数组）都修改为0，那么二维差分数组也要多变为0.

原矩阵修改一个k * k的子矩阵，对应修改差分数组四个端点的值。

枚举左上角（i， j）, 范围： 1 <= i, j <= (n - k + 1);

差分数组： f[i] [j] , 操作次数： abs(f[i] [j]), 加绝对值。最后再扫描一遍整个矩阵看是否满足条件。

代码：

#include<iostream>#include<cmath>usingnamespace std;typedeflonglong LL;constint N =5e3+10;int n, m, k; LL f[N][N];//二维差分voidinsert(int x1,int y1,int x2,int y2,int k){ f[x1][y1]+= k; f[x1][y2 +1]-= k; f[x2 +1][y1]-= k; f[x2 +1][y2 +1]+= k;}intmain(){ cin >> n >> m >> k;for(int i =1; i <= m; i++){int x, y, z; cin >> x >> y >> z;insert(x, y, x, y, z);} LL ret =0;for(int x1 =1; x1 <= n - k +1; x1++){for(int y1 =1; y1 <= n - k +1; y1++){ ret +=abs(f[x1][y1]);//操作数是其绝对值int x2 = x1 + k -1, y2 = y1 + k -1;insert(x1, y1, x2, y2,-f[x1][y1]);}}//判断不满足的 for(int i =1; i <= n; i++)for(int j =1; j <= n; j++)if(f[i][j]!=0){ cout <<-1<< endl;return0;} cout << ret << endl;return0;}

7.字串变换

题目：P1032 [NOIP 2002 提高组] 字串变换

解法：bfs解决最短路问题

将一个字符串变成另一个字符串，变化代价是1，把所有字符串当成一个点，跑一遍bfs.

1.如何统计最短路：

之前常用 int dist[i]，这里还要记录字符串，用unordered_map<string, int> 来记录最短路；

substr(起点，切的长度)，substr(从该点及之后的长度)，find(返回找到的第一个下标)，没找到返回-1。

2.如何变换：

这里涉及多次使用字符串的两个接口 find(), substr()两个接口，要熟练运用;

string tmp = s.substr(0, pos) + y + s.substr(pos + x.size())

3.细节：

一个字符串有多个地方可以变换，用pos记录变换的位置;

int pos = 0; pos = s.find(x, pos); pos++。

代码：

#include<iostream>#include<queue>#include<unordered_map>usingnamespace std;constint N =10; string a, b; unordered_map<string,int> dist;// <该点字符串,起点到该点的距离> int n;//变化规则个数 string x[N], y[N];intbfs(){if(a == b)return0;//特判  queue<string> q; q.push(a); dist[a]=0;while(q.size()){ string s = q.front(); q.pop();if(dist[s]>=10)return-1;//剪枝//变化for(int i =0; i < n; i++){//x[i] -> y[i]int pos =0;while(s.find(x[i], pos)!=-1){ pos = s.find(x[i], pos);//拼接 string tmp = s.substr(0, pos)+ y[i]+ s.substr(pos + x[i].size()); pos++;//细节：pos++提前，防止后面continue //s中tmpif(dist.count(tmp))continue;//之前出现过，剪枝  dist[tmp]= dist[s]+1; q.push(tmp);if(tmp == b)return dist[tmp];//剪枝：提前返回 }}}return-1;}intmain(){ cin >> a >> b;while(cin >> x[n]>> y[n]) n++;int ret =bfs();if(ret ==-1) cout <<"NO ANSWER!"<< endl;else cout << ret << endl;return0;}

8.矩形

题目：P4537 [CQOI2007] 矩形

解法：暴搜 dfs
这道题难在对问题的转化：分割的过程就像是从矩阵的四边，从不是四角的点中选择⼀个点进⼊，然后在矩阵里面随意⾛，直到

⾛到⼀个点出去。所以总的分割方案应该和走法是一一对应的。

细节：
1.为什么不从四角走，因为要么不合法，要么于其他方案重复；

2.因为矩阵是对称的，从左进与从右进的方案数应该相等；同理，从上进与从下进的方案数应该相等；所以总的方案数可以（上 +左）* 2，但是，有个注意的点，左进上出与上进左出虽然是两种走法，但是分割出的图形是一样的，所以总的方案数应该 / 2，所以进而推出总的方案数：（上 + 左）。

且注意，这道题不能分割包围的情况，更证明方法的适用性。

这样分割图形问题就转化为路径问题。

暴搜 dfs：

细节：
1.这里不用判断越界，因为递归出口就是边界，达到，方案数++;

2.要特殊处理0的位置，（因为只能0 ->）直接到1，便于dfs的逻辑相同(四个方向)；

3.每次dfs后要，恢复现场（回溯），将true置为false，用于下次递归。

代码：

#include<iostream>usingnamespace std;constint N =10;int n, m;bool st[N][N];//标记是否走过int ret;//方向向量int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};voiddfs(int i,int j){if(i <1|| i >= n || j <1|| j >= m){ ret++;return;} st[i][j]=true;for(int k =0; k <4; k++){int x = i + dx[k], y = j + dy[k];//不用判断边界,因为就是要走到边界 if(!st[x][y])dfs(x, y);//为走过 } st[i][j]=false;}intmain(){ cin >> n >> m;//从上开始for(int j =1; j < m; j++){ st[0][j]=true;dfs(1, j); st[0][j]=false;//恢复现场，回溯 }//从左开始for(int i =1; i < n; i++){ st[i][0]=true;dfs(i,1); st[i][0]=false;//恢复现场，回溯 } cout << ret << endl;return0;}