2023年第十四届蓝桥杯省赛真题(Java B组)
本文详细解析了 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 分
【问题描述】
小蓝有一个长度为 的数组 。现在小蓝想要从 对应的数组下标所构成的集合 中找出一个子集 ,那么 在 I 中的补集为 。记 ,,我们要求 和 均为 偶数,请问在这种情况下共有多少种不同的 。当 或 为空集时我们将 或 视为 0。
【输入格式】
第一行一个整数 ,表示有 组数据。 接下来输入 组数据,每组数据包含两行:第一行一个整数 ,表示数组 的长度;第二行输入 个整数从左至右依次为 ,相邻元素之间用空格分隔。
【输出格式】
对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你 需要将答案对 1000000007 进行取模后输出。
【样例输入】
sh2 2 6 6 2 1 6【样例输出】
sh4 0【样例说明】
对于第一组数据,答案为 4。(注意:大括号内的数字表示元素在数组中的 下标。)
;此时 为偶数, 为偶数。
;此时 为偶数, 为偶数。
;此时 为偶数, 为偶数。
;此时 为偶数, 为偶数。 对于第二组数据,无论怎么选择,都不满足条件,所以答案为 0。
【评测用例规模与约定】
对于 20% 的评测用例,。
对于 40% 的评测用例,。
对于 100% 的评测用例,。
解法
我的题解
题目要求,从数组 的下标所构成的集合 从找出一个子集 , 的和 为偶数,补集 的和 也为偶数。
那我们想想和为偶数的几种加法情况:
- 偶数与偶数相加为偶数
- 奇数与奇数相加为偶数
- 奇数与偶数相加为奇数
故决定我们集合中的和能否为偶数的因素为奇数的个数,我们可以先找出数组 A 中奇数的有多少个。
- 如果为奇数个,则无论怎样组合都无法满足有两个集合中元素和为偶数的情况,故为 种情况。
- 如果为偶数个,说明是可以组合成两个和为偶数的集合的。偶数个奇数与偶数相加的情况。奇数需要选择两个才能组合成偶数,假设奇数的个数为 个,则 偶数的个数为 ,那么奇数组合成偶数的情况为 ,偶数的组合情况为 ,那么奇数与偶数一起组合的情况为 。
- 如果为 个,则说明数组里面的集合都是偶数,那对于每个偶数,它有两种组合情况,选择它,或者不选择它,有 个偶数,则有 种情况。
注意这里要使用 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
【样例说明】
样例中的两个矩形如图所示:
【评测用例规模与约定】
对于 20% 的数据,R1 和 R2 没有重叠区域。
对于 20% 的数据,其中一个矩形完全在另一个矩形内部。
对于 50% 的数据,所有坐标的取值范围是 。
对于 100% 的数据,所有坐标的取值范围是 。
解法
思路:计算合并的面积,我们可以先计算出两个矩形的面积和,接着算出他们重叠的部分,然后去除即可。重叠部分,我们可以将找出最小右上角的坐标的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% 的数据,保证 ;
对于 100% 的数据,保证 。
解法
我的解法
这题的话,我们可以先找出走到当前这一个竹竿的最优解,那要去下一个竹竿则可以利用这个最优解选择合适的路线到达,从而减少所花的时间。
故我们可以用动态规划来解决。这里设 : 表示去竹竿底部的最短距离, 表示去当前这个竹竿传送门起点的最短距离。
我们给两个初始状态。
- :表示从起点 0 到达第 个竹竿底部的最短时间
- : 表示从起点 0 到第 个竹竿的传送门起点的最短时间
接着我们找出要去下一个竹竿,要考虑的情况:
- 如何前往要去下一个传送门的起点位置:
- 我们可以从上一个传送门到达这个竹竿的传送门,再走去要去下一个竹竿的传送门起点
- 也可以从竹竿底部往上爬到传送门的起点
- 如何到达下一个竹竿的底部:
- 从上一个竹竿底部爬到这个竹竿底部
- 从上一个竹竿通过传送门传送到这个竹竿的终点位置,往下爬
可以浅浅看下图,想象一下:

下边是代码实现
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 分
【问题描述】
小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 的正方形 区域。这两块区域都按照 的规格进行了均等划分,划分成了若干块面积 相同的小区域,其中每块小区域要么是岩石,要么就是土壤,在垂直或者水平 方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进 行合并,他想知道合并以后可以得到的最大的一块土地的面积是多少(土地的 面积就是土地中土壤小区域的块数)?在进行合并时,小区域之间必须对齐。可以在两块方形区域的任何一条边 上进行合并,可以对两块方形区域进行 度、 度、 度、 度的旋转, 但不可以进行上下或左右翻转,并且两块方形区域不可以发生重叠。
【输入格式】
第一行一个整数 表示区域大小。接下来 行表示第一块区域,每行 个值为 或 的整数,相邻的整数之间用空格进行分隔。值为 表示这块小区域是岩石,值为 表示这块小区域是土壤。
再接下来 行表示第二块区域,每行 个值为 或 的整数,相邻的整数之间用空格进行分隔。值为 表示这块小区域是岩石,值为 表示这块小区域是土壤。
【输出格式】
一个整数表示将两块区域合并之后可以产生的最大的土地面积。【样例输入】
sh4 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【样例输出】
sh15【样例说明】
第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳 的合并方式,此时最大的土地面积为 。
【评测用例规模与约定】
对于 30% 的数据,。
对于 60% 的数据,。
对于 100% 的数据,。
解法
我的解法
思路是先找出每个区域边缘的是否有土壤,有土壤,说明可以连接,没有的话说明都没法与其他区域的土壤合并连成一片。
接着对有边缘的土壤进行搜索,找出连接的土壤能最大的情况。
最后,根据两个边缘是否有土壤来进行相加或者两者中的最大值。
但只跑通了几个样例。。。。
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;
}
}
}
}

优秀题解
试题 G: 买二赠一【编程题】
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
某商场有 件商品,其中第 件的价格是 。现在该商场正在进行 “买二 赠一” 的优惠活动,具体规则是: 每购买 件商品,假设其中较便宜的价格是 (如果两件商品价格一样, 则 等于其中一件商品的价格),就可以从剩余商品中任选一件价格不超过 的商品,免费获得这一件商品。可以通过反复购买 件商品来获得多件免费商品,但是每件商品只能被购买或免费获得一次。小明想知道如果要拿下所有商品(包含购买和免费获得),至少要花费多少钱?
【输入格式】
第一行包含一个整数 。 第二行包含 个整数,代表 。【输出格式】
输出一个整数,代表答案。【样例输入】
sh7 1 4 2 8 5 7 1【样例输出】
sh25【样例说明】
小明可以先购买价格 和 的商品,免费获得一件价格为 的商品;再后 买价格为 和 的商品,免费获得价格为 的商品;最后单独购买剩下的一件 价格为 的商品。总计花费 。不存在花费更低的方案。【评测用例规模与约定】
对于 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);
}
}

试题 H: 合并石子【编程题】
试题 I: 最大开支【编程题】
【问题描述】
小蓝所在学校周边新开业了一家游乐园,小蓝作为班长,打算组织大家去 游乐园玩。已知一共有 个人参加这次活动,游乐园有 个娱乐项目,每个 项目都需要买门票后才可进去游玩。门票的价格并不是固定的,团购的人越多 单价越便宜,当团购的人数大于某个阈值时,这些团购的人便可以免费进入项 目进行游玩。这 个娱乐项目是独立的,所以只有选择了同一个项目的人才可以参与这个项目的团购。第 个项目的门票价格 与团购的人数 的关系可 以看作是一个函数:
其中 表示取二者之中的最大值。当 时说明团购人数达到了此项目的免单阈值。 这 个人可以根据自己的喜好选择 个娱乐项目中的一种,或者有些人 对这些娱乐项目都没有兴趣,也可以选择不去任何一个项目。每个人最多只会 选择一个娱乐项目,如果多个人选择了同一个娱乐项目,那么他们都将享受对 应的团购价格。小蓝想知道他至少需要准备多少钱,使得无论大家如何选择, 他都有能力支付得起所有 个人购买娱乐项目的门票钱。
【输入格式】
第一行两个整数 、,分别表示参加活动的人数和娱乐项目的个数。 接下来 行,每行两个整数,其中第 行为 、,表示第 个游乐地点 的门票函数中的参数。【输出格式】
一个整数,表示小蓝至少需要准备多少钱,使得大家无论如何选择项目, 自己都支付得起。【样例输入】
sh4 2 -4 10 -2 7【样例输出】
sh12【样例说明】
样例中有 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 其中当 时花费最大,为 。此时 个人去第一个项目,所以第一个项目的单价为 ,在这个项目上的花费为 ; 个人去 第二个项目,所以第二个项目得单价为 ,在这个项目上的花费为 ;还有 个人没去任何项目,不用统计;总花费为 ,这是花费最大的一种方案,所以答案为 。 【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ N, M ≤ 10。
对于 50% 的评测用例,1 ≤ N, M ≤ 1000。
对于 100% 的评测用例,1 ≤ N, M, Bi ≤ 10^5,− 10^5≤ Ki < 0。
试题 J: 魔法阵【编程题】
【问题描述】
魔法师小蓝为了营救自己的朋友小 ;来到了敌人 置的魔法阵。魔法阵可以看作是一幅具有 个结点 条边的无向图,结点编号为 ,图中没有重边和自环。敌人在每条边上都布置了陷阱,每条边都有一个伤害属性 ,每当小蓝经过一条边时就会受到这条边对应的 的伤害。小蓝从结点 出发,沿着边行走,想要到达结点 营敷小 。小蓝有一种特殊的魔法可以使用,假设一条路径按照顺序依次经过了以下 条边:(可以出现重复的边),那么期间小
蓝愛到的总伤害就是 表示边 的伤害属性。如果 ,那么小蓝就可以从这 条边当中选出连续出现的 条边 并免去在这 条边行 走期间所受到的伤害,即使用魔法之后路径总伤害变为 。注意必须恰好选出连续出现的 条边,所以当 时无法使用魔法。小蓝最多只可以使用一次上述的魔法,请问从结点 出发到结点 受到的最小伤害是多少?题目保证至少存在一条从结点 到 的路径。
【输入格式】
第一行输入三个整数,,用空格分隔。 接下来 行,每行包含三个整数 ,表示结点 与结点 之间存在一条伤害属性为 的无向边。【输出格式】
输出一行,包含一个整数,表示小蓝从结点 到结点 受到的最小伤害。【样例输入 1】
4 2 3
0 1 2
1 2 1
2 3 4【样例输出 1】
2【样例输入 2】
2 5 1
0 1 1【样例输出 2】
0【样例说明】
样例 ,存在路径:0 → 1 → 2 → 3,K = 2,如果在 0 → 1 → 2 上使用魔 法,那么答案就是 0 + 0 + 4 = 4;如果在 1 → 2 → 3 上使用魔法,那么答案就 是 2 + 0 + 0 = 2。再也找不到比 2 还小的答案了,所以答案就是 2。样例 ,存在路径: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;
}
}
}
}
}

