十三届蓝桥杯JAVA B组国赛部分题解
I_am_a_String
帮助1人
大学总共参加了三届蓝桥杯，这应该是我最后一次参加蓝桥杯了，再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的，甚至有许多错误，能给大家提供下思路就行。
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 围栏
不会
思路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
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);
}
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhggbfik
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
