2023年第十四届蓝桥杯省赛真题(Java B组)

2024-02-24数据结构与算法20 分钟280 次阅读
AI 摘要salmon-ai

本文详细解析了 2023 年第十四届蓝桥杯省赛 Java B 组的多道真题

题目链接:https://www.lanqiao.cn/paper/3872/result/

试题 A: 阶乘求和【填空题】

本题总分:5 分

【问题描述】
令 S = 1! + 2! + 3! + … + 202320232023!,求 S 的末尾 9 位数字。 提示:答案首位不为 0。

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

解法

思路:对于数据量大的计算题,我们一般可以只保留某部分有效数字计算即可,题目也告诉我们只求S的末尾9位数字,故我们只需计算阶乘到末尾9位数字都为0的时候即可,因为之后的阶乘项必然后九位数字都为0,如:1000000000!=123*...*1000000000=xxxx...0000000000。由于10亿的阶乘数字过大,但我们知道其后九位数字为0即可。

最终答案:420940313

我的题解

java 复制代码
// 阶乘求和
public class Main {
	public static void main(String[] args) {
		long mod = (long) 1e9;
		long s = 2; // 存储上一次的阶乘
		long ans = 3; // 阶乘和
		for (long i = 3; i <= 202320232023L; i++) {
			// 如果这个数对模取余等于0,说明它后面九位数都是0,故结束循环,算下去无意义
			if (i % mod == 0) {
				break;
			}
			// 计算当前阶乘
			s = s * i % mod;
			// 求和
			ans = (ans + s) % mod;
		}
		System.out.print(ans);
	}
}

试题 B: 幸运数字【填空题】

本题总分:5 分

【问题描述】
哈沙德数是指在某个固定的进位制当中,可以被各位数字之和整除的正整 数。例如 126 是十进制下的一个哈沙德数,因为 (126)10 mod (1+2+6) = 0;126也是八进制下的哈沙德数,因为 (126)10 = (176)8,(126)10 mod (1 + 7 + 6) = 0; 同时 126 也是 16 进制下的哈沙德数,因为 (126)10 = (7e)16,(126)10 mod (7 + e) = 0。小蓝认为,如果一个整数在二进制、八进制、十进制、十六进制下均为 哈沙德数,那么这个数字就是幸运数字,第 1 至第 10 个幸运数字的十进制表示 为:1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数字是多少?你只需要告诉小蓝这个整数的十进制表示即可。

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

解法

思路:我们可以从1开始循环判断,如果是哈沙德数则进行累计,直到累计到幸运数字等于2023时,输出当前的数字即可。

最终答案:215040

我的题解

java 复制代码
// 幸运数
public class Main {
	public static void main(String[] args) {
		int count = 0;
		for (int i = 1; true; i++) {
			if (isHasa(i, 0) && isHasa(i, 1) && isHasa(i, 2) && isHasa(i, 3)) {
				count++;
			}
			if (count == 2023) {
				System.out.println(i);
				break;
			}
		}
	}

	private static boolean isHasa(int num, int jinzhi) {
		int s = 0;
		// 二进制
		if (jinzhi == 0) {
			String binary = Integer.toBinaryString(num);
			for (int i = 0; i < binary.length(); i++) {
				s += Integer.parseInt(binary.charAt(i) + "");
			}
			// 八进制
		} else if (jinzhi == 1) {
			String octal = Integer.toOctalString(num);
			for (int i = 0; i < octal.length(); i++) {
				s += Integer.parseInt(octal.charAt(i) + "");
			}
			// 十进制
		} else if (jinzhi == 2) {
			int temp = num;
			while (temp != 0) {
				s += temp % 10;
				temp /= 10;
			}
			// 十六进制
		} else {
			String hex = Integer.toHexString(num);
			for (int i = 0; i < hex.length(); i++) {
				if (hex.charAt(i) == 'f') {
					s += 15;
				} else if (hex.charAt(i) == 'e') {
					s += 14;
				} else if (hex.charAt(i) == 'd') {
					s += 13;
				} else if (hex.charAt(i) == 'c') {
					s += 12;
				} else if (hex.charAt(i) == 'b') {
					s += 11;
				} else if (hex.charAt(i) == 'a') {
					s += 10;
				} else {
					s += Integer.parseInt(hex.charAt(i) + "");
				}
			}
		}
		return num % s == 0;
	}
}

优秀题解

java 复制代码
public class Main {
    public static void main(String[] args) {
        int i = 1, count = 0;
        while (true) {
            if (isHaSa(i, 2) && isHaSa(i, 8) && isHaSa(i, 10) && isHaSa(i, 16)) {
                count++;
            }
            // 输出第 2023 个幸运数字
            if (count == 2023) {
                System.out.println(i);
                break;
            }
            i++;
        }
    }

    /**
     * 判断是否是哈沙德数
     *
     * @param n   十进制位的数
     * @param mod 模(进制位)
     * @return 是否是哈沙德数
     */
    public static boolean isHaSa(int n, int mod) {
        int num = n, sum = 0;
        while (n != 0) {
            // 累加n上各个位的数之和
            sum += n % mod;
            n = n / mod;
        }
        // 126 % (1+2+6)
        return num % sum == 0;
    }
}

试题 C: 数组分割【编程题】

时间限制: 2.0s 内存限制: 512.0MB 本题总分:10 分

【问题描述】
小蓝有一个长度为 N{N} 的数组 A=[A0,A1,...,AN−1]{A=[A_0,A_1,...,A_{N-1}]}。现在小蓝想要从 A{A} 对应的数组下标所构成的集合 I={0,1,2,...,N−1}{I =\{0, 1, 2, . . . , N-1\}} 中找出一个子集 R1{R_1},那么 R1{R_1} 在 I 中的补集为 R2{R_2}。记 S1=Σr∈R1Ar{S_1=\Sigma_{r\in R1}Ar},S2=Σr∈R2Ar{S_2=\Sigma_{r\in R2}Ar},我们要求 S1{S_1} 和 S2{S_2} 均为 偶数,请问在这种情况下共有多少种不同的 R1{R_1}。当 R1{R_1} 或 R2{R_2} 为空集时我们将S1{S_1} 或 S2{S_2} 视为 0。

【输入格式】
第一行一个整数 T{T},表示有 T{T} 组数据。 接下来输入 T{T} 组数据,每组数据包含两行:第一行一个整数 N{N},表示数组 A{A} 的长度;第二行输入 N{N} 个整数从左至右依次为 A0,A1,...,AN−1{A_0,A_1,...,A_{N-1}},相邻元素之间用空格分隔。

【输出格式】
对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你 需要将答案对 1000000007 进行取模后输出。

【样例输入】

sh 复制代码
2
2
6 6
2
1 6

【样例输出】

sh 复制代码
4
0

【样例说明】
对于第一组数据,答案为 4。(注意:大括号内的数字表示元素在数组中的 下标。)
R1={0},R2={1}{R_1 = \{0\}, R_2 = \{1\}};此时 S1=A0=6{S_1 = A_0 = 6} 为偶数, S2=A1=6{S_2 = A_1 = 6} 为偶数。
R1={1},R2={0}{R_1 = \{1\}, R_2 = \{0\}};此时 S1=A1=6{S_1 = A_1 = 6} 为偶数, S2=A0=6{S_2 = A_0 = 6} 为偶数。
R1={0,1},R2={}{R_1 = \{0, 1\}, R_2 = \{\}};此时 S1=A0+A1=12{S_1 = A_0 + A_1 = 12} 为偶数, S2=0{S_2 = 0} 为偶数。
R1={},R2={0,1}{R_1 = \{\}, R_2 = \{0, 1\}};此时 S1=0{S_1 = 0} 为偶数, S2=A0+A1=12{S_2 = A_0 + A_1 = 12} 为偶数。 对于第二组数据,无论怎么选择,都不满足条件,所以答案为 0。

【评测用例规模与约定】
对于 20% 的评测用例,1≤N≤10{1\leq N \leq 10}。
对于 40% 的评测用例,1≤N≤102{1\leq N \leq 10^2}。
对于 100% 的评测用例,1≤T≤10,1≤N≤103,0≤Ai≤109{1\leq T\leq 10, 1 \leq N \leq 10^3, 0\leq A_i \leq10^9}。

解法

我的题解

题目要求,从数组 AA 的下标所构成的集合 II 从找出一个子集 R1R_1,R1R_1 的和 S1S_1 为偶数,补集 R2R_2 的和 S2S_2 也为偶数。

那我们想想和为偶数的几种加法情况:

  1. 偶数与偶数相加为偶数
  2. 奇数与奇数相加为偶数
  3. 奇数与偶数相加为奇数

故决定我们集合中的和能否为偶数的因素为奇数的个数,我们可以先找出数组 A 中奇数的有多少个。

  • 如果为奇数个,则无论怎样组合都无法满足有两个集合中元素和为偶数的情况,故为 00 种情况。
  • 如果为偶数个,说明是可以组合成两个和为偶数的集合的。偶数个奇数与偶数相加的情况。奇数需要选择两个才能组合成偶数,假设奇数的个数为 mm 个,则 偶数的个数为 n−mn-m,那么奇数组合成偶数的情况为 2m−12^{m-1},偶数的组合情况为 2n−m2^{n-m},那么奇数与偶数一起组合的情况为 2m−1+n−m=2n−12^{m-1+n-m}=2^{n-1}。
  • 如果为 00 个,则说明数组里面的集合都是偶数,那对于每个偶数,它有两种组合情况,选择它,或者不选择它,有 nn 个偶数,则有 2n2^n 种情况。

注意这里要使用 BigInteger,数据量大,保险些。

java 复制代码
import java.util.*;
import java.math.*;

// 数组分割
public class Main {

	static BigInteger BIG_TWO = new BigInteger("2");
	static BigInteger BIG_MOD = new BigInteger("1000000007");

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			// 题目要求从数组A中找出一个子集R1,要让子集R1中元素的和为偶数
			// 补集R2中元素的和也要为偶数,也就是剩余元素的和为偶数
			// 要让数加起来为偶数,需要注意分几种情况
			// 1.偶数与偶数相加为偶数
			// 2.奇数与奇数相加为偶数(偶数个奇数相加为偶数)
			// 3.一个奇数与一个偶数相加为奇数
			int n = sc.nextInt();
			int[] a = new int[n];
			int ans = 0; // 统计奇数个数
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				if (a[i] % 2 != 0) {
					ans++;
				}
			}
			// 如果数组奇数的个数为奇数,说明怎么凑都没法分成两个和为偶数的集合
			if ((ans & 1) == 1) {
				System.out.println(0);
				continue;
			}
			// 如果小组中没有奇数,都为偶数,则可能得组合情况为 n 的平方
			if (ans == 0) {
				System.out.println(BIG_TWO.pow(n).mod(BIG_MOD));
				continue;
			}
			// 剩下的就是偶数个奇数与偶数的组合,由于奇数需要占两个,故最终减去1
			System.out.println(BIG_TWO.pow(n - 1).mod(BIG_MOD));
		}
	}
}

试题 D: 矩形总面积【编程题】

时间限制: 2.0s 内存限制: 512.0MB 本题总分:10 分

【问题描述】
平面上有个两个矩形 R1 和 R2,它们各边都与坐标轴平行。设 (x1, y1) 和(x2, y2) 依次是 R1 的左下角和右上角坐标,(x3, y3) 和 (x4, y4) 依次是 R2 的左下 角和右上角坐标,请你计算 R1 和 R2 的总面积是多少?
注意:如果 R1 和 R2 有重叠区域,重叠区域的面积只计算一次。

【输入格式】
输入只有一行,包含 8 个整数,依次是:x1,y1,x2,y2,x3,y3,x4 和 y4。

【输出格式】
一个整数,代表答案。

【样例输入】
2 1 7 4 5 3 8 6

【样例输出】
22

【样例说明】
样例中的两个矩形如图所示:
image.png

【评测用例规模与约定】
对于 20% 的数据,R1 和 R2 没有重叠区域。
对于 20% 的数据,其中一个矩形完全在另一个矩形内部。
对于 50% 的数据,所有坐标的取值范围是 [0,103]{[0,10^3]}。
对于 100% 的数据,所有坐标的取值范围是 [0,105]{[0,10^5]}。

解法

思路:计算合并的面积,我们可以先计算出两个矩形的面积和,接着算出他们重叠的部分,然后去除即可。重叠部分,我们可以将找出最小右上角的坐标的x,y,与最大左下角的坐标x,y,进行相减,如果x与y轴的坐标差都大于0,表示他们有重叠。

java 复制代码
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt(), y1 = sc.nextInt();
        int x2 = sc.nextInt(), y2 = sc.nextInt();
        int x3 = sc.nextInt(), y3 = sc.nextInt();
        int x4 = sc.nextInt(), y4 = sc.nextInt();
        // 计算两个矩形的面积和(这里用long)
        long area = (long) (x2 - x1) * (y2 - y1) + (long) (x4 - x3) * (y4 - y3);
        // 判断是否有重复部分
        // 得出宽重叠的部分  找出最大左下角下标的x值,与最小右上角下标的x值,两者之差即为重叠的宽
        int overlapWidth = Math.min(x2, x4) - Math.max(x1, x3);
        // 得出高重叠的部分  找出最大左下角下标的y值,与最小右上角下标的y值,两者之差即为重叠的高度
        int overlapHeight = Math.min(y2, y4) - Math.max(y1, y3);
        if (overlapWidth > 0 && overlapHeight > 0) {
            area -= (long) overlapWidth * overlapHeight;
        }
        System.out.println(area);
    }
}

试题 E: 蜗牛【编程题】

时间限制: 2.0s 内存限制: 512.0MB 本题总分:15 分

【问题描述】
这天,一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴,底部纵坐标为 0,横坐标分别 为 x1, x2, …, xn。竹竿的高度均为无限高,宽度可忽略。蜗牛想要从原点走到第n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x 轴上或者竹竿上爬行,在 x 轴 上爬行速度为 1 单位每秒;由于受到引力影响,蜗牛在竹竿上向上和向下爬行 的速度分别为 0.7 单位每秒和 1.3 单位每秒。 为了快速到达目的地,它施展了魔法,在第 i 和 i + 1 根竹竿之间建立了传 送门(0 < i < n),如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai),就可以 瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1),请计算蜗牛最少需要 多少秒才能到达目的地。

【输入格式】
输入共 1 + n 行,第一行为一个正整数 n; 第二行为 n 个正整数 x1, x2, . . . , xn; 后面 n − 1 行,每行两个正整数 ai , bi+1。

【输出格式】
输出共一行,一个浮点数表示答案(四舍五入保留两位小数)。

【样例输入】
3
1 10 11
1 1
2 1

【样例输出】
4.20

【样例说明】
蜗牛路线:
(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0),花费时间为 1 + 1 /0.7 + 0 + 1 /1.3 + 1 ≈ 4.20

【评测用例规模与约定】
对于 20% 的数据,保证 n≤15{n\leq15};
对于 100% 的数据,保证 n≤105,ai,bi≤104,xi≤109{n\leq10^5, a_i,b_i \leq10^4, x_i\leq10^9}。

解法

我的解法

这题的话,我们可以先找出走到当前这一个竹竿的最优解,那要去下一个竹竿则可以利用这个最优解选择合适的路线到达,从而减少所花的时间。

故我们可以用动态规划来解决。这里设 dp[i][]dp[i][]: dp[i][0]dp[i][0] 表示去竹竿底部的最短距离,dp[i][1]dp[i][1] 表示去当前这个竹竿传送门起点的最短距离。

我们给两个初始状态。

  • dp[1][0]dp[1][0]:表示从起点 0 到达第 11 个竹竿底部的最短时间
  • dp[1][1]dp[1][1]: 表示从起点 0 到第 11 个竹竿的传送门起点的最短时间

接着我们找出要去下一个竹竿,要考虑的情况:

  • 如何前往要去下一个传送门的起点位置:
    1. 我们可以从上一个传送门到达这个竹竿的传送门,再走去要去下一个竹竿的传送门起点
    2. 也可以从竹竿底部往上爬到传送门的起点
  • 如何到达下一个竹竿的底部:
    1. 从上一个竹竿底部爬到这个竹竿底部
    2. 从上一个竹竿通过传送门传送到这个竹竿的终点位置,往下爬

可以浅浅看下图,想象一下:
image.png

下边是代码实现

java 复制代码
import java.util.*;

// 蜗牛
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] x = new int[n + 1];

		// 存放竹竿的 x 坐标
		for (int i = 1; i <= n; i++) {
			x[i] = sc.nextInt();
		}

		// 传送门起点,这个竹竿要传送到下一个竹竿的起点位置
		int[] a = new int[n + 1];
		// 传送门终点,从上一个竹竿到这一个竹竿的终点位置
		int[] b = new int[n + 1];

		// 存放传送门的位置
		for (int i = 1; i < n; i++) {
			a[i] = sc.nextInt();
			b[i + 1] = sc.nextInt();
		}

		double[][] dp = new double[n + 1][2];
		// 初始状态
		dp[1][0] = x[1]; // dp[i][0] 表示从起点 0 到达第 i 个竹竿底部的最短时间
		dp[1][1] = x[1] + a[1] / 0.7; // dp[i][1] 表示从起点 0 到第 i 个竹竿的传送门的最短时间

		// 计算出到达每个点的最短距离
		for (int i = 2; i <= n; i++) {
			// 看看我们要上升还是下降
			if (b[i] > a[i]) {
				// 从到达上一个竹竿底部最短距离 + 上一个竹竿到这个竹竿底部的距离,再往上爬到 要去下一个竹竿的传送门起点
				double dist1 = dp[i - 1][0] + (x[i] - x[i - 1]) + a[i] / 0.7;
				// 下降,从上一个竹竿到这个竹竿的传送门的位置,开始前往要去下一个竹竿的传送门的位置
				double dist2 = dp[i - 1][1] + (b[i] - a[i]) / 1.3;
				// 看这两种走法哪种时间更短
				dp[i][1] = Math.min(dist1, dist2);
			} else {
				// 从到达上一个竹竿底部最短距离 + 上一个竹竿到这个竹竿底部的距离,再往上爬到 要去下一个竹竿的起点
				double dist1 = dp[i - 1][0] + (x[i] - x[i - 1]) + a[i] / 0.7;
				// 上升,从上一个竹竿到这个竹竿的传送门的位置,开始前往要去下一个竹竿的传送门的位置
				double dist2 = dp[i - 1][1] + (a[i] - b[i]) / 0.7;
				dp[i][1] = Math.min(dist1, dist2);
			}
			// 从上一次到竹竿底部的最短距离走到这里,或者从这个竹竿的传送门走到底部,看看哪个快
			dp[i][0] = Math.min(dp[i - 1][0] + (x[i] - x[i - 1]), dp[i - 1][1] + b[i] / 1.3);
		}

		System.out.printf("%.2f", dp[n][0]);

	}
}

试题 F: 合并区域【编程题】

时间限制: 2.0s 内存限制: 512.0MB 本题总分:15 分

【问题描述】
小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 N×NN \times N 的正方形 区域。这两块区域都按照 N×NN \times N 的规格进行了均等划分,划分成了若干块面积 相同的小区域,其中每块小区域要么是岩石,要么就是土壤,在垂直或者水平 方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进 行合并,他想知道合并以后可以得到的最大的一块土地的面积是多少(土地的 面积就是土地中土壤小区域的块数)?

在进行合并时,小区域之间必须对齐。可以在两块方形区域的任何一条边 上进行合并,可以对两块方形区域进行 9090 度、180180 度、270270 度、360360 度的旋转, 但不可以进行上下或左右翻转,并且两块方形区域不可以发生重叠。

【输入格式】
第一行一个整数 NN 表示区域大小。

接下来 NN 行表示第一块区域,每行 NN 个值为 00 或 11 的整数,相邻的整数之间用空格进行分隔。值为 00 表示这块小区域是岩石,值为 11 表示这块小区域是土壤。

再接下来 NN 行表示第二块区域,每行 NN 个值为 00 或 11 的整数,相邻的整数之间用空格进行分隔。值为 00 表示这块小区域是岩石,值为 11 表示这块小区域是土壤。

【输出格式】
一个整数表示将两块区域合并之后可以产生的最大的土地面积。

【样例输入】

sh 复制代码
4
0 1 1 0
1 0 1 1
1 0 1 0
1 1 1 0
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1

【样例输出】

sh 复制代码
15

【样例说明】
image.png

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳 的合并方式,此时最大的土地面积为 1515。

【评测用例规模与约定】
对于 30% 的数据,1≤N≤51 \leq N \leq 5。
对于 60% 的数据,1≤N≤151 \leq N \leq 15。
对于 100% 的数据,1≤N≤501 \leq N \leq 50。

解法

我的解法

思路是先找出每个区域边缘的是否有土壤,有土壤,说明可以连接,没有的话说明都没法与其他区域的土壤合并连成一片。

接着对有边缘的土壤进行搜索,找出连接的土壤能最大的情况。

最后,根据两个边缘是否有土壤来进行相加或者两者中的最大值。

但只跑通了几个样例。。。。

java 复制代码
import java.util.Scanner;

public class Test5 {

	static int[][] graph1 = new int[52][52];
	static boolean[][] vis1 = new boolean[52][52];
	static int s1 = 0;
	static int[][] graph2 = new int[52][52];
	static boolean[][] vis2 = new boolean[52][52];
	static int s2 = 0;

	static int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static int n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		// 第一块区域
		// 找出区域边是否有入口
		boolean flag1 = false;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph1[i][j] = sc.nextInt();
				// 如果是土地
				if ((i == 1 || i == n || j == 1 || j == n) && graph1[i][j] == 1) {
					flag1 = true;
				}
			}
		}
		// 第二块区域
		// 找出区域边是否有入口
		boolean flag2 = false;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph2[i][j] = sc.nextInt();
				// 如果是土地
				if ((i == 1 || i == n || j == 1 || j == n) && graph2[i][j] == 1) {
					flag2 = true;
				}
			}
		}

		if (flag1) {
			for (int i = 1; i <= n; i++) {
				int startX = 1, startY = i;
				if (graph1[startX][startX] == 1) {
					vis1[startX][startY] = true;
					dfs1(startX, startY, 1);
					vis1[startX][startY] = false;
				}
				startX = n;
				startY = i;
				if (graph1[startX][startX] == 1) {
					vis1[startX][startY] = true;
					dfs1(startX, startY, 1);
					vis1[startX][startY] = false;
				}
				startX = i;
				startY = 1;
				if (graph1[startX][startX] == 1) {
					vis1[startX][startY] = true;
					dfs1(startX, startY, 1);
					vis1[startX][startY] = false;
				}
				startX = i;
				startY = n;
				if (graph1[startX][startX] == 1) {
					vis1[startX][startY] = true;
					dfs1(startX, startY, 1);
					vis1[startX][startY] = false;
				}
			}
		}
		if (flag2) {
			for (int i = 1; i <= n; i++) {
				int startX = 1, startY = i;
				if (graph2[startX][startX] == 1) {
					vis2[startX][startY] = true;
					dfs2(startX, startY, 1);
					vis2[startX][startY] = false;
				}
				startX = n;
				startY = i;
				if (graph2[startX][startX] == 1) {
					vis2[startX][startY] = true;
					dfs2(startX, startY, 1);
					vis2[startX][startY] = false;
				}
				startX = i;
				startY = 1;
				if (graph2[startX][startX] == 1) {
					vis2[startX][startY] = true;
					dfs2(startX, startY, 1);
					vis2[startX][startY] = false;
				}
				startX = i;
				startY = n;
				if (graph2[startX][startX] == 1) {
					vis2[startX][startY] = true;
					dfs2(startX, startY, 1);
					vis2[startX][startY] = false;
				}
			}
		}
		// 如果两个区域都有入口
		if (flag1 && flag2) {
			System.out.print(s1 + s2);
		} else {
			// 有区域没有入口,则找出最大的面积
			System.out.print(Math.max(s1, s2));
		}
	}

	private static boolean pd1(int nextX, int nextY) {
		if (nextX > n || nextX < 1 || nextY > n || nextY < 1 || vis1[nextX][nextY]) {
			return false;
		}
		return true;
	}

	private static void dfs1(int startX, int startY, int s) {
		if (graph1[startX][startY] == 0) {
			s1 = Math.max(s1, s);
			return;
		}
		// 尝试四个方向
		for (int i = 0; i < 4; i++) {
			int nextX = startX + direction[i][0];
			int nextY = startY + direction[i][1];
			if (pd1(nextX, nextY)) {
				vis1[nextX][nextY] = true;
				dfs1(nextX, nextY, s + 1);
				vis1[nextX][nextY] = false;
			}
		}
	}

	private static boolean pd2(int nextX, int nextY) {
		if (nextX > n || nextX < 1 || nextY > n || nextY < 1 || vis2[nextX][nextY]) {
			return false;
		}
		return true;
	}

	private static void dfs2(int startX, int startY, int s) {
		if (graph2[startX][startY] == 0) {
			s2 = Math.max(s2, s);
			return;
		}
		// 尝试四个方向
		for (int i = 0; i < 4; i++) {
			int nextX = startX + direction[i][0];
			int nextY = startY + direction[i][1];
			if (pd2(nextX, nextY)) {
				vis2[nextX][nextY] = true;
				dfs2(nextX, nextY, s + 1);
				vis2[nextX][nextY] = false;
			}
		}
	}
}
image.png

优秀题解

试题 G: 买二赠一【编程题】

时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分

【问题描述】
某商场有 NN 件商品,其中第 ii 件的价格是 AiA_i。现在该商场正在进行 “买二 赠一” 的优惠活动,具体规则是: 每购买 22 件商品,假设其中较便宜的价格是 PP(如果两件商品价格一样, 则 PP 等于其中一件商品的价格),就可以从剩余商品中任选一件价格不超过 P2\frac{P}{2} 的商品,免费获得这一件商品。可以通过反复购买 22 件商品来获得多件免费商品,但是每件商品只能被购买或免费获得一次。

小明想知道如果要拿下所有商品(包含购买和免费获得),至少要花费多少钱?

【输入格式】
第一行包含一个整数 NN。 第二行包含 NN 个整数,代表 A1,A2,A3,...,ANA_1,A_2, A_3, . . . ,A_N。

【输出格式】
输出一个整数,代表答案。

【样例输入】

sh 复制代码
7
1 4 2 8 5 7 1

【样例输出】

sh 复制代码
25

【样例说明】
小明可以先购买价格 44 和 88 的商品,免费获得一件价格为 11 的商品;再后 买价格为 55 和 77 的商品,免费获得价格为 22 的商品;最后单独购买剩下的一件 价格为 11 的商品。总计花费 4+8+5+7+1=254 + 8 + 5 + 7 + 1 = 25。不存在花费更低的方案。

【评测用例规模与约定】
对于 30% 的数据,1 ≤ N ≤ 20。 对于 100% 的数据,1 ≤ N ≤ 5 × 10^5,1 ≤ Ai ≤10^9 。

解法

我的题解

我的思路是贪心的想法,既然要使花的少,那就每次选价格大的,那能免费得到的商品的价格就会大一些,我使用题目给的测试样例跑过了,但发上去没一个跑通。。。

java 复制代码
import java.util.*;

public class Main {

	static long[] goods;

	static long[] types; // 存放这种类型的商品数量

	static long cnt;

	private static void insert(int type) {
		if (types[type] == 0) {
			cnt++; // 累计购买的种类数
		}
		types[type]++;
	}

	private static void delete(int type) {
		if (types[type] == 1) {
			cnt--; // 减去购买的种类数
		}
		types[type]--;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		goods = new long[n + 1];

		for (int i = 1; i <= n; i++) {
			goods[i] = sc.nextInt();
		}
		// 从小到大价格排序
		Arrays.sort(goods);

		types = new long[n + 1];

		// 每件商品只有1件
		Arrays.fill(types, 1);
		// 花费的钱
		int sum = 0;

		for (int i = n; i > 1; i--) {
			long a = types[i]; // 商品余量
			long b = types[i - 1]; // 商品余量
			if (a == 0 || b == 0) {
				continue;
			}
			types[i]--;
			types[i - 1]--;
			sum += goods[i] + goods[i - 1];
			cnt += 2;
			// b的价格肯定少
			// 从剩余商品中,找出价格小于 b/2的
			for (int j = i - 2; i >= 1; j--) {
				if (types[j] == 1 && goods[j] <= goods[i - 1] / 2) {
					types[j]--;
					cnt += 1;
					break;
				}
			}
			if (cnt == n) {
				break;
			}
		}
		if (cnt < n) {
			sum += goods[1];
		}
		System.out.print(sum);
	}
}

优秀题解

看到别人的思路,其实都是差不多的,不过他是用了队列来处理。我可能是在处理免费商品的地方没有处理好。我使用队列来处理,就跑通了。

java 复制代码
import java.util.*;

// 买二赠一
public class Test6 {

	static long[] goods;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		goods = new long[n + 1];

		for (int i = 1; i <= n; i++) {
			goods[i] = sc.nextInt();
		}
		// 从小到大价格排序
		Arrays.sort(goods);

		// 花费的钱
		long sum = 0;
		// 把要处理的免费商品价格放入队列
		Queue<Long> free = new LinkedList<>();
		int i = n; // 先选最后一件商品
		while (i > 0) {
			// 如果当前有未被处理的免费商品,我们先处理下,避免重复处理
			while (!free.isEmpty() && i > 0) {
				// 找出需要处理的商品
				// 该商品如果满足免费条件
				if (free.peek() >= goods[i]) {
					i--;
					free.poll();
				} else {
					// 当前商品的价格大于免费条件,则继续先选择购买商品
					break;
				}
			}
			// 看看还有没有商品可选,有的话先选一件商品
			if (i > 0) {
				sum += goods[i];
				i--;
			}

			// 再看看当前商品是否满足免费条件
			while (!free.isEmpty() && i > 0) {
				if (free.peek() >= goods[i]) {
					i--;
					free.poll();
				} else {
					break;
				}
			}
			// 看看还有没有商品可选,有的话,再选另一件商品
			if (i > 0) {
				sum += goods[i];
				// 当前这件商品肯定比上一件商品的价格小
				// 把能获得免费的最大价格放入集合中
				free.add(goods[i] / 2);
				i--;
			}

		}

		System.out.print(sum);
	}
}
image.png

试题 H: 合并石子【编程题】

试题 I: 最大开支【编程题】

【问题描述】
小蓝所在学校周边新开业了一家游乐园,小蓝作为班长,打算组织大家去 游乐园玩。已知一共有 NN 个人参加这次活动,游乐园有 MM 个娱乐项目,每个 项目都需要买门票后才可进去游玩。门票的价格并不是固定的,团购的人越多 单价越便宜,当团购的人数大于某个阈值时,这些团购的人便可以免费进入项 目进行游玩。这 MM 个娱乐项目是独立的,所以只有选择了同一个项目的人才可以参与这个项目的团购。第 ii 个项目的门票价格 Hi(X)H_i(X) 与团购的人数 XX 的关系可 以看作是一个函数:

Hi(X)=max(Ki×X+Bi,0)H_i(X) = max(K_i \times X + B_i , 0)

其中 maxmax 表示取二者之中的最大值。当 Hi=0H_i = 0 时说明团购人数达到了此项目的免单阈值。 这 NN 个人可以根据自己的喜好选择 MM 个娱乐项目中的一种,或者有些人 对这些娱乐项目都没有兴趣,也可以选择不去任何一个项目。每个人最多只会 选择一个娱乐项目,如果多个人选择了同一个娱乐项目,那么他们都将享受对 应的团购价格。小蓝想知道他至少需要准备多少钱,使得无论大家如何选择, 他都有能力支付得起所有 NN 个人购买娱乐项目的门票钱。

【输入格式】
第一行两个整数 NN、MM,分别表示参加活动的人数和娱乐项目的个数。 接下来 MM 行,每行两个整数,其中第 ii 行为 KiK_i、BiB_i,表示第 ii 个游乐地点 的门票函数中的参数。

【输出格式】
一个整数,表示小蓝至少需要准备多少钱,使得大家无论如何选择项目, 自己都支付得起。

【样例输入】

sh 复制代码
4 2
-4 10
-2 7

【样例输出】

sh 复制代码
12

【样例说明】
样例中有 4 个人,2 个娱乐项目,我们用一个二元组 (a, b) 表示 a 个人选 择了第一个娱乐项目,b 个人选择了第二个娱乐项目,那么就有 4 − a − b 个 人没有选择任何项目,方案 (a, b) 对应的门票花费为 max(−4 × a + 10, 0) × a + max(−2 × b + 7, 0) × b,所有的可能如下所示:

a b 花费
0 0 0
0 1 5
0 2 6
0 3 3
0 4 0
1 0 6
1 1 11
1 2 12
1 3 9
2 0 4
2 1 9
2 2 10
3 0 0
3 1 5
4 0 0
其中当 a=1,b=2a = 1, b = 2 时花费最大,为 1212。此时 11 个人去第一个项目,所以第一个项目的单价为 10−4=610 - 4 = 6,在这个项目上的花费为 6×1=66 \times 1 = 6;22 个人去 第二个项目,所以第二个项目得单价为 7−2×2=37 - 2 \times 2 = 3,在这个项目上的花费为 2×3=62 \times 3 = 6;还有 11 个人没去任何项目,不用统计;总花费为 1212,这是花费最大的一种方案,所以答案为 1212。

【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ N, M ≤ 10。
对于 50% 的评测用例,1 ≤ N, M ≤ 1000。
对于 100% 的评测用例,1 ≤ N, M, Bi ≤ 10^5,− 10^5≤ Ki < 0。

试题 J: 魔法阵【编程题】

【问题描述】
魔法师小蓝为了营救自己的朋友小 QQ;来到了敌人 置的魔法阵。魔法阵可以看作是一幅具有 NN 个结点 MM 条边的无向图,结点编号为 0,1,2,⋯ ,N−10,1,2,\cdots,N-1,图中没有重边和自环。敌人在每条边上都布置了陷阱,每条边都有一个伤害属性 ww,每当小蓝经过一条边时就会受到这条边对应的 ww 的伤害。小蓝从结点 00 出发,沿着边行走,想要到达结点 N−1N-1 营敷小 QQ。

小蓝有一种特殊的魔法可以使用,假设一条路径按照顺序依次经过了以下 LL 条边:e1,e2,\codts,eLe_1,e_2,\codts,e_L(可以出现重复的边),那么期间小
蓝愛到的总伤害就是 P=∑i=1Lw(ei),w(ei)P=\sum\limits_{i=1}^L w(e_i),w(e_i) 表示边 eie_i 的伤害属性。如果 L≥KL\ge K,那么小蓝就可以从这 LL 条边当中选出连续出现的 KK 条边 ec,ec+1,...,ec+K−1e_c , e_{c+1}, . . . ,e_{c+K-1} 并免去在这 KK 条边行 走期间所受到的伤害,即使用魔法之后路径总伤害变为 P′=P−∑i=cc+K−1w(ei)P'=P-\sum\limits_{i=c}^{c+K-1} w(e_i)。注意必须恰好选出连续出现的 KK 条边,所以当 L<KL < K 时无法使用魔法。

小蓝最多只可以使用一次上述的魔法,请问从结点 00 出发到结点 N−1N − 1 受到的最小伤害是多少?题目保证至少存在一条从结点 00 到 N−1N − 1 的路径。

【输入格式】
第一行输入三个整数,N,K,MN, K, M,用空格分隔。 接下来 MM 行,每行包含三个整数 u,v,wu,v,w,表示结点 uu 与结点 vv 之间存在一条伤害属性为 ww 的无向边。

【输出格式】
输出一行,包含一个整数,表示小蓝从结点 00 到结点 N−1N - 1 受到的最小伤害。

【样例输入 1】
4 2 3
0 1 2
1 2 1
2 3 4

【样例输出 1】
2

【样例输入 2】
2 5 1
0 1 1

【样例输出 2】
0

【样例说明】
样例 11,存在路径:0 → 1 → 2 → 3,K = 2,如果在 0 → 1 → 2 上使用魔 法,那么答案就是 0 + 0 + 4 = 4;如果在 1 → 2 → 3 上使用魔法,那么答案就 是 2 + 0 + 0 = 2。再也找不到比 2 还小的答案了,所以答案就是 2。

样例 22,存在路径:0 → 1 → 0 → 1 → 0 → 1,K = 5,这条路径总计恰好 走了 5 条边,所以正好可以用魔法消除所有伤害,答案是 0。

【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ N ≤ 20。
对于 50% 的评测用例,1 ≤ N ≤ 100。
对于 100% 的评测用例,1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N−1)/2 ,1 ≤ K ≤ 10, 0 ≤ u, v ≤ N − 1,1 ≤ w ≤ 1000。

解法

我的题解

一开始想着先用迪杰斯特拉,找出起点到每个点的最小单源路径,之后回溯出这最小路径。根据这个路径,找出连续边数>K的且伤害大的,那就在这段取余使用魔法,测试样例跑通了,但发上去一个没跑通。。。据说这题是去年最难的题之一。。。

java 复制代码
import java.util.*;

// 魔法阵
public class Test9 {

	private static class Edge {
		int from;
		int to;
		int w;

		Edge(int from, int to, int w) {
			this.from = from;
			this.to = to;
			this.w = w;
		}

	}

	private static class SNode implements Comparable<SNode> {
		int id;
		int n_dist;

		SNode(int id, int n_dist) {
			this.id = id;
			this.n_dist = n_dist;
		}

		@Override
		public int compareTo(SNode o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.n_dist, o.n_dist);
		}
	}

	static final int N = 1010;
	static int[] father = new int[N];
	static ArrayList<Edge>[] e = new ArrayList[N]; // 存储边
	static int[] dist = new int[N];
	static final int INF = 0x3f3f3f3f;
	static boolean[] vis = new boolean[N];

	static Vector<Integer> vectors = new Vector<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = sc.nextInt();

		for (int i = 0; i < n; i++) {
			e[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			// 无向边
			e[u].add(new Edge(u, v, w));
			e[v].add(new Edge(v, u, w));
		}
		// 先求出起点到每个点的最短单源路径
		dijkstra(0);

//		System.out.print(dist[n - 1]);

		getPath(0, n - 1);
//		System.out.print(vectors);
		// 当前的边数够减
		if (vectors.size() - 1 >= k) {
			int max = 0; // 找出路径权值最大的部分
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < k; j++) {
					if (i + k >= n) {
						break;
					}
					max = Math.max(max, dist[i + k] - dist[i]);
				}
			}
			System.out.print(dist[n - 1] - max);
		} else {
			System.out.print(dist[n - 1]);
		}
	}

	private static void getPath(int start, int n) {
		if (n == start) {
			vectors.add(n);
			return;
		}
		getPath(start, father[n]);
		vectors.add(n);
	}

	private static void dijkstra(int start) {
		Arrays.fill(dist, INF);
		dist[start] = 0;

		PriorityQueue<SNode> queue = new PriorityQueue<>();
		queue.add(new SNode(start, 0));

		while (!queue.isEmpty()) {
			SNode node = queue.poll();
			if (vis[node.id]) {
				continue;
			}
			vis[node.id] = true;
			// 访问邻接点
			for (Edge edge : e[node.id]) {
				if (dist[edge.to] > node.n_dist + edge.w) {
					dist[edge.to] = node.n_dist + edge.w;
					queue.add(new SNode(edge.to, dist[edge.to]));
					father[edge.to] = node.id;
				}
			}
		}
	}
}
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句