答题要求
题目说明
说明：要答题，请点击页面上方的“提交此题”按钮，页面将跳转到提交代码的页面，选择好你的编译语言，将你的编写好的代码粘贴到代码框中，再点击“提交答案”即可。
你的答案提交给系统后系统会自动对你的代码进行判分，并跳转到结果的列表里面，你可以直接从列表中看到你提交的代码的状态，一般几秒钟后就可以看到判分的结果。
本题作为第一题，在提示中已经分别给了C++和Java的代码，你可以直接把这个代码拷贝过去作为自己的代码提交。
请特别注意，Java的主类名必须是Main。
题目一
小蓝的IP地址为 192.168.*.21，其中 * 是一个数字，请问这个数字最大可能是多少 ?
答案：255
题解：由32位二进制数组成，IP地址是一个4个字节的二进制数，被分成4段，每段8位二进制数，一共32位二进制数。一个IP地址被分成两部分，即 网络地址 和 主机地址，从数值范围可以判断最大值为255（2^8-1=255），也即常识。
题目二
如果一个整数 g 能同时整除整数 A 和 B，则称 g 是 A 和 B 的公约数。例如：43 是 86 和 2021 的公约数。
请问在 1（含） 到 2021（含） 中，有多少个数与 2021 存在大于 1 的公约数。
请注意 2021 和 2021 有大于 1 的公约数，因此在计算的时候要算一个。
答案：89
题解：gcd 函数为Java中求公约数函数，从1~2021进行逐个查找，当其与自身的公约数大于1，即大于等于2时，说明其存在公约数，进行 count 计数
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int count = 0; for (int i = 1; i <= 2021; i++) { if (gcd(i, 2021) > 1) { count++; } } System.out.println(count); } static int gcd(int a, int b) { return b > 0 ? gcd(b, a % b) : a; } }
题目三
2021 是一个非常特殊的数，它可以表示成两个非负整数的平方差，2021 = 45 * 45 - 2 * 2。
2025 也是同样特殊的数，它可以表示成 2025 = 45 * 45 - 0 * 0。请问，在 1 到 2021 中有多少个这样的数？
请注意，有的数有多种表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算一次。
答案：1516
题解：通过嵌套循环进行迭代循环，达到全匹配的目的，这里涉及到一个数学问题，sum= a*a - b*b 也即 sum = (a+b)(a-b) ，当sum为正数时，b<a，b则为内层循环，由于sum的取值为（1 <= sum <= 2021），要想得到最小正数，则有 a+b=1 或 a-b=1 ，显然 a-b=1成立，则有 b=a-1，代入表达式 sum = (a+a-1)(a-a+1)，则有2021 = 2a-1 ，a=1011，符合条件记为1，计数统计，所以有如下代码：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int count = 0; int[] arr = 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) { arr[sum] = 1; } } } for (int j = 1; j <= 2021; j++) { if (arr[j] == 1) count++; } System.out.println(count); } }
题目四
小蓝要用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。
要想编码后的总长度尽量小，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。
请问，在最优情况下，编码后的总长度最少是多少？
答案：219
题解：哈弗曼编码，建议去认识了解一下，这里留下两个链接
13分钟学会哈夫曼编码
最全哈夫曼树哈夫曼编码讲解，兄弟你值得拥有_记录博主学到的点滴-CSDN博客_哈夫曼编码
题目五
下面的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了几次？
FFEEFEAAECFFBDBFBCDA DACDEEDCCFFAFADEFBBA FDCDDCDBFEFCEDDBFDBE EFCAAEECEECDCDECADDC DFAEACECFEADCBFECADF DFBAAADCFAFFCEADFDDA EAFAFFDEFECEDEEEDFBD BFDDFFBCFACECEDCAFAF EFAFCDBDCCBCCEADADAE BAFBACACBFCBABFDAFBE FCFDCFBCEDCEAFBCDBDD BDEFCAAAACCFFCBBAAEE CFEFCFDEEDCACDACECFF BAAAFACDBFFAEFFCCCDB FADDDBEBCBEEDDECFAFF CDEAFBCBBCBAEDFDBEBB BBABBFDECBCEFAABCBCF FBDBACCFFABEAEBEACBB DCBCCFADDCACFDEDECCC BFAFCBFECAACAFBCFBAF
答案：78
题解：此题使用HashMap效率会很高，刚开始判断不存在字符字符时，将其映射值设为1，后判断其存在时将其值加1，循环所有字符，最后get输出每个key对应的value值
import java.util.HashMap; import java.util.Map; public class Main { static String chars = "FFEEFEAAECFFBDBFBCDA" + "DACDEEDCCFFAFADEFBBA" + "FDCDDCDBFEFCEDDBFDBE" + "EFCAAEECEECDCDECADDC" + "DFAEACECFEADCBFECADF" + "DFBAAADCFAFFCEADFDDA" + "EAFAFFDEFECEDEEEDFBD" + "BFDDFFBCFACECEDCAFAF" + "EFAFCDBDCCBCCEADADAE" + "BAFBACACBFCBABFDAFBE" + "FCFDCFBCEDCEAFBCDBDD" + "BDEFCAAAACCFFCBBAAEE" + "CFEFCFDEEDCACDACECFF" + "BAAAFACDBFFAEFFCCCDB" + "FADDDBEBCBEEDDECFAFF" + "CDEAFBCBBCBAEDFDBEBB" + "BBABBFDECBCEFAABCBCF" + "FBDBACCFFABEAEBEACBB" + "DCBCCFADDCACFDEDECCC" + "BFAFCBFECAACAFBCFBAF"; public static void main(String[] args) { Map<Character, Integer> map = new HashMap<>(); for(int i = 0; i < chars.length(); i++) { char ch = chars.charAt(i); if(ch == 'A' || ch == 'B' || ch == 'C' || ch == 'D' || ch == 'E' || ch == 'F') { if(!map.containsKey(ch)) { map.put(ch, 1); } else { map.put(ch, map.get(ch) + 1); } } } System.out.println(map.get('A')); System.out.println(map.get('B')); System.out.println(map.get('C')); System.out.println(map.get('D')); System.out.println(map.get('E')); System.out.println(map.get('F')); } }
题目六
问题描述
小蓝要到店里买铅笔。
铅笔必须一整盒一整盒买，一整盒 12 支，价格 p 元。
小蓝至少要买 t 支铅笔，请问他最少花多少钱？
输入格式
输入一行包含两个整数 p、t，用一个空格分隔。
输出格式输出一行包含一个整数，表示答案。
样例输入
5 30
样例输出
15
样例说明
小蓝至少要买3盒才能保证买到30支铅笔，总共花费 15 元。
评测用例规模与约定
对于所有评测用例，1 <= p <= 100，1 <= t <= 10000。
题解：不满 12 进 1 直接算
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int p = input.nextInt(); int t = input.nextInt(); int num = t / 12; int rem = t % 12; if (rem > 0) { num = num + 1; } System.out.println(num * p); } }
题目七
问题描述
给定一个三角形的三条边的长度 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 input = new Scanner(System.in); int a = input.nextInt(); int b = input.nextInt(); int c = input.nextInt(); if ((a + b > c || a + c > b || b + c > a) && (a - b < c || a - c < b || b - c < a)) { 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"); } } 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。
题解：并查集算法，就像链表一样，这个链表中的内容都会被链表中的每个人知道，归根结底是查链，这边放两个链接
并查集基础 | 菜鸟教程
并查集快速查找 | 菜鸟教程
import java.util.Scanner; public class Main { static int n; static int[] a; static int num = 0; static int find(int k) { if (a[k] == k) return k; return a[k] = find(a[k]); } public static void main(String[] args) { Scanner input = new Scanner(System.in); n = input.nextInt(); int[] friends = new int[n + 1]; a = new int[n + 1]; for (int i = 1; i <= n; i++) { a[i] = i; friends[i] = input.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) num++; } System.out.println(num); } }
题目九
问题描述
一个 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。
题解：排列组合问题，假设100个数，奇数50个递增，其余50个偶数必定递增且唯一，因为只剩50个数且需要满足递增，齐数与偶数分别传入不同的参数，进行取余计算
import java.util.Scanner; public class Main { public static long group(long a, long b) { long ans = 1; int rem = (int) 1e9 + 7; for (long i = 1, j = a; i <= b; i++, j--) { ans = ans * (j / i) % rem; } return ans; } public static void main(String[] args) { Scanner input = new Scanner(System.in); long n = input.nextLong(); if (n % 2 == 0) { System.out.println(group(n, n / 2)); } else System.out.println(group(n, (n + 1) / 2)); } }
题目十
问题描述
小蓝住在 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。
解答：貌似这道题不是给我做的，没什么思路。借鉴大神的思路 dfs 搜一遍
参考：
算法基础：BFS和DFS的直观解释
BFS和DFS算法 - 简书
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); } }
总结
直观总结：模拟赛前九道还是有一战之力的，大致需要一些计算机常识，Java中的内置函数，for的暴力求解，字符，字符串，整形的转换，一些集合框架，并查集，排列组合问题，等，多复习多总结，相信省赛也不会很难
