十三届蓝桥杯JAVA B组国赛题解
- A 重合次数
- B 数数
- C 左移右移
- D 窗口
- E 迷宫
- F 小球称重
- G 背包与魔法
- H 修路
- I 围栏
大学总共参加了三届蓝桥杯，这应该是我最后一次参加蓝桥杯了，再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的，甚至有许多错误，能给大家提供下思路就行。
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(
