第十三届蓝桥杯模拟赛第二期Java组
模拟赛2
题目一
小蓝的IP地址为 192.168.*.21,其中 * 是一个数字,请问这个数字最大可能是多少 ?
package Main;
public class Main {
public static void main(String[] args) {
System.out.println(255);
}
}
题目二
如果一个整数 g 能同时整除整数 A 和 B,则称 g 是 A 和 B 的公约数。例如:43 是 86 和 2021 的公约数。 请问在
1(含) 到 2021(含) 中,有多少个数与 2021 存在大于 1 的公约数。请注意 2021 和 2021 有大于 1 的公约数,因此在计算的时候要算一个。
package Main;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
int n = 2021;
BigInteger a = new BigInteger("2021");
int ans=0;
for (int i = 1; i <= n; i++) {
int d = (a.gcd(new BigInteger(i+""))).intValue();
if(d>1) {
ans++;
System.out.println(d);
}
}
System.out.println(ans);//89
}
}
题目三
2021 是一个非常特殊的数,它可以表示成两个非负整数的平方差,2021 = 45 * 45 - 2 * 2。 2025
也是同样特殊的数,它可以表示成 2025 = 45 * 45 - 0 * 0。请问,在 1 到 2021 中有多少个这样的数?
请注意,有的数有多种表示方法,例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4,在算答案时只算一次。
package Main;
public class Main {
public static void main(String[] args) {
int ans=0;
for(int i=1;i<=2021;i++) {
boolean f =false;
for(int j=0;j<=2021;j++) {
if(f) break;
for(int k=0;k<=2021;k++) {
if(k*k-j*j==i) {
System.out.println(k+"*"+k+"-"+j+"*"+j+"="+i);
ans++;
f=true;break;
}
}
}
}
System.out.println(ans);//1516
}
}
题目四
小蓝要用01串来表达一段文字,这段文字包含 a, b, c, d, e, f 共 6 个字母,每个字母出现的次数依次为:a 出现 10 次,b 出现 20 次,c 出现 3 次,d 出现 4 次,e 出现 18 次,f 出现 50 次。
小蓝准备分别对每个字母使用确定的01串来表示,不同字母的01串长度可以不相同。
在表示文字时,将每个字母对应的01串直接连接起来组成最终的01串。为了能够正常还原出文字,小蓝的编码必须是前缀码,即任何一个字符对应的01串都不能是另一个字符对应的01串的前缀。例如,
以下是一个有效的编码: a: 000 b: 111 c: 01 d: 001 e: 110 f: 100其中 c 的长度为 2,其它字母的编码长度为 3,这种方式表示这段文字需要的总长度为:103+203+32+43+183+503=312。
上面的编码显然不是最优的,将上面的 f 的编码改为 10,仍然满足条件,但是总长度为 262,要短 50。
要想编码后的总长度尽量小,应当让出现次数多的字符对应的编码短,出现次数少的字符对应的编码长。 请问,在最优情况下,编码后的总长度最少是多少
哈夫曼树编码
package Main;
public class Main {
public static void main(String[] args) {
System.out.println(219);
}
}
题目五
下面的矩阵中包含 ABCDEF 六种字符,请问出现最多的字符出现了几次?
FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF
package Main;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
String s = "FFEEFEAAECFFBDBFBCDA" +
"DACDEEDCCFFAFADEFBBA" +
"FDCDDCDBFEFCEDDBFDBE" +
"EFCAAEECEECDCDECADDC" +
"DFAEACECFEADCBFECADF" +
"DFBAAADCFAFFCEADFDDA" +
"EAFAFFDEFECEDEEEDFBD" +
"BFDDFFBCFACECEDCAFAF" +
"EFAFCDBDCCBCCEADADAE" +
"BAFBACACBFCBABFDAFBE" +
"FCFDCFBCEDCEAFBCDBDD" +
"BDEFCAAAACCFFCBBAAEE" +
"CFEFCFDEEDCACDACECFF" +
"BAAAFACDBFFAEFFCCCDB" +
"FADDDBEBCBEEDDECFAFF" +
"CDEAFBCBBCBAEDFDBEBB" +
"BBABBFDECBCEFAABCBCF" +
"FBDBACCFFABEAEBEACBB" +
"DCBCCFADDCACFDEDECCC" +
"BFAFCBFECAACAFBCFBAF";
Integer a[] = new Integer[6];
Arrays.fill(a, 0);
int d=0;
for(int i=0;i<s.length();i++) {
d = s.charAt(i)-'A';
a[d]++;
}
Arrays.sort(a,Collections.reverseOrder());
// for(int i=0;i<a.length;i++) {
// System.out.println(a[i]);
// }
System.out.println(a[0]);//78
}
}
题目六
问题描述
小蓝要到店里买铅笔。 铅笔必须一整盒一整盒买,一整盒 12 支,价格 p 元。 小蓝至少要买 t 支铅笔,请问他最少花多少钱?
输入格式
输入一行包含两个整数 p、t,用一个空格分隔。
输出格式输出一行包含一个整数,表示答案。
样例输入
5 30
样例输出
15
样例说明
小蓝至少要买3盒才能保证买到30支铅笔,总共花费 15 元。
评测用例规模与约定
对于所有评测用例,1 <= p <= 100,1 <= t <= 10000。
package Main;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int p =sc.nextInt();
int t =sc.nextInt();
int ans=0;
if(t%12==0) {
ans=(t/12)*p;
} else {
ans=(t/12+1)*p;
}
System.out.println(ans);
}
}
题目七
问题描述
给定一个三角形的三条边的长度 a, b, c,请问这个三角形是不是一个直角三角形。
输入格式
输入一行包含三个整数 a, b, c,表示三角形三边的长度,相邻整数之间用一个空格分隔。
输出格式
如果是直角三角形,输出“YES”(全大写),否则输出“NO”(全大写)。
样例输入
3 4 5
样例输出
YES
样例输入
4 5 4
样例输出
NO
评测用例规模与约定
对于所有评测用例,1 <= a, b, c <= 1000。
package Main;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if (a + b <= c || a + c <= b || b + c <= a)
System.out.println("NO");
else if (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a)
System.out.println("YES");
else
System.out.println("NO");
}
}
题目八
问题描述
n 个小朋友正在做一个游戏,每个人要分享一个自己的小秘密。 每个小朋友都有一个 1 到 n 的编号,编号不重复。
为了让这个游戏更有趣,老师给每个小朋友发了一张卡片,上面有一个 1 到 n 的数字,每个数字正好出现一次。
每个小朋友都将自己的秘密写在纸上,然后根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。如果老师发给自己的数字正好是自己的编号,这个秘密就留在自己手里。
小朋友们拿到其他人的秘密后会记下这个秘密,老师会再指挥所有小朋友将手中的秘密继续传递,仍然根据老师发的卡
片上的数字将秘密传递给对应编号的小朋友。 这样不断重复 n 次。 现在,每个小朋友都记下了很多个秘密。
老师现在想找一些小朋友,能说出所有秘密,请问老师最少要找几个小朋友?
输入格式
输入的第一行包含一个整数 n。 第二行包含 n 个整数
a[1], a[2], …, a[n],相邻的整数间用空格分隔,分别表示编号 1 到 n 的小朋友收到的数字。
输出格式
输出一行包含一个整数,表示答案。 样例输入 6 2 1 3 5 6 4 样例输出 3 样例说明 最终小朋友 1, 2
互相知道了对方的秘密,小朋友 3 只知道自己的秘密,小朋友 4, 5, 6 互相知道了对方的秘密。 至少要找 3 个小朋友才能说出所有秘密。
评测用例规模与约定 对于 30% 的评测用例,2 <= n <= 30。 对于 60% 的评测用例,2 <= n <= 1000。
对于所有评测用例,2 <= n <= 100000。
题目九
问题描述 一个 1 到 n 的排列被称为半递增序列,是指排列中的奇数位置上的值单调递增,偶数位置上的值也单调递增。 例如:(1, 2, 4,
3, 5, 7, 6, 8, 9) 是一个半递增序列,因为它的奇数位置上的值是 1, 4, 5, 6, 9,单调递增,偶数位置上的值是 2,
3, 7, 8,也是单调递增。 请问,1 到 n 的排列中有多少个半递增序列? 输入格式 输入一行包含一个正整数 n。 输出格式
输出一行包含一个整数,表示答案,答案可能很大,请输出答案除以 1000000007 的余数。 样例输入 5
样例输出 10 样例说明
有以下半递增序列:
(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 3, 2, 4, 5)
(1, 3, 2, 5, 4)
(1, 4, 2, 5, 3)
(2, 1, 3, 4, 5)
(2, 1, 3, 5, 4)
(2, 1, 4, 3, 5)
(3, 1, 4, 2, 5)
评测用例规模与约定 对于 50%
的评测用例,2 <= n <= 20。 对于所有评测用例,2 <= n <= 1000。
题目十
问题描述
小蓝住在 LQ 城,今天他要去小乔家玩。 LQ 城可以看成是一个 n 行 m 列的一个方格图。 小蓝家住在第 1 行第 1
列,小乔家住在第 n 行第 m
列。小蓝可以在方格图内走,他不愿意走到方格图外。城市中有的地方是风景优美的公园,有的地方是熙熙攘攘的街道。小蓝很喜欢公园,不喜欢街道。他把方格图中的每一格都标注了一个属性,或者是喜欢的公园,标为1,或者是不喜欢的街道标为2。小蓝和小乔住的地方都标为了1。小蓝每次只能从一个方格走到同一行或同一列的相邻方格。他想找到一条路径,使得不连续走两次标为
2 的街道,请问在此前提下他最少要经过几次街道? 输入格式输入的第一行包含两个整数 n, m,用一个空格分隔。 接下来 n 行,每行一个长度为 m 第数字串,表示城市的标注。
输出格式
输出一行包含一个整数,表示答案。如果没有满足条件的方案,输出 -1。
样例输入
3 4 1121 1211 2211
样例输出
1
样例输入
3 4 1122 1221 2211
样例输出
-1
样例输入
5 6 112121 122221 221212 211122 111121
样例输出
5
评测用例规模与约定
对于 50% 的评测用例,2 <= n, m <= 20。 对于所有评测用例,2 <= n, m <= 300。