蓝桥杯最后一天复习?各大算法四步法教你轻松秒杀各种题型

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

今日涉及算法:


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


一丶全排列问题(暴力枚举)


题目链接: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;
}


二、小A的糖果(贪心)


题目链接: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。


解题思路:


二分,二分的check是最难写的,可以多思考一下。


二分四步法:


第一步:数组,录入。


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


如果求大于等于里面的最小值,求第一次出现x的位置,用(l+r+1)/2 


如果求小于等于里面的最大值,求最后一次出现x的位置,用(l+r)/2 


第三步:根据题目考虑check函数如何去写,调整细节


第四步:循环板子


求出最小值最大,用第二个,这里我们让每个木头都除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 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。


42.png


上面的布局可以用序列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


解题思路:


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


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


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


第三步:选择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
    {
        if(nums[i]>0&&nums[i]
        {
            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;
}


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


目录
相关文章
|
5月前
|
算法 Java Serverless
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
50 1
|
4月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
42 3
|
2天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
4月前
质数类判断方法(蓝桥杯,循环分支题型)
质数类判断方法(蓝桥杯,循环分支题型)
|
5月前
|
存储 算法 Java
蓝桥杯递归算法
蓝桥杯中的递归算法涉及将问题分解为子问题,通过函数自身调用来求解。优点是简洁易懂,但效率低且可能引发栈溢出。示例包括:数组求和、数的阶乘、斐波那契数列及最大公约数计算,以及字符串翻转。代码展示了各种递归场景的Java实现,如`f3`计算数组和,`f`求阶乘,`f1`计算斐波那契数,`f2`找最大公约数,和`f1`字符串反转。
33 1
|
4月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
4月前
|
算法
基础算法-去重字符串,辗转相除法,非递归前序遍历二叉树题型分析
基础算法-去重字符串,辗转相除法,非递归前序遍历二叉树题型分析
|
5月前
|
算法 安全 定位技术
【刷题】备战蓝桥杯 — dfs 算法
dfs算法在数据较小的情况下可以使用。 一定一定要确定好终止条件,避免栈溢出。 相应做好回溯,保证每次的遍历都是不一样的选择,避免少结果。 针对题目进行对应细节处理,有能力的话可以进行剪枝优化!!!
45 0
|
5月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
94 0
|
5月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
75 0