算法题目优选（蓝桥杯备战）--1
💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
分享
1.用我们老师的话：保持⼀颗平常心，承认自己的不足：我们大部分人都不是过目不忘的天才，因此学了就忘是非常非常正常的现象。及时复习，重复学习，这很重要。
2.保持热情，这也尤为重要，一天学一点也可以，把它当作一种奖励，放松，像打怪通关一样，可以成为一种长期的习惯，学无止尽。
3.不要追求数量，更多的是质量，你对这道题的收获，理解对相应算法的运用。
4.学习算法的意义：锻炼自己的代码逻辑思维，解决问题的能力，打比赛，奖学金，求职面试考察算法题。
5.最重要的是，那种AC的感觉是真的爽！
题目清单
1.借教室
解法：差分数组 + 二分查找
因为要对一个区间进行一样的处理，同时减去一个数，想到差分数组；
但是，局限性：差分数组都是先统一修改，后再单独统一查询，O(n); 这里要一边修改，一边判断，O(n^2);
可以用进阶算法线段树O（nlogm）,但这道题可用更简单的方法，用二分查找位置，再用判断，O(nlogm);
差分数组：
关键：对差分数组做一次前缀和,并判断有没有不满足条件的，是否都>= 0。
细节：1.二分查找，因为要找第一个不满足条件的位置，且区间[1, m]，找ret的位置，具有二段性，左边不包含ret，可跳过，都满足条件，更新 l = mid + 1； 右边包含，都不满足条件， 不可跳过，r = mid；2. 传入的进行判断,对区间x进行处理时,而不是所有的都处理。
代码：
#include<iostream>usingnamespace std;constint N =1e6+10;int r[N], d[N], s[N], t[N];int f[N];//差分数组int n, m;//处理[1, x]所有订单，看是否可行boolcheck(int x){//初始化差分数组for(int i =1; i <= n; i++) f[i]= r[i]- r[i -1];//对区间进行处理for(int i =1; i <= x; i++)//注意这里是x { f[s[i]]-= d[i]; f[t[i]+1]+= d[i];}//对差分数组做一次前缀和,还原数组，并判断有没有不满足条件的 for(int i =1; i <= n; i++){ f[i]= f[i -1]+ f[i];if(f[i]<0)returnfalse;}returntrue;}intmain(){ cin >> n >> m;for(int i =1; i <= n; i++) cin >> r[i];for(int i =1; i <= m; i++) cin >> d[i]>> s[i]>> t[i];//二分查找int l =1, r = m;while(l < r){int mid =(l + r)/2;if(check(mid)) l = mid +1;//不包含在左侧，跳过else r = mid;}//判断最后二分的找到位置是否满足要求,因为找第一个 if(check(l)) cout <<0<< endl;else cout <<-1<< endl << l << endl;return0;}2.搭配购买
题目：P1455 搭配购买
解法：01背包 + dfs求连通块
用图存：邻接矩阵，把所有搭配的物品连接起来，形成一个大物品，方法：用dfs遍历记录物品的总价值和总价格。
再用这些组合后的物品用01背包的逻辑,细节：用一个cnt存之后物品的个数，方便遍历与存储。
01背包：就是这个物品只能选一次，选或不选。
dp: 1.定义：f[i][j] 前i个物品挑选，总价格不超过j的最大价值，优化一维 f[j];
2.结果 ：f[w];
3.初始化，0;
4. 状态转移方程，根据最后一步选不选来划分，优化掉i,f[j] = max(f[j], f[j - cc[i]] + dd[i]);
5. 更新顺序，都可以，优化一维，倒着遍历，因为用到上面的上一个，和上一个的前面某个，前面更新的值会影响后面的更新。
代码：
#include<iostream>#include<vector>usingnamespace std;constint N =1e4+10;int n, m, w;int c[N], d[N];int cc[N], dd[N];//合并后的物品价格，价值int cnt;//标记个数bool st[N];//标记哪些节点已经访问过了 vector<int> edges[N];//邻接矩阵存图int f[N];//从前i个物品挑选，总价格不超过j的最大价值，优化一维voiddfs(int a){ st[a]=true; cc[cnt]+= c[a]; dd[cnt]+= d[a];for(auto b : edges[a]){if(!st[b])dfs(b);}}intmain(){ cin >> n >> m >> w;for(int i =1; i <= n; i++) cin >> c[i]>> d[i];for(int i =1; i <= m; i++){int a, b; cin >> a >> b;//存无向图 edges[a].push_back(b); edges[b].push_back(a);}for(int i =1; i <= n; i++){if(!st[i]){ cnt++;dfs(i);}}for(int i =1; i <= cnt; i++)for(int j = w; j >= cc[i]; j--)//优化一维，记得逆序遍历,注意这里是cc[i]{ f[j]=max(f[j], f[j - cc[i]]+ dd[i]);} cout << f[w]<< endl;return0;}3.信息传递
解法：拓扑排序 + dfs计数
要求信息传给自己，要传一圈，将这道题转化为求图中最小环大小的问题。
拓扑排序：
是将有向图中的所有结点排序，使得排在前⾯的结点不能依赖于排在后⾯的结
点。
- 将图中所有入度为 0 的点，加⼊到队列中；
- 取出队头元素，删除与该点相连的边。如果删除之后的后继结点的⼊度变为 0，加入到队列中；
- 重复 2 操作，直到图中没有点或者没有入度为 0 的点为止。
1.拓扑排序的过程可以将除了环以外的结点全部打上标记；
2.对所有没有打标记的点做⼀次 dfs，统计⼀下环的大小，然后求出最小环。
代码：
#include<iostream>#include<queue>usingnamespace std;constint N =2e5+10;int n;int ne[N];int in[N];bool st[N];//给遍历过的点打上标记int cnt;//统计环的结点个数voiddfs(int a){ cnt++; st[a]=true;//记得打上标记 int b = ne[a];if(!st[b])dfs(b);}intmain(){ cin >> n;for(int i =1; i <= n; i++){ cin >> ne[i];//i -> ne[i] in[ne[i]]++;}//1.利用拓扑排序给所有环以外的结点打上标记 queue<int> q;for(int i =1; i <= n; i++){if(in[i]==0) q.push(i);//入度为0点入队 }//执行层序遍历的逻辑while(q.size()){auto a = q.front(); q.pop(); st[a]=true;//a -> bint b = ne[a]; in[b]--;//a出队,b的入度-1 if(in[b]==0) q.push(b);}//2.利用dfs计算环的大小int ret = n;for(int i =1; i <= n; i++){if(!st[i])//环 { cnt =0;dfs(i); ret =min(ret, cnt);}} cout << ret << endl;return0;}4.集合 Subset Sums
题目：P1466 [USACO2.2] 集合 Subset Sums
解法：01背包
问题转化：
这道题本质上是让我们从[1, n]中挑⼀些数出来，凑成总和的⼀半，并且每⼀个数在⼀次挑选中只
能被选⼀次，正好是01背包问题求方案数。其中每⼀个数的大小就是体积，总和就是价值。
细节：
1.注意要先判断⼀下是否有解，因为总和可能是奇数，没有⼀半可以凑，结果为0；
2.结果可能很大用long long来存；
3.因为是求总方案数，状态转移方程用+；
4.注意初始化f[0] = 1,用于后续更新；
5.因为两种凑出一半的情况为一个，不考虑顺序，为同一种，结果要 /2。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL;//结果数据可能很大 constint N =45, M =800;int n; LL f[M];//f[i][j]从前i个物品中选 intmain(){ cin >> n;int sum =(1+ n)* n /2;if(sum %2)//if(n & 1), 奇数 { cout <<0<< endl;return0;} sum /=2;//01背包 //注意初始化 f[0]=1;for(int i =1; i <= n; i++){for(int j = sum; j >= i; j--){ f[j]= f[j]+ f[j - i];}} cout << f[sum]/2<< endl;//注意 /2 return0;}5.删数问题
题目：P1106 删数问题
解法：贪心
首先想到先删除最大的数，但是发现先删除大的数这种贪心策略是错的，数：a1a2a3……an-1an,
删除两个数比较：
s1 = a1 * 10^n-2 + a2 * 10^n-3 + ……+ ai * 10^n - i -1 +an - 1;
s2 = a1 * 10^n-2 + a2 * 10^n-3 + ……+ ai+1 * 10^n-i +1 +……+an
发现单调递增，删除最后一个，单调递减删除第一个，出现峰值，删除峰值，且贪心地先处理高位的峰值，从左往右处理；
最终贪心策略：循环k次，每次从⾼位开始遍历整个数位，如果当前位的数字⼤于下⼀位，删除当前位。细节：注意处理前导0
代码：
#include<iostream>usingnamespace std;intmain(){ string s;int k; cin >> s >> k;for(int i =1; i <= k; i++){bool flag =false;for(int j =0; j < s.size()-1; j++)//遍历到倒数第二个即可{//贪心，如果当前位大于下一位，删除 if(s[j]> s[j +1]){ s.erase(j,1);//O(n) flag =true;break;}}if(!flag) s.pop_back();}while(s.size()>1&& s[0]=='0') s.erase(0,1);//处理前导0 cout << s << endl;return0;}6.最接近神的人
题目：P1774 最接近神的人
解法：排序
两两交换，求最小的交换次数。 求逆序对的个数
排序的本质：消除逆序对
1.冒泡排序：
最坏情况会超时，n = 5e5;
时间复杂度：
| 情况 | 时间复杂度 | 比较次数 | 交换次数 |
|---|---|---|---|
| 最好 | O(n) | n-1 | 0 |
| 最坏 | O(n²) | n(n-1)/2 | n(n-1)/2 |
| 平均 | O(n²) | ≈n²/2 | ≈n²/4 |
代码：
intbubbleSort(int a[],int n){int cnt =0;for(int i =1; i < n; i++){bool flag =false;for(int j =1; j <= n - i; j++)if(a[j]> a[j +1]){swap(a[j], a[j +1]); flag =true; cnt++;}if(!flag)break;}return cnt;}2.归并排序
时间复杂度：O（nlogn）
代码：
LL merge_sort(int l,int r){if(l >= r)return0; LL ret =0;int mid =(l + r)/2;//[l, mid] [mid + 1, r] ret +=merge_sort(l, mid); ret +=merge_sort(mid +1, r);int cur1 = l, cur2 = mid +1, i = l;while(cur1 <= mid && cur2 <= r){if(a[cur1]<= a[cur2]){ tmp[i++]= a[cur1++];//有序 }else{ ret += mid - cur1 +1;//1~mid > cur2 tmp[i++]= a[cur2++];}}//剩余有序 while(cur1 <= mid) tmp[i++]= a[cur1++];while(cur2 <= r) tmp[i++]= a[cur2++];for(int j = l; j <= r; j++) a[j]= tmp[j];//排序到原数组 return ret;}7.优秀的拆分
解法：数的二进制表示
没想到这个的话就很难做，用数的二进制表示数的每一位，刚好满足题目的要求，可以注意到题目对数的表示都是用2的权值，对数据进行右移对每一位单独进行处理，然后用（1<< i）恢复输出每一位。细节： 注意首先要用if(n & 1) 或 if(n % 2) 判断是否是奇数，因为最后一位是1不满足要求 。
代码：
#include<iostream>usingnamespace std;int n;intmain(){ cin >> n;if(n &1)//if(n % 2) 判断是否是奇数，因为最后一位是1不满足要求 { cout <<-1<< endl;return0;}for(int i =30; i >=0; i--)//1e7 约2^23~2^24{if((n >> i)&1){ cout <<(1<< i)<<" ";}}return0;}8.领地选择
题目：P2004 领地选择
解法：暴力枚举 + 二维前缀和
题目要在一个n * m的矩阵中，找出一个最大的 c * c 方块领地的和。
暴力枚举出所有边长为c的正方形，左上角下标；
先预处理出一个，二位前缀和数组，可极大降低时间复杂度，用难点：要处理下标的细节。
细节：领地的值有负数，要用一个负无穷来更新最大值更合理。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =1e3+10;int n, m, c; LL f[N][N];intmain(){ cin >> n >> m >> c;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){int x; cin >> x; f[i][j]= f[i -1][j]+ f[i][j -1]- f[i -1][j -1]+ x;}} LL ret =-1e18;int x, y;for(int x1 =1; x1 <= n - c +1; x1++){for(int y1 =1; y1 <= m - c +1; y1++){int x2 = x1 + c -1, y2 = y1 + c -1; LL t = f[x2][y2]- f[x2][y1 -1]- f[x1 -1][y2]+ f[x1 -1][y1 -1];if(t > ret){ ret = t; x = x1, y = y1;}}} cout << x <<" "<< y << endl;return0;}种一棵树最好的时间是10年前，其次是现在。 加油，你已经很棒了！ 共勉！
