⭐️引言⭐️

              大家好，我是执梗。还有一个星期蓝桥杯就要开赛了，但是现在却风起云涌，由于疫情的原因，绝大多数地区已经改为线上考试。理所当然，在这种趋势下，出现作弊行为肯定是无法避免的。甚至在贴吧都沦陷成如下都是如下场景F1a;

当然蓝桥杯官方组委也注意到这种情况，在线上考的趋势下，作弊肯定是无法避免的，官方也加大了打击力度和举报渠道！我们要做的就是在这种趋势下做最好自己，保持自己的本心。

甚至根据蓝桥杯某地区负责人而言：本届蓝桥杯填空题将变为两道题，这就意味着就会有八道编程大题！难度将提升不止一个档次，当然这也更多是为了防止作弊，因为编程大题雷同很容易被检测出来。虽然不知真假，在这种情况下，我也从蓝桥31日冲刺训练营中总结出一套蓝桥考前压轴卷，帮助大家巩固自身，即使有人作弊也要用实力碾压他们！

下面写的题解精选的都是来自蓝桥训练营的往届真题，考点贴合近三年蓝桥改革趋势，大家有任何疑问都可以在评论区交流.

⭐️精彩回放⭐️

蓝桥真题6	【蓝桥真题6】三十块的蓝桥省赛模拟真题，做的大一都直呼上当（文末PDF原题）_执 梗的博客-CSDN博客
蓝桥真题5	【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）_执 梗的博客-CSDN博客
蓝桥真题4	【蓝桥真题4】练练填空就想进国赛？拿下大题才能让你真正有底气（蓝桥31日冲刺打卡）_执 梗的博客-CSDN博客
蓝桥真题3	【蓝桥真题3】蓝桥改革变难，想进国赛这些能力你可缺一不可_执 梗的博客-CSDN博客_蓝桥杯进国赛难不难
蓝桥真题2	【蓝桥真题2】蓝桥杯不会全排列，那就只能写10个for循环了【内附近8年真题资源】_执 梗的博客-CSDN博客
蓝桥真题1	【蓝桥真题1】这道用了7个for循环的蓝桥真题，让舍友哭着跑出考场【内附原题资源】_执 梗的博客-CSDN博客

目录

🎃 1.打包（二分答案）

👻2. 跳跃的小明（动态规划）

🎆3.大胖子走迷宫（BFS）

🎏4.合根植物（并查集）

 🎓5.分考场（回溯）

🎒 6.迷宫与陷阱（BFS）

🎎7.蓝肽子序列（线性DP）

———🌸——🌸——​

🎍8.日志统计（滑动窗口）

🍋9.高校算法学习社区（兄弟们速来）

---

🎃 1.打包（二分答案）

Lazy有N个礼物需要打成M个包裹，邮寄给M个人，这些礼物虽然很便宜，但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费，他还希望让包裹的最大重量最小。

题目链接：打包 

        题目的意思有一点容易理解错（蓝桥题目特色，生怕你读懂哈哈哈），刚开始我还以为选一个长度为M的子数组保证和最小。但其实它的意思是将N个礼物分成若M个包裹，每个包裹可以有若干个礼物，然后让我们求这些包裹中最大重量最小的值。

       像这种求某某某最大的最小值，或者最小的最大值大家一定要想到二分。很多人肯定心想，切二分嘛，套个模板不就好啦。确实是套个模板不就好了，但是对于二分的题目是分为两种，一种是求值二分，而另外一种就是二分答案。直接对答案去进行二分查找，所以这题我们直接对包括的最大重量的最小值这个属性进行二分，所以问题来了，如何确定边界和check函数逻辑？

•        对于左边界left，它肯定是我们所有礼物中最重礼物的重量，因为礼物必须全部打包，最重的包裹在最轻的情况下就是只单独选最重的礼物
•        对于右边界right，我们直接考虑极限情况，全部礼物的重量的总值就好，既然是二分，只有答案能在区间里，那就肯定能找到答案
•        至于最核心的check函数，无非则是判断选择当前重量，能否分成至多M个包裹，每次选择连续且重量之和不超过mid的的礼物打包为一个包裹，最后的包裹数量小于等于M说明符合，我们让r=;mid，否则l=mid+1.

       代码转换：

import java.util.Scanner;

public class Main {
	static int N=100010;
	static int[] arr=new int[N];
	static int n,m;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		int max=0;
		int sum=0;
		for(int i=1;i<=n;++i) {
			arr[i]=sc.nextInt();
			sum+=arr[i];
			max=Math.max(max, arr[i]);
		}
		int l=max;
		int r=sum;
		while(l<r) {
			int mid=(l+r)>>1;
			if(check(mid)) r=mid;
			else l=mid+1;
		}
		System.out.PRintln(l);
	}
	static boolean check(int target) {
		int count=0;
		int tmp=0;
		for(int i=1;i<=n;++i) {
			count+=arr[i];
			if(count>target){
				count=0;
				tmp++;
				i--;
			}else if(i==n){
				tmp++;
			}
		}
		return tmp<=m;
	}
}

👻2. 跳跃的小明（动态规划）

　　有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。 　　小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？

题目链接：跳跃的小明

       比较明显的DP问题：

1.         状态表示：F[i][j]：通过j步走到第i格的最大权值
2.         转移方程分析：分析最后一步是通过走了跳了第几格到达第i格。如果最后一步是通过跳跃1格到达第i格，那么转移方程应该是，w[i]是第i格的权值。如果最后一步是通过跳跃2格，则转移方程是：@H_304_180@。最多是通过跳跃p格到达第i格，我们只需要在这么多方案中取一个最大值即可。
3.         初始化：由于权值是带有负数的，所以我们首先需要将所有方案初始化成负无穷，然后初始化第一步走一格一直到第一步走p格的情况。最后答案是f[n+1][t]，因为对于给定的数组其实左右两头有两个权值为0的位置，那才是我们的起点和终点。

        代码转换：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N=1010;
    static int n,p,t;
    //通过j步走到第i个格子的最大权值
    static int[][] f=new int[N][N];
    static int[] arr=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        p=sc.nextInt();
        t=sc.nextInt();
        for(int i=1;i<=n;++i) arr[i]=sc.nextInt();
        for(int[] a:f) {
            Arrays.fill(a,-0x3f3f3f);
        }
        //初始化：通过第一步能走到的位置
        for(int i=1;i<=p&&i<=n+1;++i) f[i][1]=arr[i];
        //走到第i格
        for(int i=1;i<=n+1;++i){
            //通过j步
            for(int j=2;j<=t;++j){
                //上一次走了k步到达第i格
                for(int k=1;k<=p&amp;&k<=i;++k) {
                    f[i][j]=Math.max(f[i-k][j-1]+arr[i],f[i][j]);
                }
            }
        }
        System.out.println(f[n+1][t]);
    }
}

🎆3.大胖子走迷宫（BFS）

题目链接：大胖子走迷宫 

        比较经典的BFS问题，稍微属于一点变种的BFS，首先大家要认真理解题目的意思，摒弃掉我们平常做BFS问题的思维，首先思考以下几个问题：

       1.每次行动的决策，是否只能是上下左右移动？

       2.对于能否移动的判断，我们应该如何判定？

       疑问解答：

        1.由于在某些地点，可能因为小明太胖而走不过去，而这条路径却是唯一的路径，所以小明得在原地等待变小后再通过，或者其实小明走其他路还不如在原地变小再过去，所以在上下左右移动的决策中，还应该加上原地等待

        2.由于小明太胖，所以他占用的区域可能是5X5或者3X3，所以我们在移动到（x，y）坐标时，不仅需要判断x,y和合法坐标，还得判断以x,y为中心周围的3x3或者5x5都得是合法的。这样我们可以用一个变量count记录成小明的膨胀因子，每次判断是否合法时，都需要在原坐标上加上或者减去膨胀因子，最开始是5x5，所以膨胀因子为2，当变成3x3时，膨胀因子为1，最后变回原形以后膨胀因子则变为0。

        代码转换：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N=310;
    static char[][] arr=new char[N][N];
    static boolean[][] visIT=new boolean[N][N];
    static int[] dx= {1,-1,0,0};
    static int[] dy= {0,0,-1,1};
    static int tmp=2;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        for(int i=0;i<n;++i) {
            arr[i]=sc.next().toCharArray();
        }
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{2,2});
        visit[2][2]=true;
        int count=0;
        while(!queue.iSEMpty()) {
            int size=queue.size();
            while(size-->0) {
                int[] curr=queue.poll();
                int x=curr[0];
                int y=curr[1];
                if(x==n-3&&y==n-3) {
                    System.out.println(count);
                    return;
                }
                for(int i=0;i<4;++i) {
                    int a=x+dx[i];
                    int b=y+dy[i];
                    if(a-tmp>=0&&a+tmp<n&&b-tmp>=0&&b+tmp<n&&!visit[a][b]&&check(a,b)) {
                        queue.offer(new int[]{a,b});
                        visit[a][b]=true;
                    }
                }
                //需要再把自己当前位置加入队列，表示原地等待
                queue.offer(new int[]{x,y});
            }
            count++;
            if(count==k) tmp=1;
            if(count==2*k) tmp=0;
        }
    }
    //判断当前位置小明是否能够移动到此
    static boolean check(int a,int b){
        for (int i =a-tmp; i<=a+tmp; i++) {
            for (int j =b-tmp; j<=b+tmp ; j++) {
                if (arr[i][j]=='*') return false;
            }
        }
        return true;
    }
}

🎏4.合根植物（并查集）

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

题目链接：合根植物

        这道题考察的就是基础的并查集题目。并查集是一种很实用并且比较简单容易理解的数据结构。大家不要觉得很难，而且并查集的题目套模板即可，记住那几个方法的实现就可以，而且这道题目属于往年的国赛真题，并查集在省赛出现的概率也是非常大的。

        如果大家不知道该如何入手并查集，可以去看一下黑马的数据结构教学视频： 黑马数据结构

        代码转换：

import java.util.Scanner;
public class Main {
	static int N=1010;
	static int[][] arr=new int[N][N];
	//并查集
	static int[] p=new int[N*N];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=m;++j) {
				arr[i][j]=i*m+j;
			}
		}
		int count=m*n;
		for(int i=1;i<=n*m;++i) p[i]=i;
		int k=sc.nextInt();
		while(k-->0) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int root1=find(a);
			int root2=find(b);
			if(root1!=root2){
				p[root1]=root2;
				count--;
			}
		}
		System.out.println(count);
	}
	
	static int find(int x) {
		if(x!=p[x]) p[x]=find(p[x]);
		return p[x];
	}
}

 🎓5.分考场（回溯）

n个人参加某项特殊考试。 为了公平，要求任何两个认识的人不能分在同一个考场。 求最少需要分几个考场才能满足条件。

题目链接：分考场

           首先这道题目的数据范围很小，n最大只能取到100，所以如此我们可以考虑使用回溯去进行爆搜。因为确实这道题看上去没有很好的解决办法，但是这道题目使用回溯也非常有讲究，因为它需要双回溯，也就是回溯两次。

          为什么会出现这种情况呢？因为爆搜要考虑所有的情况。这个我们先不提

           这道题我我先是用的贪心的想法：当选择一名学生时，考虑第一个考场，是否能把他放进去，不能就看第二个，如果全都不行就重新开一个考场给他，直到所有学生放进去。但一名学生他可能是可以出现在多个考场的，不同的考场都会影响我们的答案，所以这样只拿了40分。

           之所以要讲贪心的错误做法，正是因为回溯弥补了贪心的缺陷，当我们对一个学生对已有考场进行判断时，先考虑A考场，可以放入我们就先放入，往后判断完以后再回溯不放入，接着再考虑B考场，也是类似A一样的考虑。最后再考虑如果这个学生无法安排进去则需要新开一个考场，无论有没有考场放入他，因为我们要考虑所有的情况。这样考虑每次安排完所有学生后看使用了多少个考场，然后取一个最小值。

          代码转换：

import java.util.*;

public class Main {
    static int n,m,N=110;
    static List<Integer>[] list=new ArrayList[N];
    static int ans=100;
    static boolean[][] map=new boolean[N][N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            map[a][b]=map[b][a]=true;
        }
        for (int i = 1; i<=n ; i++) {
            list[i]=new ArrayList<>();
        }
        dfs(1,0);
        System.out.println(ans);
    }
    //st是学生，cl是教室数量
    static void dfs(int st,int cl){
        //这步是剪枝操作，很重要，否则可能导致超时
        //当我们判断已用教室已经大于等于找到的最小情况
        //那我们没有必须继续搜索，因为它一定不是答案
        if (cl>=ans) return;
        //到这一步说明找到了一种更小的方案
        if (st>n){
            ans=cl;
            return;
        }
        for (int i = 1;i<=cl ; i++) {
            int j=0;
            for (;j<list[i].size();++j){
                if(map[st][list[i].get(j)]) break;
            }
            //说明和这个教室全部学生都不相等
            if (j==list[i].size()){
                //放入学生
                list[i].add(st);                
                dfs(st+1,cl);
                //回溯
                list[i].remove(list[i].size()-1);
            }
        }
        //走到这步还没找到教室说明需要新教室
        list[cl+1].add(st);
        dfs(st+1,cl+1);
        //回溯
        list[cl+1].remove(list[cl+1].size()-1);
    }
}

🎒 6.迷宫与陷阱（BFS）

题目链接：迷宫与陷阱           

        这道题目也是考察BFS广度优先搜索，有点类似前面的大胖子走迷宫，对于我而言会比大胖子更难一些，因为会容易有失分情况。

        首先这道题同样要像大胖子一样思考，每一次有多少种选择？有时候从陷阱过去可能会更快，所以会有吃了无敌点再倒回去从陷阱过去的情况，所以这道题移动时如果我们具有无敌步数，是可以走回头路的。

        但提交以后会发现是这样：

          为什么在大数据会超时甚至爆内存呢？

           这就是这道题比大胖子那题更难的原因，因为我们前面的做法是当你的无敌步数不为0的时候，就可以往任何你走过的地方走。如果无敌点太多，就会导致大量被走过的位置疯狂重新入队，不仅会导致超时还会爆内存。

          所以我们应该如何解决呢？我们可以这样想，如果此时我们走到一个位置(x,y)。此时无敌步数剩m。如果我们后面从其他无敌点再次走回这个位置，无敌步数仍然是m，那我们还有必要走下去吗？答案肯定是没有必要的！因为BFS搜索是不会搜索重复的，我们以往BFS判断已走过的标准只是坐标而已，而这题我们需要对剩余无敌步数也进行记忆。当在同一个位置，但剩余的无敌步数不同时，这是属于两种情况，否则视为一种需要进行去重！因此我们的标记数组要从普通的二维变成三维，多一维用来记录剩余无敌步数。

        代码转换：

import java.util.LinkedList;
import java.util.Queue;
import java.io.*;
public class Main {
    static int N = 1010;
    static char[][] arr = new char[N][N];
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    //因为无敌步数做多只有10，所以第三维开11就行了
    //不然太大肯定爆掉了，三维太大了
    static int[][][] visit = new int[N][N][11];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String[] s1=br.readLine().split(" ");
        int n = Integer.parseint(s1[0]);
        int k = Integer.parseInt(s1[1]);
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine().toCharArray();
        }
        Queue<PII> queue = new LinkedList<>();
        queue.offer(new PII(0, 0, 0));
        visit[0][0][0]=1;
        int tmp = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                PII curr = queue.poll();
                int x = curr.x;
                int y = curr.y;
                int z = curr.z;
                //找到答案
                if (x == n - 1 && y == n - 1) {
                    System.out.println(tmp);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int a = x + dx[i];
                    int b = y + dy[i];
                    int c = z;
                    //越界
                    if ((!(a >= 0 && a < n && b >= 0 && b < n))||arr[a][b]=='#'||visit[a][b][c]==1) continue;
                    if (arr[a][b]=='X'){
                       if (c>0){                        
                           queue.offer(new PII(a,b,c-1));
                           visit[a][b][c-1]=1;
                       }
                    }else if (arr[a][b]=='%'){
                        queue.offer(new PII(a,b,k));
                        visit[a][b][c]=1;
                        arr[a][b]='.';
                    }else{
                        visit[a][b][c]=1;
                        queue.offer(new PII(a,b,c>0?c-1:0));
                    }
                }
            }
            tmp++;
        }
        System.out.println(-1);
    }
}
//x，y记录的是坐标
//z记录的是剩余的无敌步数
class PII{
    int x,y,z;
    public PII(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

🎎7.蓝肽子序列（线性DP）

题目链接：蓝肽子序列 

        题目表达的确实很让人头疼，但如果做过最长公共子序列模型的题目，大家应该还是能看出来的。本质上就是求最长公共子序列，但恶心你一点就是需要先根据大写字母去进行切割。像LCS(最长公共子序列)和LIS（最长递增子序列）还是比较基础的线性DP题目，大家一定要去学习掌握一下，这几年蓝桥杯考的也是挺多的。

       代码转换:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N=1010;
    static int[][] f=new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        List<String> A = new ArrayList<>();
        List<String> B = new ArrayList<>();
        int n = s1.length();
        int m = s2.length();
        int i = 0;
        while (i <n) {
            int j = i + 1;
            while (j != n && s1.charAt(j) > 'Z') j++;
            A.add(s1.substring(i, j));
            i = j;
        }
        i=0;
        while (i<m){
            int j=i+1;
            while (j != m && s2.charAt(j) > 'Z') j++;
            B.add(s2.substring(i, j));
            i = j;
        }
        //以上均为切割步骤
        for (int j = 1; j <=A.size(); j++) {
            for (int k = 1; k <=B.size(); k++) {
                f[j][k]=Math.max(f[j-1][k],f[j][k-1]);
                if (A.get(j-1).equals(B.get(k-1))) f[j][k]=Math.max(f[j][k],f[j-1][k-1]+1);
            }
        }
        System.out.println(f[A.size()][B.size()]);
    }
}

🎍8.日志统计（滑动窗口）

 题目链接：日志统计

        这道题我觉得还是有一定难度的，至少在考场上如果第一次见，还是需要一定细心的能力的。因为做法确实很多，但有些细节处理起来很复杂。这里我才用的是滑动窗口的思想。

       为什么会想到用滑动窗口来做呢？（理解此做法需要一定滑动窗口的思想）

       因为一篇日志在长度为D的时间段内点赞达到k则为热帖。那我的想法则是维护一个长度为D的时间窗口，统计这个窗口内所有文章的被点赞数。用一个Map<Integer,List>来存储时间和这个时间里被点赞的日志，每次窗口移动一格时，先减去左边界的被点赞的文章，再加上被点赞的文章，如果判断此时它的点赞数达到k了，则将它标记为成为过热帖的日志。     

       代码转换：

import java.util.*;

public class Main {
    static int N=100010;
    //记录文章区间出现次数
    static int[] cut=new int[N];
    //这个数组用来标记文章是否成为过热帖
    static boolean[] isOK=new boolean[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int d=sc.nextInt();
        int k=sc.nextInt();
        Map<Integer, List<Integer>> map=new HashMap<>();
        for(int i=0;i<n;++i) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            //全部存入到map中
            if(map.containsKey(a)) map.get(a).add(b);
            else {
                ArrayList<Integer> list=new ArrayList<>();
                list.add(b);
                map.put(a, list);
            }
        }
        //计算初始窗口内的值
        int l=0;
        int r=d;
        for(int i=l;i<r;++i) {
            if(map.containsKey(i)) {
                for(int index:map.get(i)) {
                    cut[index]++;
                    //热度够了
                    if(cut[index]>=k) isOK[index]=true;
                }
            }
        }
        //滑动窗口枚举时间
        while (r<N) {
            if(map.containsKey(l)) {
                for(int index:map.get(l)) cut[index]--;
            }
            l++;
            r++;
            if(map.containsKey(r)) {
                for(int index:map.get(r)) {
                    cut[index]++;
                    if(cut[index]>=k) isOK[index]=true;
                }
            }
        }
        for(int i=0;i<isOK.length;++i) {
            if(isOK[i]) System.out.println(i);
        }
    }
}

---

这次的题目都比前面的更难一些，但是如果大家能克服肯定会有所进步。还是那句话，无论他人如何，大家做好自己，坚持本心！

🍋9.高校算法学习社区（兄弟们速来）

        不知道大家学习算法的时候，会不会感觉到一个人总是难以坚持？每天刷一天的题目总是做不了几道题，陷入低勤奋的误区。为此执梗集合自己认识的一群热爱的算法的小伙伴创办了——高校算法学习社区。

        创办目的：

        1.为了集合高校学习算法的爱好者，形成一个良好的刷题氛围，每天能交流题目，一起打各种周赛 ，交流博客写作，一起成为万粉博主 

        2.开始每日刷题活动，打卡可获积分，后续还有各种算法活动，排行榜奖励丰厚：

     

         想了解更多高校算法社玩法->：https://docs.QQ.COM/doc/DVnZJbkFPc1BNU2x2

         社区直达地址：https://BBS.csdn.net/forums/Suanfa?category=0

         现在加入还可以加入专属内部交流群，为了保证群质量，后续将会封群，志同道合的兄弟们快来！社区可以扫二维码进入，也可以后台私信我回复算法集结拉你入群。

        感觉文章有用的兄弟们还请给个三连呀！！！感谢！！