目录
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>U
static 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;
}
}
文章来源地址https://www.toymoban.com/news/detail-743189.html
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、人物相关性分析 -
思路:文章来源:https://www.toymoban.com/news/detail-743189.html
到了这里,关于【蓝桥杯 第十届省赛Java B组】真题训练(A - H)H待更新的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!