23年蓝桥杯java-b组
前言：
23年蓝桥杯当时并没有参加，不过打算参加24年的蓝桥杯，于是打算复习下23年的题目，哦，不做不知道，做了几道题后评价一下，真的是老🐷上🏠，难死了；😂
发现蓝桥杯的题目都是偏思维，和立扣的题目还是有很大差别的；想要参加蓝桥杯的话，一定要将往年的真题都看一看；
话不多说，上题目！
A.阶乘求和
【问题描述】
令 S = 1! + 2! + 3! + … + 202320232023! ，
求 S 的末尾 9 位数字。
提示：答案首位不为 0 。
结果：420940313
看着题目很短，毕竟是签到题，但是没有一些常识的话还真不一定能做出来；
即：
应该知道的前置常识：
1.随着阶乘的增加，结果后边的0的个数会不断增加，0的数量还是很容易判断的，n的阶乘中可以挑出一对5和2，即能组成*10，就可以确认结果的最后一位会是0，通过思考，能想像到2很容易挑出，再挑出5就行了，以40为例，40的阶乘中有5,10,15,20,25,30,35,40,而25可以写成5 * 5，能拆分成两个5因子，所以40就应该是最小能满足最后9位为0的阶乘了；即使想不到40,45应该也是可以想到的；否则的话这道题是没法做的；
2.java中大数的计算可以使用BigInteger，使用long容易爆；
最后就变成了使用BigInteger进行for循环到40的阶乘累加和运算；
铛铛：
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
//先找出40的阶乘后有9个0，知道只用算到40就可以啦
BigInteger sum=BigInteger.valueOf(0);
for (int i = 1; i <=40 ; i++) {
BigInteger sum1=BigInteger.valueOf(1);
for (int j = 1; j <=i ; j++) {
sum1=sum1.multiply(BigInteger.valueOf(j));
}
sum= sum.add(sum1);
}
// 取模获取最后九位数
BigInteger modValue = BigInteger.valueOf(1000000000);
BigInteger lastNineDigits = sum.mod(modValue);
// 输出最后九位数
System.out.println(lastNineDigits);
}
}
B.幸运数字
【问题描述】
哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整 数。例如 126 是十进制下的一个哈沙德数，因为 (126) 10 mod
(1+2+6) = 0 ； 126 也是八进制下的哈沙德数，因为 (126) 10 = (176) 8 ， (126) 10 mod (1 + 7 + 6) = 0 ； 同时 126 也是 16 进制下的哈沙德数，因为 (126) 10 = (7 e ) 16 ， (126) 10 mod (7 + e ) = 0 。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为
哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示 为：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数 字是多少？你只需要告诉小蓝这个整数的十进制表示即可。
答案：215040
第一眼看就知道是要考进制转换了，关键在于如何转换才能做到正确又不失优雅；如果没有个好的思路，会写的很乱甚至把自己绕进去了；
这里介绍一种方法：
既然转换8进制，那就除8，余数就是对应的进制的后位数字，商有余接着除，举题中例子126的8进制，126除8=15…6, 15除8=1…7,1除8=…1,三个余数分别是1,7,6是不是就是题目所述，其他同理；可写出方法：😏
public static int li(int n,int m) {//传入数字和要转换的进制 int sum=0; while (n>0){ sum=sum+n%m; n=n/m; } return sum; }
逼格瞬间就低了，然后再从小遍历数字是否符合条件直到第2023个数字；
【代码实现】
public class Main {
public static void main(String[] args) {
int count=0;
int i=0;
while (count<2023)//统计数字个数
{i=i+1;
if(i%li(i,2)==0&&i%li(i,8)==0&&i%li(i,10)==0&&i%li(i,16)==0)//且连接，必须全部符合
count++;
}
System.out.println(i);
}
public static int li(int n,int m) {//传入数字和要转换的进制
int sum=0;
while (n>0){
sum=sum+n%m;
n=n/m;
}
return sum;
}
}
C.数组分割
[题目描述]
小蓝有一个长度为 N 的数组 A = [A0, A1,…, AN−1]。现在小蓝想要从 A 对应的数组下标所构成的集合 I = {0,
1, 2, . . . , N − 1} 中找出一个子集 R1，那么 R1在 I 中的补集为 R2。记 S1=∑r∈R1Ar，S2
=∑r∈R2Ar，我们要求 S1 和 S2 均为偶数，请问在这种情况下共有多少种不同的 R1。当 R1 或 R2 为空集时我们将 S1 或 S2 视为 0。 输入格式 第一行一个整数 T，表示有 T 组数据。 接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N，表示数组
A 的长度；第二行输入 N 个整数从左至右依次为 A0, A1, . . . , AN−1，相邻元素之间用空格分隔。 输出格式
对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对1000000007 进行取模后输出。
样例输入:
2
6 6
2
1 6
样例输出:
4
0
[提示]
对于第一组数据，答案为 4。（注意：大括号内的数字表示元素在数组中的下标。）
R1 = {0}, R2 = {1}；此时 S1 = A0 = 6 为偶数, S2 = A1 = 6 为偶数。
R1 = {1}, R2 = {0}；此时 S1 = A1 = 6 为偶数, S2 = A0 = 6 为偶数。
R1 = {0, 1}, R2 = {}；此时 S1 = A0 + A1 = 12 为偶数, S2 = 0 为偶数。
R1 = {}, R2 = {0, 1}；此时 S1 = 0 为偶数, S2 = A0 + A1 = 12 为偶数。
对于第二组数据，无论怎么选择，都不满足条件，所以答案为 0。
对于 20% 的评测用例，1 ≤ N ≤ 10。
对于 40% 的评测用例，1 ≤ N ≤ 10^2。
对于 100% 的评测用例，1 ≤ T ≤ 10, 1 ≤ N ≤ 10^3 , 0 ≤ Ai ≤ 10^9。
【题解思路】：
开始上难度了，🤒，如果平常经常只写立扣那种单接口题目，写这种的会很不适，所以才要提前接触；
先不说多个数组，对一个数组进行分析，题目意思是对于一个数组，希望能分成两个集合，A1,A2两集合的和都应该为偶数；然后计算A1,A2集合有多少种不同的组合；
我们能知道很多有用信息：
1.既然两集合都应为偶数，那么数组总和也应该是偶数；
2.题目中求的是R1即A1集合的总数，其实也是A2集合的总数，因为U-R1=R2，只用讨论左侧全部情况，右侧相当于也讨论了
由信息1知道，三个数组和肯定都是偶数，我们可以讨论A1集合的全部情况，那么A2集合不用讨论就已经注定了，
题目中有两个注意点：
1.怎么将偶数的情况分析完：先分析数字是奇数还是偶数，统计偶数个数为l，总方法2的l次方
2.奇数的情况：先分析所有奇数个数为r，
1）若r为奇数，则该数组不能分为两个偶数和，直接结束；
2）若r为偶数，每次拿出偶数个奇数，即C(0, J) + C(2, J) + C(4, J) + … + C(J, J)，又对于一个偶数个数的集合，从中拿去奇数个数和从中拿去偶数个数的方法应该相同，总方法=2的r次方=拿奇数个数的方法+拿偶数个数的方法；
具体解释看代码
【示例代码】
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
//思路：题目意思是选出所有以偶数分割的数组方案；
//可以知道数组和必须是偶数；
int mod =1000000007;
Scanner scanner = new Scanner(System.in);
int a=scanner.nextInt(); //先传入有多少个数组；
int[] b;//接收传入的数组
while (a>0){
int m=scanner.nextInt(); //数组长度
b=new int[m];
for (int i = 0; i <m; i++) {
b[i]=scanner.nextInt(); //for循环接收数组各个值；
}
int l=0; //统计偶数个数
int r=0; // 统计奇数个数
for (int i = 0; i <m; i++) {
if (b[i]%2==0)l++;
else r++;
}
if (r%2!=0) System.out.println(0);//如果奇数个数是奇数个，那么数组值和必为奇数，必然不可能满足条件；
else {
if (r==0)r=1; //特殊情况，特殊处理，方便之后计算；
int res=1;
for (int i = 0; i <l+r-1 ; i++) {//为什么答案会是这个？，
// 因为偶数中取法:2的l次方:每个数都是可取可不取；共有l个数；
// 奇数中取法2的r-1次方：每次必须取偶数个数；可以看作C(0, J) + C(2, J) + C(4, J) + … + C(J, J)
// 因为一共有偶数个数，那么数中的奇数个数和偶数个数和是相同的，所以取偶数个数的方法=取奇数个数的方法，又相加起来=全部方法=2的j次方；巴拉巴啦‘
res=res*2%mod;
}
System.out.println(res);
}
a--;
}
}
}
其实上述A1，A2表述不是非常清晰，有些同学深究时还是不太懂单对奇数偶数分析为什么就包含了全部的情况，其实我们可以这样想：
因为题目让分为两个数组来做，对于上述所有的分析的都可以认为是对A1数组进行的分析，A1包含了所有偶数的情况*奇数的情况（A1中分成了两个小集合，一个集合只讨论偶数，一个集合只讨论奇数，总数=奇数方法 * 偶数方法），那么A2肯定和A1对应就行了；
D.矩形总面积
[题目描述]
平面上有个两个矩形 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% 的数据，所有坐标的取值范围是 [0, 10^3 ]。
对于 100% 的数据，所有坐标的取值范围是 [0, 10^5 ]。
【解题思路】：
又是一道思维逻辑题😥
首先要知道重叠面积应该是怎么形成的，才能下手敲代码，不然逻辑会非常混乱；
重叠面积应该是有两个矩形的最左下角点比较出个共同拥有的即较大的，最右上角点比较出较小的即共同拥有的，你可以仔细想想，是不是这样，当然，这种情况必须是有重叠，无重叠会出现负数；🤐：这点需要好好理解一下
代码语言就是：
int overlapX1 = Math.max(x1, x3);
int overlapY1 = Math.max(y1, y3);
int overlapX2 = Math.min(x2, x4);
int overlapY2 = Math.min(y2, y4);
【完整代码】
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int x1=scanner.nextInt();
int y1=scanner.nextInt();
int x2=scanner.nextInt();
int y2=scanner.nextInt();
int x3=scanner.nextInt();
int y3=scanner.nextInt();
int x4=scanner.nextInt();
int y4=scanner.nextInt();
//先算两个矩形的面积；
long s1= (long) (x2 - x1) *(y2-y1);
long s2= (long) (x4 - x3) *(y4-y3);
//算重叠区域左下角和右上角坐标
//若重叠，则左下角坐标为两者左下角坐标中的坐标最大者
// 右上角坐标为两者右上角坐标中的最小者（仔细想一想）
int overlapX1 = Math.max(x1, x3);
int overlapY1 = Math.max(y1, y3);
int overlapX2 = Math.min(x2, x4);
int overlapY2 = Math.min(y2, y4);
// 重叠面积,右减左，上减下，再和0比较，若大于，说明是存在重叠面积的；
long s= (long) Math.max(0, (overlapX2 - overlapX1)) *Math.max(0,(overlapY2-overlapY1));
s=s1+s2-s;
System.out.println(s);
}
}
E.蜗牛
【题目描述】
这天，一只蜗牛来到了二维坐标系的原点。
在 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；
对于 100% 的数据，保证 n ≤ 105，ai , bi ≤ 104，xi ≤ 109。
【思路】
首先需要知道这是一道动态规划类型的题目，因为题目中有最短时间的字眼，并且前一个和后一个之间有联系，很容易就能想到；
而且也能很容易写出前面的dp值，复杂的是递推公式如何确立，因为该题并不是单独的一个点，而是包含了传送门，需要同时维护两个递推公式；想到这里，应该就有些思路了；再详细的就不说了，毕竟动态规划看的就是条件，做起来套公式还是没有那么多的弯弯绕绕的；🤗
【具体代码】
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 竹竿的数量
// 输入每个竹竿的x坐标
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
// 输入每个传送门的位置和传送到的位置
double[][] b = new double[n][2];
for (int i = 0; i < n-1; i++) {
b[i][0] = scanner.nextInt(); // 传送门自身的传送点在哪个高度
b[i][1] = scanner.nextInt(); // 传送门传送到的下一个杆子的高度
}
// 动态规划计算最短时间
double[][] dp = new double[n][2];
dp[0][0] = a[0]; // 第一根竹竿底部的位置
dp[0][1] = a[0] + b[0][0] / 0.7; // 第一个竹竿的传送门
for (int i = 1; i < n; i++) {
if(b[i][0]<=b[i-1][1])// 传送到的点在自己杆子传送门的上边，需要下滑
dp[i][1]=Math.min(dp[i-1][0]+(a[i]-a[i-1])+b[i][0]/0.7,dp[i-1][1]+(b[i-1][1]-b[i][0])/1.3); //该根杆子的传送点
else dp[i][1]= Math.min(dp[i-1][0]+(a[i]-a[i-1])+b[i][0]/0.7,dp[i-1][1]+(b[i][0]-b[i-1][1])/0.7); //传到的点在自己传送门的下方，需要上移
dp[i][0]=Math.min(dp[i-1][0]+(a[i]-a[i-1]),dp[i-1][1]+b[i-1][1]/1.3); // 该根杆子的底部节点；
}
// 输出结果，保留两位小数
System.out.printf("%.2f\n", dp[n - 1][0]);
}
}
