⭐️引言⭐️

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

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

甚至根据蓝桥杯某地区负责人而言:本届蓝桥杯填空题将变为两道题,这就意味着就会有八道编程大题!难度将提升不止一个档次,当然这也更多是为了防止作弊,因为编程大题雷同很容易被检测出来。虽然不知真假,在这种情况下,我也从蓝桥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格,那么转移方程应该是F[i][j]=F[i-1][j-1]+w[i],w[i]是第i格的权值。如果最后一步是通过跳跃2格,则转移方程是:F[i][j]=F[i-2][j-1]+w[i]。最多是通过跳跃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&&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

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

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

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐