第十三届蓝桥杯第2期模拟赛JAVA组"/>
第十三届蓝桥杯第2期模拟赛JAVA组
目录
1.IP地址
2.公约数
3.特殊的数
4.编码长度(哈夫曼编码)
5.矩阵字符
6.买铅笔
7.直角三角形
8.分享秘密
9.半递增序列
解法一
解法二
10.方格图
1.IP地址
小蓝的IP地址为 192.168.*.21,其中 * 是一个数字,请问这个数字最大可能是多少 ?
【答案】255
计算机网络知识,IP地址为8位二进制为一个位,每一个位都是2^8-1=255。
2.公约数
如果一个整数 g 能同时整除整数 A 和 B,则称 g 是 A 和 B 的公约数。例如:43 是 86 和 2021 的公约数。
请问在 1(含) 到 2021(含) 中,有多少个数与 2021 存在大于 1 的公约数。请注意 2021 和 2021 有大于 1 的公约数,因此在计算的时候要算一个。【解法】用欧几里得算法,判断如果和2021公约数 大于1 就加1,最后直接输出总数。
【答案】89
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); int count = 0;for(int i = 1;i <= 2021;i++) {if(gcd(i,2021) > 1)count++;}System.out.println(count);}private static int gcd(int a, int b) {return b>0 ? gcd(b,a % b) :a;}
}
3.特殊的数
2021 是一个非常特殊的数,它可以表示成两个非负整数的平方差,2021 = 45 * 45 - 2 * 2。
2025 也是同样特殊的数,它可以表示成 2025 = 45 * 45 - 0 * 0。
请问,在 1 到 2021 中有多少个这样的数?
请注意,有的数有多种表示方法,例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4,在算答案时只算一次。【答案】1516
【解法】数学的平方差公式a^2-b^2=(a-b)(a+b),b < a ,b是内层循环,(a-b)(a+b)当a确定时,b=a-1的时候,是最小正数,也就是(a-a+1)(a+a-1)=2a-1。我们让2a-1去等于2021,得到a=1011,b=a-1=1010的最小正数是2021。
public class Main {public static void main(String[] args) {int count = 0;int[] a = new int[2022];for(int i = 1;i <= 1011;i++) {for(int j = 0;j < i;j++) {int sum = i*i -j *j;if(sum <= 2021)a[sum] = 1;}}for(int i = 1;i <= 2021;i++) {if(a[i] == 1)count++;}System.out.println(count);}
}
4.编码长度(哈夫曼编码)
小蓝要用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。
要想编码后的总长度尽量小,应当让出现次数多的字符对应的编码短,出现次数少的字符对应的编码长。
请问,在最优情况下,编码后的总长度最少是多少?
哈夫曼树,WPL=所有叶子结点 * 带权路径。
构造过程:先排序,构造树时,把小的数放左边,大的数放右边。
c(3):1 1 0 0 0
d(4):1 1 0 0 1
a(10):1 1 0 1
e(18):1 1 1
b(20):1 0
f(50):0
WPL=3*5 + 4*5 + 10*4 + 18*3 + 20*2 + 50*1 =219
【答案】219
5.矩阵字符
下面的矩阵中包含 ABCDEF 六种字符,请问出现最多的字符出现了几次?
FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF
利用word文档解决,把这个矩阵复制到word文档中,分别查找"ABCDEF"出现的次数。
分别得出A:66,B:58,C:76,D:63,E:59,F:78。
【答案】78
6.买铅笔
问题描述
小蓝要到店里买铅笔。
铅笔必须一整盒一整盒买,一整盒 12 支,价格 p 元。
小蓝至少要买 t 支铅笔,请问他最少花多少钱?
输入格式
输入一行包含两个整数 p、t,用一个空格分隔。
输出格式
输出一行包含一个整数,表示答案。
样例输入
5 30
样例输出
15
样例说明
小蓝至少要买3盒才能保证买到30支铅笔,总共花费 15 元。
评测用例规模与约定
对于所有评测用例,1 <= p <= 100,1 <= t <= 10000。
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 r = t % 12;int num = t / 12;if(r > 0)num++;int count = p * num;System.out.println(count);}
}
7.直角三角形
问题描述
给定一个三角形的三条边的长度 a, b, c,请问这个三角形是不是一个直角三角形。
输入格式
输入一行包含三个整数 a, b, c,表示三角形三边的长度,相邻整数之间用一个空格分隔。
输出格式
如果是直角三角形,输出“YES”(全大写),否则输出“NO”(全大写)。
样例输入
3 4 5
样例输出
YES
样例输入
4 5 4
样例输出
NO
评测用例规模与约定
对于所有评测用例,1 <= a, b, c <= 1000。
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) {if(a*a + b*b == c*c || a*a + c*c == b*b || c*c + b*b == a*a)System.out.println("YES");elseSystem.out.println("NO");}else {System.out.println("NO");}}
}
8.分享秘密
问题描述
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。
并查集的题,因为每个人的手上都有自己或别人的秘密,就像链表一样,肯定会有一条条链,因为链中循环n次,那链中的人一定会知道那条链中每个人的秘密,所以最后查一下有多少条链就知道问至少问多少个小盆友,就可以知道所有小盆友的秘密了。
import java.util.*;
public class Main{static Scanner sc = new Scanner(System.in);static int n;static int [] a;static int cnt = 0;static int find(int k) {if(a[k]==k) return k;return a[k] = find(a[k]);}public static void main(String[] args) {n = sc.nextInt();int [] friends = new int[n+1];a = new int[n+1];for(int i=1;i<=n;i++)a[i] = i;for(int i=1;i<=n;i++)friends[i] = sc.nextInt();for(int i=1;i<=n;i++) {if(find(i) != find(friends[i]))a[find(i)] = find(friends[i]);}for(int i=1;i<=n;i++) {if(a[i] == i)cnt ++;}System.out.println(cnt);}
}
9.半递增序列
问题描述
一个 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。
解法一
//求组合数,只要选出奇数位置的数,奇数位置和偶数位置的数一定就固定下来
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();if(n%2 == 0)System.out.println(C(n,n/2));elseSystem.out.println(C(n,(n+1)/2));}private static long C(long a, long b) {long ans = 1;for(long i=1,j=a;i<=b;i++,j--) {ans = ans*(j/i)%1000000007;}return ans;}
}
解法二
//杨辉三角形
import java.util.*;
public class Main{static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int n = sc.nextInt();int k = n / 2;int [] a = new int[1001];a[0] = 1;for(int i=1;i<=n;i++) {a[0] = 1;a[i] = 1;for(int j=i-1;j>0;j--) {a[j] = (a[j] + a[j-1])%1000000007;}}System.out.println(a[k]);}
}
10.方格图
问题描述
小蓝住在 LQ 城,今天他要去小乔家玩。
LQ 城可以看成是一个 n 行 m 列的一个方格图。
小蓝家住在第 1 行第 1 列,小乔家住在第 n 行第 m 列。
小蓝可以在方格图内走,他不愿意走到方格图外。
城市中有的地方是风景优美的公园,有的地方是熙熙攘攘的街道。小蓝很喜欢公园,不喜欢街道。他把方格图中的每一格都标注了一个属性,或者是喜欢的公园,标为1,或者是不喜欢的街道标为2。小蓝和小乔住的地方都标为了1。
小蓝每次只能从一个方格走到同一行或同一列的相邻方格。他想找到一条路径,使得不连续走两次标为 2 的街道,请问在此前提下他最少要经过几次街道?
输入格式
输入的第一行包含两个整数 n, m,用一个空格分隔。
接下来 n 行,每行一个长度为 m 第数字串,表示城市的标注。
输出格式
输出一行包含一个整数,表示答案。如果没有满足条件的方案,输出 -1。
样例输入
3 4
1121
1211
2211
样例输出
2
样例输入
3 4
1122
1221
2211
样例输出
-1
样例输入
5 6
112121
122221
221212
211122
111121
样例输出
5
评测用例规模与约定
对于 50% 的评测用例,2 <= n, m <= 20。
对于所有评测用例,2 <= n, m <= 300。
import java.util.Scanner;public class Main {private static final int INF = 0x3f3f3f3f;private static int n, m, res = INF;private static int[][] map = new int[305][305];private static boolean[][] st = new boolean[305][305];private final static int[][] next = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private static void dfs(int x, int y, int count) { //count记录已经走过的街道的数量if(x == n - 1 && y == m - 1) {// 到终点了res = Math.min(res, count);return;}st[x][y] = true;for(int i = 0; i < 4; i++) {int tx = x + next[i][0];int ty = y + next[i][1];if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;if(st[tx][ty]) continue;if(map[tx][ty] == 2 && map[x][y] == 2) continue;dfs(tx, ty, map[x][y] == 2 ? count + 1 : count);}st[x][y] = false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 0; i < n; i++) {String line = sc.next();for(int j = 0; j < m; j++) {int ch = line.charAt(j);int cur = ch - '0';map[i][j] = cur;}}dfs(0, 0, 0);if(res == INF) res = -1;System.out.println(res);}
}
更多推荐
第十三届蓝桥杯第2期模拟赛JAVA组
发布评论