【蓝桥杯 第十届省赛Java B组】真题训练（A - H）H待更新

目录

A、组队 - 看图一眼出答案

B、不同子串 - 字符串模拟 + set去重

C、数列求值 - 模拟取余

D、数的分解 - 三重暴力

E、迷宫 - bfs 判断路径

F、特别数的和 - 弱智模拟

G、外卖店优先级 - map 暴力（90%通过率）

H、人物相关性分析 - 

---

A、组队 - 看图一眼出答案

思路：

 没啥说的，注意不能重复选择同一编号！

98+99+98+97+98=98*5=490

B、不同子串 - 字符串模拟 + set去重

import java.util.*;public class test {public static void main(String[] args){Scanner sc=new Scanner(System.in);String s="0100110001010001";int n=s.length();Set<String> st=new HashSet<>();for(int i=0;i<n;i++)for(int j=i+1;j<n+1;j++){String t=s.substring(i,j);st.add(t);}System.out.print(st.size());}
}

 答案是100！

C、数列求值 - 模拟取余

思路：

最后算出来结果非常大，我们只需要每次取最后4位就好

答案是4659 

public class test {static int N=20190324;public static void main(String[] args){Scanner sc=new Scanner(System.in);int[] d=new int[N];d[0]=1;d[1]=1;d[2]=1;for(int i=3;i<N;i++) d[i]=(d[i-1]+d[i-2]+d[i-3])%10000;System.out.print(d[N-1]);}
}

D、数的分解 - 三重暴力

思路：

3个各不相同的正整数，我们只需要i j k三重循环，并保证i<j<k，再字符串判断是否含2或4即可，答案是40785

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int res=0,target=2019;for(int i=1;i<target;i++)for(int j=i+1;j<target;j++)for (int k=j+1;k<target;k++){if(i+j+k==target&&ck(i)&&ck(j)&&ck(k)) res++;}System.out.println(res);}public static boolean ck(int x) {String s=String.valueOf(x);if(s.indexOf('2')!=-1||s.indexOf('4')!=-1) return false;return true;}
}

E、迷宫 - bfs 判断路径

【蓝桥杯集训11】BFS（4 / 4）_Roye_ack的博客-CSDN博客 

思路：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDRDRRURRUURRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

迷宫问题用bfs解决，要求满足字典序最小的最短路，我们可以设置能走时优先选择顺序【D>L>R>U】，也就是在dx dy方向数组上按顺序定义

建立坐标系，x轴正方向向下，y轴正方向向右

首先倒着bfs预处理出d[i][j]——(i，j)到终点的最短距离

然后正向遍历能走的点，如果d[x][y]==d[nx][ny]+1，说明走这点是在最短路上，记录方向

因为我们优先是【D>L>R>U】这么走的，所以输出的最短路肯定是字典序最小的

为什么d[x][y]==d[nx][ny]+1说明是在最短路上？

因为bfs跑完，处理出的 值非-1的d[i][j] 都是能通往终点的最短路。d[i][j]代表(i，j)到终点的最短距离，如果d[x][y]==d[nx][ny]+1，说明(x，y)是最短路上(nx，ny)的前一个点，相当于说(x，y)在最短路上

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n=30,m=50;static int[][] d=new int[n+1][m+1]; //d[i][j]是(i,j)到终点的最短距离static String[] g=new String[n+1]; //存储原始迷宫static int[] dx={1,0,0,-1};  // 方向优先D>L>R>Ustatic int[] dy={0,-1,1,0};static char[] dir={'D','L','R','U'};public static void main(String[] args) {Scanner sc=new Scanner(System.in);for(int i=0;i<n;i++) g[i]=sc.next();bfs();String res="";int x=0,y=0;while(x!=n-1||y!=m-1){for(int i=0;i<4;i++){int nx=dx[i]+x;int ny=dy[i]+y;if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx].charAt(ny)=='0'){if(d[x][y]==d[nx][ny]+1){res+=dir[i]; //如果这条路能走且在最短路上 记录方向x=nx;y=ny;}}}}System.out.println("最短路径为："+d[0][0]);System.out.println(res);}public static void bfs() {for(int i=0;i<n;i++) Arrays.fill(d[i],-1);d[n-1][m-1]=0;Queue<PII> q=new LinkedList<>();q.offer(new PII(n-1,m-1));while(!q.isEmpty()){PII t=q.poll();for(int i=0;i<4;i++){int nx=t.x+dx[i];int ny=t.y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==-1&&g[nx].charAt(ny)=='0'){d[nx][ny]=d[t.x][t.y]+1;q.offer(new PII(nx,ny));}}}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

F、特别数的和 - 弱智模拟

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int res=0;int n=sc.nextInt();for(int i=1;i<=n;i++)if(ck(i)) res+=i;System.out.println(res);}public static boolean ck(int x){String s=String.valueOf(x);if(s.indexOf('0')!=-1||s.indexOf('1')!=-1||s.indexOf('2')!=-1||s.indexOf('9')!=-1)return true;return false;}}

 

G、外卖店优先级 - map 暴力（90%通过率）

思路：

（碎碎念可以不看）这题折磨死我了，看一眼数据范围就知道双for会t，然后就想着找规律，但是找规律不行，第一次找的规律是：预处理记录每个id的时间点，2*时间点的个数=总共赚的优先级，然后再减去没有的时间点个数（因为如果没有订单优先级-1），最后判断大于3就说明在队列里

但这样写忽略了一种情况：id为2的时间点【5，6，6】如果按照上面规律，1，2，3，4属于没有出现的时间点，减去他们就是-4，然而实际上1，2，3，4时因为优先级为0，并不需要减去。

然后我就放弃思考了，写了个暴力……暴力写的完也是debug一年（因为循环时把t写成n了，为了这改了很久……）（碎碎念结束）

• 建一个map，【id：时间点列表】
• 然后遍历每一个id的从1—t的时间点
  • 如果出现，则【优先级+=2×时间点出现次数】，这里运用排序+下标方法计算时间点出现次数
  • 如果没有出现，则优先级-1，如果已经是0了就不变
• 最后判断一下状态，如果优先级>5则true，如果优先级<=3则false
• 如果状态为true，则res++

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int res=0;int n=sc.nextInt(),m= sc.nextInt(), t= sc.nextInt();Map<Integer,List<Integer>> mp=new HashMap<>();int[] shopnum=new int[n+1];boolean[] st=new boolean[n+1];int[] h=new int[n+1];while(m-->0){int ts=sc.nextInt();int id=sc.nextInt();List<Integer> list=new ArrayList<>();if(shopnum[id]!=0) list=mp.get(id);  //注意只有map中有list时才能直接赋值，否则需要新建list.add(ts);mp.put(id,list);shopnum[id]++;}int id=1;for(List<Integer> x:mp.values()){Collections.sort(x); //排序是为了后面计算一个时间点出现多次的情况for(int i=1;i<=t;i++){if(x.contains(i))  h[id]+=2*(x.lastIndexOf(i)-x.indexOf(i)+1); //eg：【1，1，1，3】 1的lastindex-indexof+1就是1的个数else if(!x.contains(i)) h[id]=Math.max(0,h[id]-1);if(h[id]>5) st[id]=true;else if(h[id]<=3) st[id]=false;}if (st[id]) res++;id++;}System.out.println(res);}
}

 

H、人物相关性分析 - 

思路：