【题解 | 分享】2023年十四届蓝桥杯国赛（Java B组）

答案：640720414

参考：

public class Main {static int mod = 1000000007;public static void main(String[] args) {long sum = power(2023, 2023);long p1 = ((sum % mod) * power(  7,  mod - 2)) % mod;long p2 = ((sum % mod) * power( 17,  mod - 2)) % mod;long p3 = ((sum % mod) * power(7*17, mod - 2)) % mod;long ans = (sum - p1 - p2 + p3 + mod + mod) % mod;System.out.println(ans);}static long power(long a, long p) { // 乘法快速幂long ans = 1;a %= mod;while (p != 0) {if ((p & 1) == 1) {ans = (ans * a) % mod;}a = (a * a) % mod;p >>= 1;}return ans;}
}

解题思路：

我们知道，如果两个数互质，那么它们的最大公约数为1，我们需要找出在 $[1,2023^{2023}]$ 范围内与 $2023$ 互质的数的数量。

通过将 $2023$ 分解质因子，发现是 $7$ 和 $17$，所以在 $[1,2023^{2023}]$ 范围内，与 $2023$ 不互质的数，要么是 $7$ 的倍数，要么是 $17$ 的倍数，要么是 $7$ 和 $17$ 的公倍数。

因此，我们只需先计算所有数的数量（$2023^{2023}$），然后减去 $7$ 的倍数、 $17$的倍数的数量以及 $7$ 与 $17$ 的公倍数。但需要注意，在减去$7$的倍数和$17$的倍数的数量时，我们实际上减去了两次$7$和$17$的公倍数的数量，因为$7$和$17$的公倍数既是$7$的倍数，也是$17$的倍数。因此在实际计算中，我们需要再加上一次7和17的公倍数的数量，以抵消这个重复计算的部分。

这也是很浅的"容斥原理"，一分析就明白了。

另外，在实际编码中，我们可以：

• 利用乘法快速幂来加速计算 $a^b$ 。
• 在计算有多少个数是 7 的倍数时，我们使用的是除法，而题目要求计算结果对 $1000000007$ 取模，对于除法 (a / b) % mod来说，取模操作比较特殊，需要先求出逆元，我们使用power(b, mod - 2) 可以计算 b在模 mod 下的逆元。此时 (a / b) % mod 可转化为 ((a % mod) * (power(b, mod - 2))) % mod。
• 最终计算答案时，之所以要加上两次 mod，是因为要处理减法取模可能出现的负数结果。

答案：1307261675

这道题也不难，直接模拟求解就行，只不过一个个数去求逆元太慢了，下面展示如何加速求解 $1$ ~ $n$ 区间内每个数的逆元，套用递推公式即可。

参考：

public class Main {static int n = 233333333;static int[] inv = new int[n+1];static final int MOD = 2146516019;public static void main(String[] args) {// 初始化：连续数字逆元的线性递推inv[1] = 1;for (int i = 2; i <= n; i++) {// 核心公式，不用纠结为什么，会用就行（原理是基于费马小定理和欧几里得算法）inv[i] = (int) (MOD - (long) inv[MOD % i] * (MOD / i) % MOD);}// 计算答案long ans = inv[1];for (int i = 2; i <= n; i++) {ans = (ans ^ inv[i]);}System.out.println(ans);}
}

连续数字逆元的线性递推是一种高效计算模 $p$ 下每个数逆元的方法。

在模 $p$ 意义下，我们可以使用以下公式来计算 $123...n$ 每个数的逆元：

inv[1] = 1
inv[i] = (int) (p - (long) inv[p % i] * (p / i) % p);

这个公式的推导基于费马小定理和欧几里得算法，其时间复杂度是 $O(n)$ ，所以它非常高效的。

样例输入：

2
2 2 3 4

样例输出：

14

这道题，不知道为什么，一眼贪心，结果还真是。具体的，他们先把数列排个序，然后每次都拿最小的数和最大的数进行配对，相乘后累加答案，再去计算下一轮的结果，以此类推：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(bf);static PrintWriter out = new PrintWriter(System.out);public static void main(String[] args) throws IOException {in.nextToken();int n = (int)in.nval;n *= 2;long[] nums = new long[n];for(int i = 0; i<n; i++) {in.nextToken();nums[i] = (long)in.nval;}Arrays.sort(nums);int l = 0, r = n-1;long ans = 0;while(l < r) {ans += (nums[l++] * nums[r--]);}out.print(ans);out.flush();out.close();bf.close();}
}

共四种情况，分类讨论即可，纯模拟。

参考：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(System.out);public static void main(String[] args) throws IOException {String line = bf.readLine(); // A op B = Cint n = line.length();int A = 0, B = 0;char[] str = line.toCharArray();if(str[n-1] == '?') { // A op B = ?int idx = 0;// 先收集Awhile(str[idx] >= '0' && str[idx] <= '9') {A = A * 10 + (str[idx] - '0');idx++;}// 收集opchar op = str[idx++];// 最后收集Bwhile(str[idx] >= '0' && str[idx] <= '9') {B = B * 10 + (str[idx] - '0');idx++;}int C = compute1(A, op, B);System.out.println(C);} else {String[] parts = line.split("=");int C = Integer.parseInt(parts[1]);String s = parts[0];int m = s.length();char op = ' ';if(s.charAt(0) == '?') { // ? op B = Cop = s.charAt(1);for(int i = 2; i<m; i++) {B = (B * 10) + (s.charAt(i) - '0');}A = compute2(B, op, C);System.out.println(A);} else if(s.charAt(m-1) == '?') { // A op ? = Cop = s.charAt(m-2);for(int i = 0; i<m-2; i++) {A = (A * 10) + (s.charAt(i) - '0');}B = compute3(A, op, C);System.out.println(B);				} else { // A ? B = CString[] temp = s.split("\\?");A = Integer.parseInt(temp[0]);B = Integer.parseInt(temp[1]);op = compute4(A, B, C);System.out.println(op);}}		}public static int compute1(int A, char op, int B) { // A op B = ?int ans = 0;switch (op) {case '+':ans = A + B;break;case '-':ans = A - B;break;case '*':ans = A * B;break;case '/':ans = A / B;break;}return ans;}public static int compute2(int B, char op, int C) { // ? op B = Cint A = 0;switch (op) {case '+':A = C - B;break;case '-':A = C + B;break;case '*':A = C / B;break;case '/':A = C * B;break;}return A;}public static int compute3(int A, char op, int C) { // A op ? = Cint B = 0;switch (op) {case '+':B = C - A;break;case '-':B = A - C;break;case '*':B = C / A;break;case '/':B = A / C;break;}return B;}public static char compute4(int A, int B, int C) { // A ? B = Cchar ans = ' ';if(A + B == C) {ans = '+';} else if(A - B == C) {ans = '-';} else if(A * B == C) {ans = '*';} else if(A / B == C) {ans = '/';}return ans;}
}

思路：

经典旅行商问题，可用状态压缩DP来求解。

状态压缩是动态规划的一个小技巧，一般应用在集合问题中。当DP的状态是一个集合时，把集合的组合或排列用一个二进制来表示，也就是用某个数的二进制位（0/1组合）来表示集合的一个子集，从而用二进制的位操作来处理DP状态。

参考：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(bf);static int n;static int MAXN = 18;static int x[] = new int[MAXN];static int y[] = new int[MAXN];static int z[] = new int[MAXN];static int w[] = new int[MAXN];static double dp[][] = new double[1 << MAXN][MAXN];public static void main(String[] args) throws IOException {// 输入数据n = nextInt();for (int i = 0; i < n; i++) {x[i] = nextInt();y[i] = nextInt();z[i] = nextInt();w[i] = nextInt();}// 初始化缓存表（用于记忆化搜索）for (int s = 0; s < (1 << n); s++) {for (int i = 0; i < n; i++) {dp[s][i] = -1;}}// 开始计算int end = (1 << n) - 1; // 进攻所有星球的最终集合状态，即全是1的状态（每个星球都进攻过了）double ans = Double.MAX_VALUE;for (int i = 0; i < n; i++) {// 尝试从每个星球出发，进攻所有星球所需的最少能量是多少？ans = Math.min(ans, f(1 << i, i, end));}System.out.printf("%.2f", ans);}/*** 记忆化搜索，也可以改为严格位置依赖的动态规划* * @param status 一个整型变量，表示当前的星球访问状态，我们关注其二进制位。如果为1，表示已经进攻过该星球，否则表示未进攻过。* @param idx    表示当前所在的星球的位置（范围从 0 到 n-1 ）。* @param end    终止状态，即表示所有星球都被访问过的状态（所有比特位都为1）。* @return 返回从当前idx星球出发，进攻所有未访问过的星球，所需的最少能量。*/public static double f(int status, int idx, int end) {if (status == end) { // 已经访问了所有星球，到达终止状态return 0; }if (dp[status][idx] != -1) { // 缓存命中，直接返回return dp[status][idx];}double ans = Double.MAX_VALUE;for (int i = 0; i < n; i++) {// 如果 i 星球还没有被访问过，则尝试访问，并更新所需的最少能量if ((status & (1 << i)) == 0) {// status | (1 << i)：将i星球添加到集合 status 中// dist(idx, i)：从当前 idx 星球进攻 i 星球所需的能量ans = Math.min(ans, f(status | (1 << i), i, end) + dist(idx, i));}}// 加缓存dp[status][idx] = ans;return ans;}// 计算两点之间所需能量public static double dist(int v1, int v2) {double dx = Math.abs(x[v1] - x[v2]);double dy = Math.abs(y[v1] - y[v2]);double dz = Math.abs(z[v1] - z[v2]);return Math.sqrt(dx * dx + dy * dy + dz * dz) * w[v2];}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}

解题：

这道题的解法也是通过观察得知，我们根据样例一的数据进行绘表：

我们发现，这个表格：

• 第 1 行和第 1 列均是：首项为 1 ，公差为 1 的等差数列
• 第 2 行和第 2 列均是：首项为 2 ，公差为 1 的等差数列
• 第 3 行和第 3 列均是：首项为 3 ，公差为 3 的等差数列
• …
• 第 i 行和第 i 列均是：首项为 i ，公差为 i 的等差数列

对于 $a$ 序列中的每一个元素$a_i$，我们需要在当前这一列（等差数列）中查看每一个数 $b_i$，判断 $a_i$ 是否整除 $b_i$，即 $b_i\%a_i=0$。

因此：

• $a_1$ 整除 $b_2$ 和 $b_4$ ，该列贡献为 2
• $a_2$ 整除 $b_1$ 、$b_2$ 、 $b_3$ 和 $b_4$ ，该列的贡献为 4
• $a_3$ 整除 $b_1$ 、$b_2$ 、 $b_3$ 和 $b_4$ ，该列的贡献为 4
• $a_4$ 整除 $b_1$ 、$b_2$ 、 $b_3$ 和 $b_4$ ，该列的贡献为 4

最终答案为 $2+4+4+4=14$

那现在关键在于，如何判断并查出 $a_i$ 在首项为 $i$，公差为 $i$ 的等差数列中，整除了哪些数？

答案取决于 $a_i$ 和 $i$ 的最小公倍数，我们记为 lcm(ai, i)。那么每一列对答案的贡献就是 (i*n)/lcm(ai,i)，其中 i*n 用于求出当前这一列等差数列的末尾数值，用它去除以 $a_i$ 和 $i$ 的最小公倍数，就能够得到符合条件的数目。

比如：

$i=1$，此时 $a_1$ 的值为$2$，$2$ 和 $1$ 的最小公倍数为 $2$，等差数列的末尾元素为 $4$，那么该列对答案的贡献就是 $4/2=2$。

$i=2$，此时 $a_2$ 的值为$2$，$2$ 和 $2$ 的最小公倍数为 $2$，等差数列的末尾元素为 $8$，那么该列对答案的贡献就是 $8/2=4$。

以此类推。

纯粹通过观察，得出结论。

参考：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(bf);static long n, ai, ans;public static void main(String[] args) throws IOException {n = nextLong();for(long i = 1; i<=n; i++) {ai = nextLong();ans += i * n / lcm(ai, i);}System.out.println(ans);}public static long lcm(long a, long b) {return a / gcd(a, b) * b;}public static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}public static long nextLong() throws IOException {in.nextToken();return (long)in.nval;}
}

解题：

求最小生成树中的最大单边权重：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {public static int MAXN = 200001;public static int MAXM = 200001;public static int[] father = new int[MAXN];	// 并查集public static int[][] edges = new int[MAXM][3]; // u, v, wpublic static int n, m;public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));public static StreamTokenizer in = new StreamTokenizer(br);public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {// 输入并初始化数据n = nextInt();for (int i = 1; i <= n; i++) {father[i] = i;}m = nextInt();for (int i = 0; i < m; i++) {edges[i][0] = nextInt();edges[i][1] = nextInt();edges[i][2] = nextInt();}// 根据边的权重排序，用于Kruskal算法求最小生成树Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);int ans = Integer.MIN_VALUE;int edgeCnt = 0;for (int i = 0, u, v, w; i < m; i++) {u = edges[i][0];v = edges[i][1];w = edges[i][2];if (union(u, v)) {	// 求生成最小树，并维护单次最大花费edgeCnt++;ans = Math.max(ans, w);}}out.println(edgeCnt == n-1 ? ans : -1);out.flush();out.close();br.close();}public static int find(int i) {if (i != father[i]) {father[i] = find(father[i]);}return father[i];}public static boolean union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {father[fx] = fy;return true;} else {return false;}}public static int nextInt() throws IOException {in.nextToken();return (int)in.nval;}
}

思路：

对每个子序列求最大值和最小值的差值，并计算平均值：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(bf);static int n, k;static int MAXN = 100001;static int[] arr = new int[MAXN];public static void main(String[] args) throws IOException {n = nextInt();k = nextInt();for (int i = 0; i < n; i++) {arr[i] = nextInt();}long sum = 0;for (int i = 0, max, min; i < n-k+1; ++i) {max = Integer.MIN_VALUE;min = Integer.MAX_VALUE;for (int j = i; j < i+k; ++j) {max = Math.max(arr[j], max);min = Math.min(arr[j], min);}sum += (max - min);}double ans = (double) sum / (n-k+1);System.out.printf("%.2f\n", ans);}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}

思路：

根据题意，枚举并累加答案即可：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer in = new StreamTokenizer(bf);static int n, k, p1, p2, curHeight;static int MAXN = 37;static long[][] f = new long[MAXN][MAXN];static long ans = 0;public static void main(String[] args) throws IOException {n = nextInt();k = nextInt();compute();System.out.println(ans);}public static void compute() {f[0][0] = 1;f[1][1] = 1;// 遍历节点数for (int node = 2; node <= n; node++) {// 左子树的节点数为lCnts，右子树的节点数为rCntsfor (int lCnts = 0, rCnts; lCnts < node; lCnts++) {rCnts = node - lCnts - 1;// 左子树的高度为lHeight，右子树的高度为rHeight，for (int lHeight = 0; lHeight <= lCnts; lHeight++) {for (int rHeight = 0; rHeight <= rCnts; rHeight++) {p1 = Math.max(lHeight, rHeight);p2 = k * Math.min(lHeight, rHeight);if (p1 >= p2) {// 当前二叉树的高度curHeight = Math.max(lHeight, rHeight) + 1;// 有 node 个节点，高度为 curHeight 的非对称二叉树有多少个？f[node][curHeight] += f[lCnts][lHeight] * f[rCnts][rHeight];}}}}}// 有 n 个节点，高度为 1 的非对称二叉树有多少个？// 有 n 个节点，高度为 2 的非对称二叉树有多少个？// ...// 有 n 个节点，高度为 n 的非对称二叉树有多少个？for (int i = 1; i <= n; i++) {ans += f[n][i];}}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}

样例输入：

7 7
2 -1 -1 2 -1 -1 2 -1 -1 2 4 -1 2 14 -1 2 19 -1 2 11 -1
2 -1 -1 2 -1 -1 2 21 24 1 1 1 1
2 -1 -1 2 26 18 1 1 1 1 1
2 -1 12 1 1 2 -1 -1 2 -1 3 1 1
2 -1 16 1 1 2 17 -1 2 11 8 1 1
2 -1 28 1 1 1 1 1 2 -1 -1
2 -1 14 1 1 1 1 2 -1 -1 2 -1 -1

样例输出：

_ _ _ _ _ _ _
_ _ _ 3 9 7 5
_ _ 6 1 5 4 2
_ 8 4 _ _ 2 1
_ 9 7 _ _ 5 3
_ 7 3 9 8 1 _
_ 2 1 8 3 _ _

思路：

用状态压缩记录10个数的选取方案，每个方案选择的数的长度为len，总和则为sum，对于每个条目，枚举选择状压方案中的哪个数，消掉哪一位之后再进行递归调用，最后判断当前方案是否合法。