大家好，我是泡泡，距离蓝桥杯还有一天时间，我们一定要把握住最后的时间，跟着我，把全部的题型复习整理一遍，让自己不再迷茫不自信，AK蓝桥！

📒博客首页：泡泡的首页

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

❤️ ：热爱C/C++与算法学习，云计算等，期待一起交流！

🙏作者水平有限，如果发现错误，求告知，多谢！

👻高校算法学习社区：https://bbs.csdn.net/forums/Suanfa        

一起加入刷题内卷大军，还可以加入专属内卷群，里面福利多多大佬多多！

今日涉及算法：

暴力枚举，二分，贪心，dfs，bfs，01背包，双指针，哈希表，并查集。最短路和树，前缀和，质数约数，快速幂大家自己复习一下看看模板就好，这些就是基本常考的了，接下来就开始今天的疯狂复习之路吧！

目录

一丶全排列问题（暴力枚举）

 二丶小Ａ的糖果（贪心）

三丶木材加工（二分）

四丶八皇后（dfs）

五丶子串分值（双指针）

六丶缺失的第一个正数（哈希表）

七丶马的遍历（bfs）

八丶合根植物（并查集）

九丶采药（01背包）

十丶数字三角形（线性dp）

一丶全排列问题（暴力枚举）

题目链接：P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目要求：

按照字典序输出自然数 1 到 n 所有不重复的排列，即 nn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

解题思路：

这是一个全排列暴力，大家记好，比赛很可能出！

按我自己的方法四步

全排列四步：

第一步：搞定标记数组（用没用过这个数），原数组和输入。

第二步：判断结束条件（如何时打印）。

第三步：考虑循环次数，判断用没用过。

第四步：递归回溯。

#include<bits/stdc++.h>
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<bits/stdc++.h>
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;i<n;i++)
{
    if(a[i]+a[i+1]>x)
{
        sum += a[i+1] - x+a[i];
        a[i+1] = x-a[i];
    }
}
cout<<sum;
return 0;   
}

三丶木材加工（二分）

题目链接：P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目要求：

木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。

木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。

解题思路：

二分，二分的ｃｈｅｃｋ是最难写的，可以多思考一下。

二分四步法：

第一步：数组，录入。

第二步：定义左端点，右端点，考虑是最大值最小还是最小值最大

如果求大于等于里面的最小值，求第一次出现x的位置，用（ｌ＋ｒ＋１）／２　

如果求小于等于里面的最大值，求最后一次出现ｘ的位置，用（ｌ＋ｒ）／２　

第三步：根据题目考虑ｃｈｅｃｋ函数如何去写,调整细节

第四步：循环板子

求出最小值最大，用第二个，这里我们让每个木头都除mid加起来，如果大于等于k就让他l=mid，否则r=mid。（如果是另一个模板第一个就是r=mid）

#include<bits/stdc++.h>
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<r)
{
mid=(l+r)/2;
int sum=0;
for(int i=1;i<=n;i++)
{
sum += a[i]/mid;
}
if(sum>=k)
{
l = mid;
}
else
{
r = mid;
}
}
cout<<l<<endl;
return 0;
}

四丶八皇后（dfs）

题目链接：八皇后

题目要求：

一个如下的 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<bits/stdc++.h>
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<<a[k]<<" ";
}
        cout<<endl;
    }
    sum++;
}
void queen(int i)
{
    if(i>n)
    {
        print();
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))
            {
                a[i]=j;
                b[j]=1;
                c[i+j]=1;
                d[i-j+n]=1;
                queen(i+1);
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
            }
        }
    }
}
int main()
{    
    cin>>n;
    queen(1);
    cout<<sum;
    return 0;
}

五丶子串分值（双指针）

题目链接：子串分值 - 蓝桥云课 (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<n)，f(Si⋯j​) 的和是多少。

解题思路：

双指针，双指针四步法也不难。

第一步：首先考虑这个题目是滑窗还是快慢指针，然后正常的录入。

第二步：如果是滑窗，那就确定滑窗的判断条件，如果是快慢指针，考虑右指针在末尾还是在左指针前面一个一起走。

第三步：选择while或者for循环，进行双指针扫描，如果是滑窗判断完之后记得更新指针位置，快慢指针也是。

第四步：如果是累积的和就每次相加，如果不是就直接输出啦。

这个就是双指针，一个左端点一个右端点在末尾扫描，然后累加

#include<bits/stdc++.h>
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<<l<<"";
}
cout << sum;
return 0;
}

六丶缺失的第一个正数（哈希表）

题目链接：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;i<numsSize;i++)
    {
        if(nums[i]>0&&nums[i]<MAX)
        {
            hash[nums[i]]++;
        }
    }
    for(int i=1;i<=numsSize;i++)
    {
        if(hash[i]==0)
        {
            return i;
        }
    }
    return numsSize+1;
}

七丶马的遍历（bfs）

题目链接：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目要求：

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

解题思路：

标准的bfs，bfs四步法

第一步：存图，标记数组，确定起始点结束点，方向数组。

第二步：有必要可以初始化，定义结构体（或者其他的办法搞队列），定义队列。

第三步：压入起点，时间（可以根据题目单独判断不进队列），标记，定义变量获取队首元素，弹出，循环判断方向是否出界是否用过。

第四步：如果到了终点返回或者输出，否则标记并且压入，时间+1.

#include<bits/stdc++.h>
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)
{
queue<node>q;
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<<endl;
}
return 0;
}

八丶合根植物（并查集）

题目链接：进去登录点题集 真题 搜索合根植物

题目要求：

w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

解题思路：

并查集四步法

第一步：初始化函数

第二步：查找函数

第三步：判断函数

第四步：根据题目要求循环使用这些函数

我相信各位学过并查集的都懂我的意思，没学过的话来这里学 链接：通俗易懂并查集

#include<bits/stdc++.h>
 
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<k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
join(x,y);
}
for(int i=1;i<=n*m;i++)
{
vis[find(i)] = 1;
}
for(int i=1;i<=n*m;i++)
{
ans += vis[i];
}
cout<<ans<<endl;
return 0;
}

九丶采药（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<bits/stdc++.h>
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<<f[n];
return 0;
}

十丶数字三角形（线性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<bits/stdc++.h>
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<<f[1][1];
    return 0;
}

相信各位通过这些题目能巩固基本功，希望各位蓝桥杯都能考出自己想要的成绩！