碎碎念:
在攻克第十题的时候教学楼停电了, 本来想保存了代码到寝室慢慢做, 刚准备保存, 啪一下没电了, 第十题已经写了的代码还没来得及保存就没了, 淦.

第一题

题目

问题描述
小蓝的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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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。
要想编码后的总长度尽量小,应当让出现次数多的字符对应的编码短,出现次数少的字符对应的编码长。
请问,在最优情况下,编码后的总长度最少是多少?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

分析

题目中很明显的给出了解题思路:要想编码后的总长度尽量小,应当让出现次数多的字符对应的编码短,出现次数少的字符对应的编码长。
所以我们首先确定一种编码方案:
编码方案
这道题考的是哈夫曼树和哈夫曼编码,是一种用于无损数据压缩的熵编码算法.
哈夫曼编码-百度百科 霍夫曼编码-维基百科 如果对哈夫曼编码不清楚会很吃亏, 因为求到的不一定是最短的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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));
}
}

哎我就是想加package, 这是我的标志. 注意复制的时候别复制进去了

第七题

题目

问题描述
  给定一个三角形的三条边的长度 a, b, c,请问这个三角形是不是一个直角三角形。
输入格式
  输入一行包含三个整数 a, b, c,表示三角形三边的长度,相邻整数之间用一个空格分隔。
输出格式
  如果是直角三角形,输出“YES”(全大写),否则输出“NO”(全大写)。
样例输入
3 4 5
样例输出
YES
样例输入
4 5 4
样例输出
NO
评测用例规模与约定
  对于所有评测用例,1 <= a, b, c <= 1000。

分析

勾三股四弦五, 老祖宗在《周髀算经》里就告诉我们怎么做这道题了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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把手上的秘密65,5把手上的秘密46,6把手上的秘密54
这时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()资源占用情况怎样. 所以尽量少运行这个代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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,深度优先搜索的题目, 把第一个格子作为根节点, 下一个可以走的位置作为下一个节点,一直重复下去直到没有位置可以走或者到终点.

就快搞出来的时候, 停电了, 淦! 思路在, 代码有空更新