碎碎念:
在攻克第十题的时候教学楼停电了, 本来想保存了代码到寝室慢慢做, 刚准备保存, 啪一下没电了, 第十题已经写了的代码还没来得及保存就没了.
第一题
题目
问题描述
小蓝的IP地址为 192.168.*.21，其中 * 是一个数字，请问这个数字最大可能是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
分析
这道题大概是考常识, 题目也没给子网掩码. 如果对网络地址不了解可能会吃亏.
答案应该是255. 反正不可能是20.
第二题
题目
问题描述
如果一个整数 g 能同时整除整数 A 和 B，则称 g 是 A 和 B 的公约数。例如：43 是 86 和 2021 的公约数。
请问在 1（含） 到 2021（含） 中，有多少个数与 2021 存在大于 1 的公约数。请注意 2021 和 2021 有大于 1 的公约数，因此在计算的时候要算一个。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
分析
整数g同时整除A和B, 这里设B为2021, 我们需要求A在[1,2021]中满足条件的个数.
首先, g需要是2021的约数, 再找到g的倍数且小于等于2021.
接着去掉重复值, 就完事了.
答案应该是:89
package cf.vbnm.q01;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class Main {
public static void main(String[] args) {
/*先算出2021的约数*/
List<Integer> dividers = new ArrayList<>();
for (int i = 2; i < 2022; i++) {
if (2021 % i == 0) {
dividers.add(i);
}
}
/*计算2021的约数的倍数,同时去除重复值*/
/*使用HashSet去重*/
HashSet<Integer> result = new HashSet<>();
for (int divider : dividers) {
for (int i = divider; i < 2022; i += divider) {
result.add(i);
}
}
/*输出HashSet的元素个数*/
System.out.println(result.size()); //89
}
}
第三题
题目
问题描述
2021 是一个非常特殊的数，它可以表示成两个非负整数的平方差，2021 = 45 * 45 - 2 * 2。
2025 也是同样特殊的数，它可以表示成 2025 = 45 * 45 - 0 * 0。
请问，在 1 到 2021 中有多少个这样的数？
请注意，有的数有多种表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算一次。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
分析
穷举所有平方差组合, 然后去重就行.
要点在于确定穷举的平方差的上限. 这道题的上限是1011.因为:sqr( 1011 )- sqr( 1010 ) = 2021
package cf.vbnm.q03;
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
int max = 0;
for (int i = 2; i * i - (i - 1) * (i - 1) <= 2021; i++) {
max = i;
}
HashSet<Integer> result = new HashSet<>();
for (int i = 1; i <= max; i++) {
for (int j = i - 1; j >= 0; j--) {
final int e = i * i - j * j;
if (e > 2021)
break;
result.add(e);
}
}
System.out.println(result.size()); //1516
}
}
我认为答案是1516, 题目中说1-2021之间, 不算0.
好像我填了1517, 忘了去0,记不清了.
第四题
题目
问题描述
小蓝要用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，这种方式表示这段文字需要的总长度为：10*3+20*3+3*2+4*3+18*3+50*3=312。
上面的编码显然不是最优的，将上面的 f 的编码改为 10，仍然满足条件，但是总长度为 262，要短 50。
要想编码后的总长度尽量小，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。
请问，在最优情况下，编码后的总长度最少是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
分析
题目中很明显的给出了解题思路:要想编码后的总长度尽量小，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。
所以我们首先确定一种编码方案:
这道题考的是哈夫曼树和哈夫曼编码,是一种用于无损数据压缩的熵编码算法.
哈夫曼编码-百度百科 霍夫曼编码-维基百科 如果对哈夫曼编码不清楚会很吃亏, 因为求到的不一定是最短的.
package cf.vbnm.q04;
public class Main {
public static void main(String[] args) {
//这里我手工排序了, 数据量大的话可以用 Arrays.sort();
int[] appears = {3, 4, 10, 18, 20, 50};
int[] code = {5, 5, 4, 3, 2, 1};
int result = 0;
for (int i = 0; i < appears.length; i++) {
result += appears[i] * code[i];
}
System.out.println(result); //219
}
}
所以答案是219
第五题
题目
问题描述
下面的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了几次？
FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
分析
这里使用用HashMap进行去重和计数.
不知道为什么, 这次比赛尤其喜欢用HashXXX.
package cf.vbnm.q04;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
//直接复制题干就是这样了
String patten = " FFEEFEAAECFFBDBFBCDA\n" +
" DACDEEDCCFFAFADEFBBA\n" +
" FDCDDCDBFEFCEDDBFDBE\n" +
" EFCAAEECEECDCDECADDC\n" +
" DFAEACECFEADCBFECADF\n" +
" DFBAAADCFAFFCEADFDDA\n" +
" EAFAFFDEFECEDEEEDFBD\n" +
" BFDDFFBCFACECEDCAFAF\n" +
" EFAFCDBDCCBCCEADADAE\n" +
" BAFBACACBFCBABFDAFBE\n" +
" FCFDCFBCEDCEAFBCDBDD\n" +
" BDEFCAAAACCFFCBBAAEE\n" +
" CFEFCFDEEDCACDACECFF\n" +
" BAAAFACDBFFAEFFCCCDB\n" +
" FADDDBEBCBEEDDECFAFF\n" +
" CDEAFBCBBCBAEDFDBEBB\n" +
" BBABBFDECBCEFAABCBCF\n" +
" FBDBACCFFABEAEBEACBB\n" +
" DCBCCFADDCACFDEDECCC\n" +
" BFAFCBFECAACAFBCFBAF";
//去掉无用字符,这里的空格不是\u0020的空格,所以不能直接敲出来,要复制粘贴
final String formatted = patten.replace(" ", "").replace("\n", "");
HashMap<Character, Integer> resultMap = new HashMap<>();
for (int i = 0; i < formatted.length(); i++) {
//这段代码其实就做了下面注释代码的事情
resultMap.merge(formatted.charAt(i), 1, Integer::sum);
// final Integer integer = resultMap.get(formatted.charAt(i));
// if (integer == null) {
// resultMap.put(formatted.charAt(i), 1);
// } else
// resultMap.put(formatted.charAt(i), integer + 1);
}
System.out.println(resultMap);
//{A=66, B=58, C=76, D=63, E=59, F=78}
}
}
所以答案是78
其实这个复制到Word里面查找都行.
第六题
题目
问题描述
小蓝要到店里买铅笔。
铅笔必须一整盒一整盒买，一整盒 12 支，价格 p 元。
小蓝至少要买 t 支铅笔，请问他最少花多少钱？
输入格式
输入一行包含两个整数 p、t，用一个空格分隔。
输出格式
输出一行包含一个整数，表示答案。
样例输入
5 30
样例输出
15
样例说明
小蓝至少要买3盒才能保证买到30支铅笔，总共花费 15 元。
评测用例规模与约定
对于所有评测用例，1 <= p <= 100，1 <= t <= 10000。
分析
重点就在于要整盒的买, 所以用Math.ceil()方法向上取整. 也可以使用余数判断法
int result = p * ((t % 12 == 0)?t / 12 : t / 12 + 1);
package cf.vbnm.q06;
//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 类名必须是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();
System.out.println((int) (Math.ceil(t / 12.0) * p));
}
}
第七题
题目
问题描述
给定一个三角形的三条边的长度 a, b, c，请问这个三角形是不是一个直角三角形。
输入格式
输入一行包含三个整数 a, b, c，表示三角形三边的长度，相邻整数之间用一个空格分隔。
输出格式
如果是直角三角形，输出“YES”（全大写），否则输出“NO”（全大写）。
样例输入
3 4 5
样例输出
YES
样例输入
4 5 4
样例输出
NO
评测用例规模与约定
对于所有评测用例，1 <= a, b, c <= 1000。
分析
勾三股四弦五, 老祖宗在《周髀算经》里就告诉我们怎么做这道题了.
package cf.vbnm.q07;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a, b, c;
a = sc.nextInt();
b = sc.nextInt();
//保证a最大
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
c = sc.nextInt();
//保证a最大
if (a < c) {
int tmp = a;
a = c;
c = tmp;
}
//c²+b²=a²
System.out.println((b * b + c * c) == a * a ? "YES" : "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。
分析
这个题有点绕, 写分析的时候我差点也被绕进去了.
这题是一种追溯来源类型, 我也不知道怎么叫, 反正就是想到了.
从题干可以看出顺序和获得的号码一样的话就会陷入信息孤岛, 从而获取不到别人的秘密.
第一轮:
4把秘密给5, 然后5把秘密给了6,6把秘密给4
这时4有了秘密6, 5有了秘密4,6有了秘密5
下一轮
4把手上的秘密6给5,5把手上的秘密4给6,6把手上的秘密5给4
这时4有了秘密4,6,5; 5有了秘密5,4,6; 6有了秘密6,5,4
此时4,5,6已经互相知道了各自的秘密
图片不是很好表示, 虽然文字有点绕, 但是意思在那里了.
我们用一个HashMap<Key, Value>来存储数据.
K是顺序, V是要传给卡片的下一个人.
用K(当前人)获取V(下一人序号), 得到V(下一人的序号)后删除K, 此时新的K就是之前获取到的V(下一人).用这个K(下一人)去获取V(下下一人)的序号后删除; 依次进行下去知道获取到null. 说明之前已经访问过要获取的序号了, 这些就是一个闭环, 将答案+1.
接下来从HashMap获取一个Key继续进行上述访问,直到HashMap.size()==0
我这里在获取输入的时候就解决了信息孤岛的情况,留到后面其实也行, 但我不知道map.keySet().iterator()资源占用情况怎样. 所以尽量少运行这个代码.
package cf.vbnm.q08;
import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
//最终答案
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>(i);
for (int j = 0; j < i; j++) {
int value = sc.nextInt();
if (j + 1 == value)
sum++;
else
map.put(j + 1, value);
}
//一直到把key用完
while (map.size() != 0) {
Integer entry = map.keySet().iterator().next(); //获取入口
Integer next;
do {
next = map.get(entry);//获取到下一个人
map.remove(entry);//移除当前人
entry = next;//下一人作为入口
} while (next != null); //如果没有下一人，说明当前搜索结束
sum++;
}
System.out.println(sum);
}
}
第九题
题目
问题描述
一个 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。
分析
想了一下,这道题应该是考的一个组合排列问题, 但是数据量会非常大. 1000!用long是肯定装不下的. 不过题目给了请输出答案除以 1000000007 的余数, 所以我也不会了.
答案就是C(n/2 , n).
因为只要确定了奇数位置的数, 偶数位置的数就固定了. 同时排序也固定了. 反之同理.
第十题
题目
问题描述
小蓝住在 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,深度优先搜索的题目, 把第一个格子作为根节点, 下一个可以走的位置作为下一个节点,一直重复下去直到没有位置可以走或者到终点.
就快搞出来的时候, 停电了!
Q.E.D.
