文章目录
试题 A: 相乘
试题 B: 直线
试题 C: 货物摆放
试题 D: 路径
试题 E: 回路计数
试题 A: 相乘
本题总分：5 分
【问题描述】
小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以1000000007 的余数，会得到不同的数。小蓝想知道，能不能在 1 至 1000000007 之间找到一个数，与 2021 相乘后再除以 1000000007 后的余数为 999999999。如果存在，请在答案中提交这个数；如果不存在，请在答案中提交 0。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
直接暴力，不过记得用long数据类型。
【Java代码】
public class Xiang { public static void main(String[] args) { long res = 0; for(long i = 1; i <= 1000000007L; i++) { if((i * 2021) % 1000000007L == 999999999L) { res = i; break; } } System.out.println(res); } }
【结果】
17812964
试题 B: 直线
本题总分：5 分
【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上 2 × 3 个整点 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。给定平面上 20 × 21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
①每个点坐标（x，y），即有两个数据组成，可以使用String类型“x,y”形式存储。使用时split以“,”分开并且使用Integer的ParseInt。
②两点确定一直线使用两点式(y-y1)/(y2-y1)=(x-x1)/(x2-x1)表示直线，转换成标准式(y1-y2)x+(x2-x1)y-y1(x2-x1)+x1(y2-y1)=0。
③对系数和常数进行约分，即求三者最大公因数。
④取唯一，即对于求得结构相同的只算一次，可以考虑使用HashSet存储。
【Java代码】
import java.util.ArrayList; import java.util.HashSet; public class test { public static void main(String[] args) { //生成存储点 ArrayList<String> ps = new ArrayList<>(); for (int i = 0; i < 20; i++) { for (int j = 0; j < 21; j++) { //以"x,y"形式存储 ps.add(i + "," + j); } } //取点求直线 HashSet<String> line = new HashSet<>(); //第一层循环取第一个点 for (int i = 0; i < ps.size(); i++) { String p1 = ps.get(i); int x1 = Integer.parseInt(p1.split(",")[0]); int y1 = Integer.parseInt(p1.split(",")[1]); //第二层循环取第二个点 for (int j = i+1; j < ps.size(); j++) { String p2 = ps.get(j); int x2 = Integer.parseInt(p2.split(",")[0]); int y2 = Integer.parseInt(p2.split(",")[1]); //根据(y1-y2)x+(x2-x1)y-y1(x2-x1)+x1(y2-y1)=0求系数及常数 int a = y1 - y2; int b = x2 - x1; int c = x1*(y2-y1)-y1*(x2-x1); //求最大公因数约分 int m = gcd(gcd(a, b), c); a /= m; b/= m; c/= m; line.add(a + "," + b + "," + c); } } System.out.println(line.size()); } //求最大公因数 public static int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); } }
【结果】
40257
试题 C: 货物摆放
本题总分：10 分
【问题描述】
小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 L、W、H 的货物，满足 n = L × W × H。
给定 n，请问有多少种堆放货物的方案满足要求。
例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1。
请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
①由于n值过大，直接暴力破解会超时。
②因此考虑到缩小数据，由题意可知L、W、H可能取值都是n的因子，因此只要找到n的全部因子，然后再循环破解就可以了，找因子时开方也极大缩小了数据。
【Java代码】
import java.util.ArrayList; public class test { public static void main(String[] args) { long n = 2021041820210418l; //找出n的所有因子并保存 ArrayList<Long> list = new ArrayList<>(); for (long i = 1l; i < Math.sqrt(n)+1; i++) { if (n % i == 0){ list.add(i); if (i * i != n){ list.add(n/i); } } } //所有因子进行匹配 int count = 0; for (int i = 0; i < list.size(); i++) { for (int j = 0; j < list.size(); j++) { for (int k = 0; k < list.size(); k++) { if (list.get(i)*list.get(j)*list.get(k) == n){ count++; break; } } } } System.out.println(count); } }
【结果】
2430
试题 D: 路径
【问题描述】
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
带权最短路径，可以使用Floyd算法实现。（关于Floyd算法可以自行搜索）
【Java代码】
public class Floyd { //求a和b的最小公约数 static int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b); } //求a和b的最小公倍数 static int lcm(int a,int b){ return a * b / gcd(a,b); } public static void main(String[] args) { //初始化方阵 int[][] floyd = new int[2021][2021]; for (int i = 0; i < 2021; i++) { for (int j = i + 1; j < i + 22 && j < 2021; j++) { floyd[i][j] = floyd[j][i] = lcm(i+1, j+1); } } //Floyd算法 for (int k = 0; k < floyd.length; k++) { for (int i = 0; i < floyd.length; i++) { for (int j = 0; j < floyd.length; j++) { if (floyd[i][k] != 0 && floyd[k][j] != 00 && (floyd[i][j] == 0 || floyd[i][j] > floyd[i][k] + floyd[k][j])) { floyd[i][j] = floyd[i][k] + floyd[k][j]; } } } } //输出第一个点到第2021个点的距离 System.out.println(floyd[0][2020]); } }
【结果】
10266837
试题 E: 回路计数
本题总分：15 分
【问题描述】
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
深度优先搜索+Map剪枝
【Java代码】
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; public class DPMAP { //求a和b的最小公约数 static int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b); } static ArrayList<Integer>[] list = new ArrayList[22]; //邻接表存储每个教学楼及其可以到达的教学楼 static Map<String, Long> set = new HashMap<String, Long>(); //存储状态及其路线条数 public static void main(String[] args) { //初始化邻接表 for (int i = 1; i < list.length; i++) list[i] = new ArrayList<Integer>(); for (int i = 1; i < 22; i++) for (int j = i + 1; j < 22; j++) if (gcd(i, j) == 1) { list[i].add(j); list[j].add(i); } System.out.println(dfs(21, 1, 0)); } //深度优先搜索 public static long dfs(int total, int begin, int state) { if (total == 0) return 1; //返回第一栋教学楼了 long res = 0; for (int p : list[begin]) { if ((state & (1 << p)) != (1 << p)) { long r = 0; if (set.containsKey(p + "-" + state)) { //剪枝 r = set.get(p + "-" + state); } else { if (p != 1 || p == 1 && total == 1) { r = dfs(total-1, p, state | (1 << p)); } set.put(p + "-" + state, r); } res += r; } } return res; } }
【结果】
881012367360
