【题解 | 分享】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

样例输出：

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

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 = C
		int n = line.length();
		int A = 0, B = 0;
		char[] str = line.toCharArray();

		if(str[n-1] == '?') { // A op B = ?
			int idx = 0;
			// 先收集A
			while(str[idx] >= '0' && str[idx] <= '9') {
				A = A * 10 + (str[idx] - '0');
				idx++;
			}
			// 收集op
			char op = str[idx++];
			// 最后收集B
			while(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 = C
				op = 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 ? = C
				op = 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 = C
				String[] 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 = C
		int 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 ? = C
		int 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 = C
		char 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, w
	public 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，右子树的节点数为rCnts
			for (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，对于每个条目，枚举选择状压方案中的哪个数，消掉哪一位之后再进行递归调用，最后判断当前方案是否合法。