第十二届蓝桥杯–javaB组第二场-一一网

【摘要】
复盘心得其实有些题我是可以做出来的，比如第四题和第八题，只是第一次参加，没有什么经验，把太多时间浪费在第五题，结果容易的分没拿到，难的分也没拿到。结果出来了–省三。有点丢人。与预期有点差别。

第一题：求余
题目

在 C/C++/Java/Python 等语言中，使用 % 表示求余，请问 2021%20 的值是多少？

答案：1
public…

复盘心得
其实有些题我是可以做出来的，比如第四题和第八题，只是第一次参加，没有什么经验，把太多时间浪费在第五题，结果容易的分没拿到，难的分也没拿到。结果出来了–省三。有点丢人。与预期有点差别。

第一题：求余

题目

在 C/C++/Java/Python 等语言中，使用 % 表示求余，请问 2021%20 的值是多少？

答案：1

public class ASC { public static void main(String[] args) { System.out.println(2021%20); }
}
  
 
  1
  2
  3
  4
  5
  6

第二题：双阶乘

题目
一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。n 的双阶乘用 n!! 表示。

例如：

3!! = 3 × 1 = 3。

8!! = 8 × 6 × 4 × 2 = 384。

11!! = 11 × 9 × 7 × 5 × 3 × 1 = 10395。
请问，2021!! 的最后 5 位（这里指十进制位）是多少？

注意：2021!! = 2021 × 2019 × · · · × 5 × 3 × 1。

提示：建议使用计算机编程解决问题。

代码

public class 双阶乘 { public static void main(String[] args) { System.out.println(f(2021)); } private static long f(long k) { if (k==1){ return 1; }else return (k*f(k-2))%100000; }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

第三题：格点

题目
如果一个点 (x, y) 的两维坐标都是整数，即 x ∈ Z 且 y ∈ Z，则称这个点为一个格点。如果一个点 (x, y) 的两维坐标都是正数，即
x > 0 且 y > 0，则称这个点在第一象限。请问在第一象限的格点中，有多少个点 (x, y) 的两维坐标乘积不超过 2021，即 x · y ≤ 2021。
提示：建议使用计算机编程解决问题。

代码

public class 格点 { static  int ans = 0; public static void main(String[] args) { for (long i = 1; i <=2021 ; i++) { for (int j = 1; j <=2021 ; j++) { if (i*j<=2021){ ans++; } } } System.out.println(ans); }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

第四题：整数分解

题目将 3 分解成两个正整数的和，有两种分解方法，分别是 3 = 1 + 2 和3 = 2 + 1。注意顺序不同算不同的方法。将 5
分解成三个正整数的和，有 6 种分解方法，它们是 1+1+3 = 1+2+2 =1 + 3 + 1 = 2 + 1 + 2 = 2 + 2

1 = 3 + 1 + 1。请问，将 2021 分解成五个正整数的和，有多少种分解方法？

借鉴别人的解题思路：
考试的时候，用了四个for循环，结果跑了半个小时也没有跑出来，而且当时也没有做剪枝。
别人的思路，三重循环跑一下前三个数的情况，后两个数可能情况只有m-1种情况。
也可以用排列组合的知识来求解。

代码：

public class 整数分解 { static  long ans = 0; public static void main(String[] args) { int num = 2021; for (int i = 1; i < num; i++) { for (int j = 1; j <num ; j++) { for (int k = 1; k < num; k++) { int m = num - i - j - k; if (m<=1) break; ans += m -1; } } } System.out.println(ans); }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

第五题：城邦

小蓝国是一个水上王国，有 2021 个城邦，依次编号 1 到 2021。在任意两个城邦之间，都有一座桥直接连接。为了庆祝小蓝国的传统节日，小蓝国政府准备将一部分桥装饰起来。对于编号为 a 和 b 的两个城邦，它们之间的桥如果要装饰起来，需要的费用如下计算：找到 a 和 b 在十进制下所有不同的数位，将数位上的数字求和。例如，编号为 2021 和 922 两个城邦之间，千位、百位和个位都不同，将这些数位上的数字加起来是 (2 + 0 + 1) + (0 + 9 + 2) = 14。注意 922 没有千位，千位看成 0。为了节约开支，小蓝国政府准备只装饰 2020 座桥，并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。请问，小蓝国政府至少要花多少费用才能完成装饰。
提示：建议使用计算机编程解决问题。

解题思路：不会（手动狗头）

第六题：特殊年份

题目

今年是 2021 年，2021 这个数字非常特殊，它的千位和十位相等，个位比百位大 1，我们称满足这样条件的年份为特殊年份。输入 5
个年份，请计算这里面有多少个特殊年份。【输入格式】输入 5 行，每行一个 4 位十进制数（数值范围为 1000 至
9999），表示一个年份
【输出格式】输出一个整数，表示输入的 5 个年份中有多少个特殊年份。
【样例输入】
2019
2021
1920
2120
9899
【样例输出】 2
【样例说明】 2021 和 9899 是特殊年份，其它不是特殊年份。

解题思路：
没啥难度，直接获取各个位数，进行判断即可。

import java.util.Scanner;

public class 特殊年份 { static int ans =0; public static void main(String[] args) { Scanner cin = new Scanner(System.in); for (int i = 0; i <5 ; i++) { int num = cin.nextInt(); int a = num/1000; int b = (num%1000)/100; int c = (num%100)/10; int d = (num%100)%10; //  System.out.println(a +" "+ b+ " "+ c +" " +d);  检验各位数是否正确 if (a==c&&d-1==b){ ans++; } } System.out.println(ans); }
}

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

第七题：小平方

题目

小蓝发现，对于一个正整数 n 和一个小于 n 的正整数 v，将 v 平方后对 n取余可能小于 n 的一半，也可能大于等于 n的一半。请问，在 1 到 n − 1 中，有多少个数平方后除以 n 的余数小于 n 的一半。例如，当 n = 4 时，1, 2, 3的平方除以 4 的余数都小于 4 的一半。又如，当 n = 5 时，1, 4 的平方除以 5 的余数都是 1，小于 5 的一半。而2, 3的平方除以 5 的余数都是 4，大于等于 5 的一半。

【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一个整数，表示满足条件的数的数量。
【样例输入】
5
【样例输出】
2
【评测用例规模与约定】对于所有评测用例，1 ≤ n ≤ 10000。

解题思路
数据<10000，用int应该可以了。

import java.util.Scanner;

public class 小平方 { static int ans = 0; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int k = cin.nextInt(); for (int i = 1; i < k; i++) { if ((i*i)%k<(k/2)){ ans++; } } System.out.println(ans); }
}
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

第八题：完全平方数

题目：一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 $ a = b^2 $。给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。

【输入格式】
输入一行包含一个整数 n。

【输出格式】
输出找到的最小的正整数 x。

【样例输入】
12
【样例输出】
3
【样例输入】
15
【样例输出】
15
【评测用例规模与约定】对于 30% 的评测用例，1 ≤ n ≤ 1000，答案不超过 1000。

对于 60% 的评测用例，1 ≤ n ≤ 108，答案不超过 $ 10^8 。

对于所有评测用例，1 ≤ n ≤ 1012，答案不超过 $ 10^{12} 。

import java.util.Scanner;

public class 完全平方数 { public static void main(String[] args) { Scanner cin = new Scanner(System.in); long k = cin.nextLong() ; long num; for (double i = 1; i <=k ; i++) { num = (long) Math.sqrt((long) i*k); if (num*num==i*k){ System.out.println((int)i); break; } } }
}
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

第九题：负载均衡

题目：

有 n 台计算机，第 i 台计算机的运算能力为 vi。
有一系列的任务被指派到各个计算机上，第 i 个任务在 ai 时刻分配，指定
计算机编号为 bi ，耗时为 ci 且算力消耗为 di 。如果此任务成功分配，将立刻
开始运行，期间持续占用 bi 号计算机 di 的算力，持续 ci 秒。
对于每次任务分配，如果计算机剩余的运算能力不足则输出 −1，并取消这
次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。
【输入格式】
输入的第一行包含两个整数 n, m，分别表示计算机数目和要分配的任务数。
第二行包含 n 个整数 v1, v2, · · · vn，分别表示每个计算机的运算能力。
接下来 m 行每行 4 个整数 ai, bi, ci, di，意义如上所述。数据保证 ai 严格递
增，即 ai < ai+1。
【输出格式】
输出 m 行，每行包含一个数，对应每次任务分配的结果。
【样例输入】
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
【样例输出】
2
-1
-1
1
-1
0
【样例说明】
时刻 1，第 1 个任务被分配到第 1 台计算机，耗时为 5 ，这个任务时刻 6
会结束，占用计算机 1 的算力 3。
时刻 2，第 2 个任务需要的算力不足，所以分配失败了。
时刻 3，第 1 个计算机仍然正在计算第 1 个任务，剩余算力不足 3，所以
失败。
时刻 4，第 1 个计算机仍然正在计算第 1 个任务，但剩余算力足够，分配
后剩余算力 1。
时刻 5，第 1 个计算机仍然正在计算第 1, 4 个任务，剩余算力不足 4，失
败。
时刻 6，第 1 个计算机仍然正在计算第 4 个任务，剩余算力足够，且恰好
用完。
【评测用例规模与约定】
对于 20% 的评测用例，n, m ≤ 200。
对于 40% 的评测用例，n, m ≤ 2000。
对于所有评测用例，1 ≤ n, m ≤ 200000，1 ≤ ai, ci, di, vi ≤ 109，1 ≤ bi ≤ n。

第十题：国际象棋

题目:

众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 8 个皇后，使得两
两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简
单了，意犹未尽。作为一个国际象棋迷，他想研究在 N × M 的棋盘上，摆放 K
个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需
计算答案除以 1000000007 (即 109 + 7) 的余数。
如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 (x, y)
格的马（第 x 行第 y 列）可以攻击 (x + 1, y + 2)、(x + 1, y − 2)、(x − 1, y + 2)、 (x − 1, y − 2)、(x + 2, y + 1)、(x + 2, y − 1)、(x − 2, y + 1) 和 (x − 2, y − 1) 共 8 个
格子。
【输入格式】
输入一行包含三个正整数 N, M, K，分别表示棋盘的行数、列数和马的个
数。
试题 J: 国际象棋 13
第十二届蓝桥杯大赛软件赛省赛第二场 Java 大学 B 组
【输出格式】
输出一个整数，表示摆放的方案数除以 1000000007 (即 109 + 7) 的余数。
【样例输入】
1 2 1
【样例输出】
2
【样例输入】
4 4 3
【样例输出】
276
【样例输入】
3 20 12
【样例输出】
914051446
【评测用例规模与约定】
对于 5% 的评测用例，K = 1；
对于另外 10% 的评测用例，K = 2；
对于另外 10% 的评测用例，N = 1；
对于另外 20% 的评测用例，N, M ≤ 6，K ≤ 5；
对于另外 25% 的评测用例，N ≤ 3，M ≤ 20，K ≤ 12；
对于所有评测用例，1 ≤ N ≤ 6，1 ≤ M ≤ 100，1 ≤ K ≤ 20。