大学总共参加了三届蓝桥杯,这应该是我最后一次参加蓝桥杯了,再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的,甚至有许多错误,能给大家提供下思路就行。
A 重合次数
思路:模拟下时钟就行,签到题
答案:502-8=494(由于匀速运动,59分59秒到0分0秒实际算一次)
public class Main {
public static void main(String[] args) {
int h = 6;
int m = 13;
int s = 22;
long result = 0;
while(true) {
s++;
if(s==60) {
s=0;
m++;
}
if(m==60) {
m=0;
h++;
}
if(s==m)result++;
if(h==14&&m==36&&s==20)break;
}
System.out.println(result);
}
}
B 数数
思路:最大的质因子不大于23333333/(2^11)=11393,筛出11393前的质数,把范围的数挨个检测就是,10的7次方*10的三次方的数量级,10的九次方数量级大概是1s,这题直接暴力大概100s就能跑出来(实际上我比赛时大概也就跑了一两分钟,读完C题题目准备写时发现已经跑出来了),所以直接暴力就行。
答案:25606
public class Main {
public static void main(String[] args) {
//欧拉筛
int N = 11393;
int m = 2333333;
int[] p = new int[N+1];
int[] f = new int[N+1];
int cnt=0;
for(int i=2;i<=N;i++) {
if(f[i]==0)p[cnt++]=i;
for(int j=0;j<cnt&&p[j]*i<=N;j++) {
f[p[j]*i]=1;
if(i%p[j]==0)break;
}
}
//挨个检测
int result = 0;
for(int i=2333333;i<=23333333;i++) {
int tmp = 0;
int now = i;
while(tmp<12) {
int flag=0;//判断是否能整除
for(int j=0;j<cnt;j++) {
if(now%p[j]==0) {
tmp++;
now/=p[j];
flag=1;
break;
}
}
if(flag==0)break;
}
if(now==1&&tmp==12)result++;//能整除且刚好12个质因子
}
System.out.println(result);
}
}
C 左移右移
思路:乍一看第一反应是双头队列,然而发现移动的x并非下标而是具体的数,每次移动都去找那个数肯定是不高效,不过200000*200000貌似直接这样暴力也能ac,这里提供一种更快的思路,给每个数一个cnt,维护zuo和you两个变量,每次左移将- - zuo赋给cnt,右移++you赋给cnt,然后根据cnt排序挨个输出就行,nlogn的复杂度,这样应该是最优解了。再就是10w的输入输出,直接scanner和sysout估计会卡输入输出。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String line = in.readLine();
String[] ml = line.split(" ");
int N = Integer.parseInt(ml[0]);
int M = Integer.parseInt(ml[1]);
num[] allnum = new num[N+1];
allnum[0]=new num(0,9999999);
for(int i=1;i<=N;i++) {
allnum[i]=new num(i, i);
}
long zuo = 1;
long you = N;
for(int i=0;i<M;i++) {
line = in.readLine();
ml = line.split(" ");
char zy = ml[0].charAt(0);
int x = Integer.parseInt(ml[1]);
if(zy=='L') allnum[x].cnt=--zuo;
else allnum[x].cnt=++you;
}
Arrays.sort(allnum,new Comparator<num>() {
@Override
public int compare(num arg0, num arg1) {
if(arg0.cnt>arg1.cnt) return 1;
else return -1;
}
});
out.print(allnum[0].id);
for(int i=1;i<N;i++)out.print(" "+allnum[i].id);
out.flush();
}
}
class num {
long id;
long cnt;
public num(long id,long cnt) {
this.id=id;
this.cnt=cnt;
}
}
D 窗口
思路:直接模拟,借用上题思路,用id记录优先级,每次操作将其id赋值当前最大,最后根据id排序,从下往上依次涂显示器。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
public class D {
static char[][] map;
static int N;
static int M;
static int nowID=1;
static ck[] allCK;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line = in.readLine();
String[] ml = line.split(" ");
N = Integer.parseInt(ml[0]);
M = Integer.parseInt(ml[1]);
map = new char[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
map[i][j]='.';
}
}
allCK = new ck[100001];
for(int i=0;i<=100000;i++)allCK[i]= new ck(i, 0, 0, 0, 0, -1);
line = in.readLine();
int K = Integer.parseInt(line);
for(int i=0;i<K;i++) {
line = in.readLine();
ml = line.split(" ");
if(ml[0].equals("new")) newCK(Integer.parseInt(ml[1]),Integer.parseInt(ml[2]),Integer.parseInt(ml[3]),Integer.parseInt(ml[4]),Integer.parseInt(ml[5]));
else if(ml[0].equals("move")) moveCK(Integer.parseInt(ml[1]),Integer.parseInt(ml[2]),Integer.parseInt(ml[3]));
else if(ml[0].equals("resize")) resizeCK(Integer.parseInt(ml[1]),Integer.parseInt(ml[2]),Integer.parseInt(ml[3]));
else if(ml[0].equals("close")) closeCK(Integer.parseInt(ml[1]));
else activeCK(Integer.parseInt(ml[1]));
}
Arrays.sort(allCK,new Comparator<ck>() {
@Override
public int compare(ck o1, ck o2) {
if(o1.id>o2.id) return 1;
return -1;
}
});
int now = 0;
while(allCK[now].id<0)now++;
for(;now<=100000;now++) {
ck tmp = allCK[now];
for(int i=tmp.top;i<=tmp.top+tmp.height-1;i++) {
for(int j=tmp.left;j<=tmp.left+tmp.width-1;j++) {
if(i>=0&&i<N&&j>=0&&j<M)map[i][j]=' ';
}
}
if(tmp.top>=0&&tmp.top<N)
for(int i=tmp.left;i<=tmp.left+tmp.width-1;i++) {
if(i>=0&&i<M)map[tmp.top][i]='-';
}
if((tmp.top+tmp.height-1)>=0&&(tmp.top+tmp.height-1)<N)
for(int i=tmp.left;i<=tmp.left+tmp.width-1;i++) {
if(i>=0&&i<M)map[tmp.top+tmp.height-1][i]='-';
}
if(tmp.left>=0&&tmp.left<M)
for(int i=tmp.top;i<=tmp.top+tmp.height-1;i++) {
if(i>=0&&i<N)map[i][tmp.left]='|';
}
if((tmp.left+tmp.width-1)>=0&&(tmp.left+tmp.width-1)<M)
for(int i=tmp.top;i<=tmp.top+tmp.height-1;i++) {
if(i>=0&&i<N)map[i][(tmp.left+tmp.width-1)]='|';
}
if(tmp.left>=0&&tmp.left<M&&tmp.top>=0&&tmp.top<N) map[tmp.top][tmp.left]='+';
if((tmp.left+tmp.width-1)>=0&&(tmp.left+tmp.width-1)<M&&tmp.top>=0&&tmp.top<N) map[tmp.top][(tmp.left+tmp.width-1)]='+';
if(tmp.left>=0&&tmp.left<M&&(tmp.top+tmp.height-1)>=0&&(tmp.top+tmp.height-1)<N) map[(tmp.top+tmp.height-1)][tmp.left]='+';
if((tmp.left+tmp.width-1)>=0&&(tmp.left+tmp.width-1)<M&&(tmp.top+tmp.height-1)>=0&&(tmp.top+tmp.height-1)<N) map[(tmp.top+tmp.height-1)][(tmp.left+tmp.width-1)]='+';
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
private static void activeCK(int tpid) {
allCK[tpid].id=nowID++;
}
private static void closeCK(int tpid) {
allCK[tpid].id=-1;
}
private static void resizeCK(int tpid, int theight, int twidth) {
allCK[tpid].id=nowID++;
allCK[tpid].height=theight;
allCK[tpid].width=twidth;
}
private static void moveCK(int tpid, int tvertical, int thorizontal) {
allCK[tpid].id=nowID++;
allCK[tpid].top=allCK[tpid].top+tvertical;
allCK[tpid].left=allCK[tpid].left+thorizontal;
}
private static void newCK(int tpid, int ttop, int tlefg, int theight, int twidth) {
allCK[tpid].id=nowID++;
allCK[tpid].top=ttop;
allCK[tpid].left=tlefg;
allCK[tpid].height=theight;
allCK[tpid].width=twidth;
}
}
class ck{
int pid;
int top;
int left;
int height;
int width;
int id;
public ck(int pid,int top,int left,int height,int width,int id) {
this.pid=pid;
this.top=top;
this.left=left;
this.height=height;
this.width=width;
this.id=id;
}
}
E 迷宫
思路:很基础的搜索题,就是搜索时加了个传送门的分支,当时只看到了20*20,直接dfs了,写题解才发现ac要2000x2000,dfs肯定爆栈了,得改写成bfs,这里仅贴dfs代码,bfs写法为从终点往各个点走,亦可以打表或者dp。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class E {
static int[][] rem;
static int N;
static int[][] map;
static csm[][] allcsm;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int min=99999999;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
int M = in.nextInt();
rem = new int[N+1][N+1];
map = new int[N+1][N+1];
allcsm = new csm[N+1][N+1];
for(int i=0;i<M;i++) {
int x1=in.nextInt();
int y1=in.nextInt();
int x2=in.nextInt();
int y2=in.nextInt();
map[x1][y1]=1;
map[x2][y2]=1;
allcsm[x1][y1]=new csm(x2, y2);
allcsm[x2][y2]=new csm(x1, y1);
}
double sum = 0;
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
min = 99999999;
rem[i][j]=1;
dfs(i,j,0);
rem[i][j]=0;
sum+=min;
}
}
System.out.printf("%.02f\n",sum/(N*N));
}
private static void dfs(int x, int y, int n) {
if(x==N&&y==N) {
if(n<min)min=n;
return;
}
if(map[x][y]==1) {
int nx=allcsm[x][y].x;
int ny=allcsm[x][y].y;
if(rem[nx][ny]==0) {
rem[nx][ny]=1;
dfs(nx, ny, n+1);
rem[nx][ny]=0;
}
}
for(int d=0;d<4;d++) {
int nx = x+dir[d][0];
int ny = y+dir[d][1];
if(nx>=1&&nx<=N&&ny>=1&&ny<=N&&rem[nx][ny]==0) {
rem[nx][ny]=1;
dfs(nx, ny, n+1);
rem[nx][ny]=0;
}
}
}
}
class csm{
int x;
int y;
public csm (int x,int y) {
this.x=x;
this.y=y;
}
}
F 小球称重
思路:所有球标为0记为未测试。
大于和小于号:小的一边标记不为1(已排除嫌疑)的标为-1记为嫌疑人,
大的一边标为1记为排除嫌疑。
等于号:两边都记为1排除嫌疑
最后统计-1和0的数量,若标记为-1的球的数量不为0就是答案,否则标记为0的球的数量是答案。
这里数据量大时用数组记录会爆内存,当另寻它法。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] rem = new int[N+1];
for(int i=0;i<M;i++) {
int K = in.nextInt();
ArrayList<Integer> l = new ArrayList<>();
ArrayList<Integer> r = new ArrayList<>();
for(int j=0;j<K;j++) {
int x = in.nextInt();
l.add(x);
}
for(int j=0;j<K;j++) {
int x = in.nextInt();
r.add(x);
}
String tmp = in.next();
if(tmp.equals(">")) {
for(int j=0;j<K;j++) {
rem[l.get(j)]=1;
}
for(int j=0;j<K;j++) {
if(rem[r.get(j)]==0){
rem[r.get(j)]=-1;
}
}
}else if(tmp.equals("<")) {
for(int j=0;j<K;j++) {
rem[r.get(j)]=1;
}
for(int j=0;j<K;j++) {
if(rem[l.get(j)]==0){
rem[l.get(j)]=-1;
}
}
}else {
for(int j=0;j<K;j++) {
rem[l.get(j)]=1;
}
for(int j=0;j<K;j++) {
rem[r.get(j)]=1;
}
}
}
int cnt = 0;
int r = 0;
for(int i=1;i<N;i++) {
if(rem[i]==-1) cnt++;
if(rem[i]==0) r++;
}
if(cnt!=0)System.out.println(cnt);
else System.out.println(r);
}
}
G 背包与魔法
思路:很基础的01背包,就是转移方法多了个要不要用魔法的分支。
这里题意有歧义,如果理解成只能用从头到尾一次魔法,这里当用2维dp,k为0时表示没用魔法,k为1时表示用了。dp[j][0]取dp[j][0]和dp[j-w[i]][0]+v[i]中较大者,分别表示不用魔法装i和不装i,dp[j][1]取dp[j][1],dp[j-w[i]][1]和dp[j-w[i]-wk][0]中最大着,分别表示不装i已用魔法,装i已用魔法,未用魔法当前物品i用魔法并装。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class G {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int N = (int)in.nval;
in.nextToken();
int M = (int)in.nval;
in.nextToken();
int wK = (int)in.nval;
int[] W = new int[N+1];
int[] V = new int[N+1];
int[] dp = new int[M+2];
for(int i=1;i<=N;i++) {
in.nextToken();
int wi = (int)in.nval;
in.nextToken();
int vi = (int)in.nval;
W[i]=wi;
V[i]=vi;
}
for(int i=1;i<=N;i++) {
for(int j=W[i];j<=M;j++) {
int max=0;
max=Math.max(dp[j],dp[j-W[i]]+V[i]);
if(j>=W[i]+wK)max=Math.max(max, dp[j-wK-W[i]]+V[i]*2);
dp[j]=max;
}
}
System.out.println(dp[M]);
}
}
H 修路
思路:和20年国赛画廊没啥区别
https://blog.csdn.net/I_am_a_String/article/details/117568160
I 围栏
不会文章来源:https://www.toymoban.com/news/detail-478732.html
思路1:暴力枚举,用kmp或者其它匹配方法判断是否包含子串。
思路2: 直接找符合范围长度的数,把左右边界字符串长度-4,就是你要找到数字串长度范围,求个全排列把2022往中间插入,判断是否在范围内就行,2022后面加0的情况单独分析。
eg: 左边界100000 右边界20000000
左:6-4=2,右:8-4=4
全排列10到9999
如12344把2022往里面插就是2022 12344,1 2022 2344,12 2022 2344 …
判断是否在100000和20000000之间就行。
最后单独考虑202200,2022000,20200000文章来源地址https://www.toymoban.com/news/detail-478732.html
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Scanner;
public class F {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] rem = new int[N+1];
for(int i=0;i<M;i++) {
int K = in.nextInt();
ArrayList<Integer> l = new ArrayList<>();
ArrayList<Integer> r = new ArrayList<>();
for(int j=0;j<K;j++) {
int x = in.nextInt();
l.add(x);
}
for(int j=0;j<K;j++) {
int x = in.nextInt();
r.add(x);
}
String tmp = in.next();
if(tmp.equals(">")) {
for(int j=0;j<K;j++) {
rem[l.get(j)]=1;
}
for(int j=0;j<K;j++) {
if(rem[r.get(j)]==0){
rem[r.get(j)]=-1;
}
}
}else if(tmp.equals("<")) {
for(int j=0;j<K;j++) {
rem[r.get(j)]=1;
}
for(int j=0;j<K;j++) {
if(rem[l.get(j)]==0){
rem[l.get(j)]=-1;
}
}
}else {
for(int j=0;j<K;j++) {
rem[l.get(j)]=1;
}
for(int j=0;j<K;j++) {
rem[r.get(j)]=1;
}
}
}
int cnt = 0;
int r = 0;
for(int i=1;i<N;i++) {
if(rem[i]==-1) cnt++;
if(rem[i]==0) r++;
}
if(cnt!=0)System.out.println(cnt);
else System.out.println(r);
}
}
到了这里,关于十三届蓝桥杯JAVA B组国赛部分题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!