【蓝桥真题7】贴吧车队作弊？应对线上考和双填趋势，我们该如何备考？
蓝桥杯倒计时一周，贴吧集合作弊风气严重，选择题压缩到只剩两题？我们到底该如何应考？
⭐️引言⭐️
大家好，我是执梗。还有一个星期蓝桥杯就要开赛了，但是现在却风起云涌，由于疫情的原因，绝大多数地区已经改为线上考试。理所当然，在这种趋势下，出现作弊行为肯定是无法避免的。甚至在贴吧都沦陷成如下都是如下场景：
当然蓝桥杯官方组委也注意到这种情况，在线上考的趋势下，作弊肯定是无法避免的，官方也加大了打击力度和举报渠道！我们要做的就是在这种趋势下做最好自己，保持自己的本心。
甚至根据蓝桥杯某地区负责人而言：本届蓝桥杯填空题将变为两道题，这就意味着就会有八道编程大题！难度将提升不止一个档次，当然这也更多是为了防止作弊，因为编程大题雷同很容易被检测出来。虽然不知真假，在这种情况下，我也从蓝桥31日冲刺训练营中总结出一套蓝桥考前压轴卷，帮助大家巩固自身，即使有人作弊也要用实力碾压他们！
下面写的题解精选的都是来自蓝桥训练营的往届真题，考点贴合近三年蓝桥改革趋势，大家有任何疑问都可以在评论区交流.
⭐️精彩回放⭐️
目录
———🌸——🌸——
🎃 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问题：
- 状态表示：F[i][j]：通过j步走到第i格的最大权值
- 转移方程分析：分析最后一步是通过走了跳了第几格到达第i格。如果最后一步是通过跳跃1格到达第i格，那么转移方程应该是
，w[i]是第i格的权值。如果最后一步是通过跳跃2格，则转移方程是：
。最多是通过跳跃p格到达第i格，我们只需要在这么多方案中取一个最大值即可。
- 初始化：由于权值是带有负数的，所以我们首先需要将所有方案初始化成负无穷，然后初始化第一步走一格一直到第一步走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
现在加入还可以加入专属内部交流群，为了保证群质量，后续将会封群，志同道合的兄弟们快来！社区可以扫二维码进入，也可以后台私信我回复算法集结拉你入群。
感觉文章有用的兄弟们还请给个三连呀！！！感谢！！
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
141
0- 0
已为社区贡献8条内容
所有评论(0)