大家好，我是泡泡，距离蓝桥杯还有一天时间，我们一定要把握住最后的时间，跟着我，把全部的题型复习整理一遍，让自己不再迷茫不自信，AK蓝桥！
今日涉及算法：📒博客首页：泡泡的首页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❤️ ：热爱C/C++与算法学习，云计算等，期待一起交流！
🙏作者水平有限，如果发现错误，求告知，多谢！
👻高校算法学习社区：https://bbs.csdn.net/forums/Suanfa
一起加入刷题内卷大军，还可以加入专属内卷群，里面福利多多大佬多多！
暴力枚举，二分，贪心，dfs，bfs，01背包，双指针，哈希表，并查集。
最短路和树，前缀和，质数约数，快速幂大家自己复习一下看看模板就好，这些就是基本常考的了，接下来就开始今天的疯狂复习之路吧！
目录
一丶全排列问题（暴力枚举）
二丶小Ａ的糖果（贪心）
三丶木材加工（二分）
四丶八皇后（dfs）
五丶子串分值（双指针）
六丶缺失的第一个正数（哈希表）
七丶马的遍历（bfs）
八丶合根植物（并查集）
九丶采药（01背包）
十丶数字三角形（线性dp）
一丶全排列问题（暴力枚举）
题目链接：P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
按照字典序输出自然数 1 到 n 所有不重复的排列，即 nn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
解题思路：
这是一个全排列暴力，大家记好，比赛很可能出！
按我自己的方法四步
全排列四步：
第一步：搞定标记数组（用没用过这个数），原数组和输入。
第二步：判断结束条件（如何时打印）。
第三步：考虑循环次数，判断用没用过。
第四步：递归回溯。
#include
using namespace std;
int n,pd[100],a[100];
void dfs(int k)
{
if(k==n)
{
for(int i=1;i<=n;i++)
{
printf("%5d",a[i]);
}
printf("\n");
return ;
}
for(int i=1;i<=n;i++)
{
if(!pd[i])
{
pd[i]=1;
a[k+1]=i;
dfs(k+1);
pd[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
} 题目链接：P3817 小A的糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
小 A 有 n 个糖果盒，第 i 个盒中有 ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 x，至少得吃掉几颗糖。
解题思路：
贪心，源于生活，你现实够贪心，贪心写的就好（不是
贪心是我认为不和其他板子一样，纯粹就是看情况，如果不顺真的贪不出来，这个东西蓝桥也不会
出太难，大家有兴趣可以去练练其他贪心。
#include
using namespace std;
long long sum;
int n,x,a[100010];
int main()
{
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;ix)
{
sum += a[i+1] - x+a[i];
a[i+1] = x-a[i];
}
}
cout< 题目链接：P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。
解题思路：
二分，二分的ｃｈｅｃｋ是最难写的，可以多思考一下。
二分四步法：
第一步：数组，录入。
第二步：定义左端点，右端点，考虑是最大值最小还是最小值最大
如果求大于等于里面的最小值，求第一次出现x的位置，用（ｌ＋ｒ＋１）／２
如果求小于等于里面的最大值，求最后一次出现ｘ的位置，用（ｌ＋ｒ）／２
第三步：根据题目考虑ｃｈｅｃｋ函数如何去写,调整细节
第四步：循环板子
求出最小值最大，用第二个，这里我们让每个木头都除mid加起来，如果大于等于k就让他l=mid，否则r=mid。
（如果是另一个模板第一个就是r=mid）
#include
using namespace std;
int n,k;
int a[100007];
int main()
{
cin>>n>>k;
int r = 0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>r)
{
r = a[i];
}
}
int l=0,mid;
while(l+1=k)
{
l = mid;
}
else
{
r = mid;
}
}
cout< 题目链接：八皇后
题目要求：
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。
请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。
最后一行是解的总个数。
解题思路：
为什么要用八皇后，就是因为他很经典，用到了标记数组，斜线判断等，综合练习了dfs
dfs四步法：
第一步：定义好标记数组，存图数组，如果是迷宫 连通块需要定义方向数组，录入
第二步：判断结束条件是否打印（有的时候不需要打印）
第三步：循环判断四个方向或者八个方向（没有方向的话直接判断有没有用过），有没有用过。
第四步：递归调用，回溯。
#include
using namespace std;
int a[100],b[100],c[100],d[100];
//a数组表示的是行；
//b数组表示的是列；
//c表示的是左下到右上的对角线；
//d表示的是左上到右下的对角线；
int n,sum;
int print()
{
if(sum<=2)
{
for(int k=1;k<=n;k++)
{
cout>n;
queen(1);
cout< 题目链接：子串分值 - 蓝桥云课 (lanqiao.cn)
题目要求：
对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。
例如f(aba)=1，f(abc)=3,f(aaa)=0。
现在给定一个字符串 S0⋯n−1（长度为 n，1≤n≤105），请你计算对于所有 S 的非空子串 Si⋯j(0≤i≤j
解题思路：
双指针，双指针四步法也不难。
第一步：首先考虑这个题目是滑窗还是快慢指针，然后正常的录入。
第二步：如果是滑窗，那就确定滑窗的判断条件，如果是快慢指针，考虑右指针在末尾还是在左指针前面一个一起走。
第三步：选择while或者for循环，进行双指针扫描，如果是滑窗判断完之后记得更新指针位置，快慢指针也是。
第四步：如果是累积的和就每次相加，如果不是就直接输出啦。
这个就是双指针，一个左端点一个右端点在末尾扫描，然后累加
#include
using namespace std;
int main()
{
string s;
cin >> s;
long long len = s.length();
long long sum = 0;
int l,r;
char ss;
for(int i = 0; i < len;i++)
{
ss = s[i];
for(r = i + 1; r < len;r++)
{
if(s[r]==ss)
{
break;
}
}
for(l = i - 1; l >= 0;l--)
{
if(s[l]==ss)
{
break;
}
}
sum += (r - i) * (i - l);
cout< 题目链接：41. 缺失的第一个正数 - 力扣（LeetCode） (leetcode-cn.com)
题目要求：
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
解题思路：
简单哈希的四步法
第一步：定义哈希数组，录入。
第二步：在录入数据的时候每次让哈希数组在该值的下标++或者=1（如果是abcd这种记得-'a')
第三步：判断值，如果在哈希表里出现次数少于条件或者大于条件就输出（根据题目多变）
第四步：输出原数组值或者该哈希值。
记得，循环判断哈希表里的值要根据数据范围开循环范围。
这是一个简单哈希，难得也不会考估计，这个可以套在很多题目里面用，灵活多变
#define MAX 500001
int hash[500001];
int firstMissingPositive(int* nums, int numsSize){
memset(hash,0,sizeof(hash));
for(int i=0;i0&&nums[i] 题目链接：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
解题思路：
标准的bfs，bfs四步法
第一步：存图，标记数组，确定起始点结束点，方向数组。
第二步：有必要可以初始化，定义结构体（或者其他的办法搞队列），定义队列。
第三步：压入起点，时间（可以根据题目单独判断不进队列），标记，定义变量获取队首元素，d出，循环判断方向是否出界是否用过。
第四步：如果到了终点返回或者输出，否则标记并且压入，时间+1.
#include
using namespace std;
const int N = 401;
int dx[] = {2,-2,2,-2,-1,1,-1,1};
int dy[] = {1,1,-1,-1,2,2,-2,-2};
int a[N][N];
int b[N][N];
int n,m,x,y;
struct node{
int x,y;
};
void bfs(int x,int y)
{
queueq;
q.push({x,y});
a[x][y] = 1;
b[x][y] = 0;
while(q.size())
{
node tt = q.front();
q.pop();
for(int i=0;i<8;i++)
{
int xxx = tt.x + dx[i];
int yyy = tt.y + dy[i];
if(xxx<1||xxx>n||yyy<1||yyy>m)
{
continue;
}
if(!a[xxx][yyy])
{
a[xxx][yyy] = 1;
b[xxx][yyy] = b[tt.x][tt.y]+1;
q.push({xxx,yyy});
}
}
}
}
int main()
{
memset(b,-1,sizeof(b));
cin >> n >> m >> x >> y;
bfs(x,y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%-5d",b[i][j]);
}
cout< 题目链接：进去登录点题集 真题 搜索合根植物
题目要求：
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。
每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
解题思路：
并查集四步法
第一步：初始化函数
第二步：查找函数
第三步：判断函数
第四步：根据题目要求循环使用这些函数
我相信各位学过并查集的都懂我的意思，没学过的话来这里学 链接：通俗易懂并查集
#include
using namespace std;
const int N = 1000010;
int m,n,k,pre[N],ans;
bool vis[N];
void init()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n*m;i++)
{
pre[i] = i;
}
}
int find(int x)
{
if(x!=pre[x])
{
return pre[x] = find(pre[x]);
}
return x;
}
void join(int x,int y)
{
int xx = find(x);
int yy = find(y);
if(xx!=yy)
{
pre[yy] = xx;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=0;i
九丶采药（01背包）
题目链接：P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求：
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。
”
如果你是辰辰，你能完成这个任务吗？
解题思路：
01背包啊 背包四步法（这里根据y总的dp分析来的）
第一步：确定集合，集合属性。
第二步：状态计算。
第三步：确定状态转移方程
第四步：初始化并且dp
集合：f[i][j]表示采第i株药,花费时间j可以采到的草药的最大总价值。
集合属性：max
状态计算： 最后一个不同点就是选不选第i个物品 左边所有不选第i个物品的方案 右边是所有选择
左边：从1-i-1选总体积小于j的集合 左边这个集合就是fi-1,j
右边：从1-i选并且总体积小于j i固定所以只看变化的部分包含i的话小于等于j 如果不包含就是小于等于j-vi 最大值式f(i-1,j-vi) 最终结果：f(i-1,j-vi)+wi
状态转移方程：f[j] = max(f[j],f[j-v[i]]+w[i])（01背包优化到一维，i可以不用）
二维状态转移：f[i,j] = max(f(i-1,j),fi-1(j-vi)+wi)
#include
using namespace std;
int f[1001];
int v[1001],w[1001];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=m;i++)
{
for(int j=n;j>=v[i];j--)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout<
十丶数字三角形（线性dp）
题目链接：]数字三角形
题目要求：
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。
每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 7→3→8→7→5 的路径产生了最大
解题思路：
很简单的线性dp，可以从上到下，从下到上。
四步法
第一步：确定集合，集合属性，根据题目要求选择一种方法（自己熟悉的）。
第二步：状态计算。
第三步：确定状态转移方程
第四步：初始化并且dp
状态表示：f[i,j]
集合：所有从起点走到ij的路径
属性：max
状态计算
左上状态:fi-1j]-1+a[i,j]从起点走到这里的最大值 右上状态f[i-1,j]+a[i,j] 同上 两者取max就是答案
方程：f[i,j] = max(f[i-1,j]+a[i,j],f[i-1,j-1]+a[i,j]
倒着做的方程：f[i][j] = max(a[i+1][j],a[i+1][j+1])
读入不用初始化 i=r j=i >=1 最后最顶上的就是答案
#include
using namespace std;
int r;
int f[1010][1010];
int main()
{
cin >> r;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=i;j++)
{
cin>>f[i][j];
}
}
for(int i = r;i>=1;i--)
{
for(int j=i;j>=1;j--)
{
f[i][j] = max(f[i+1][j],f[i+1][j+1])+f[i][j];
}
}
cout<
相信各位通过这些题目能巩固基本功，希望各位蓝桥杯都能考出自己想要的成绩！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）