【蓝桥杯 第十四届省赛Java B组】真题训练（A

真题训练（A"/>

【蓝桥杯 第十四届省赛Java B组】真题训练（A

目录

A、阶乘求和 - BigInteger

B、幸运数字 - 字符串 + 进制转换 暴力大法

C、数组分割 - 数学思维 + 乘法排列组合 

D、矩形总面积 - 推导公式 + 找规律

 （1）暴力大法好 50%

（2）正解 100%

E、蜗牛 - （我以为是模拟其实是线性DP）

（1）自己写的（模拟） 27/100

 （2）线性dp 100%

G、买二赠一 - 二分 + 贪心（80%）

---

A、阶乘求和 - BigInteger

思路：

当时比赛时，拿计算器算的，然后辛辛苦苦也没对

看到这个数肯定很大，而且只求后9位，阶乘越大，后面0个数会逐渐增长

首先设置BigInteger测试，发现从40！开始，再往后的数，后9位均为0，所以我们只用计算1！+……+39！然后取余就ok

答案是：420940313

import java.math.BigInteger;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);long res=0;for(int i=1;i<=39;i++)res=(res+f(i))%1000000000;System.out.println(res);}public static long f(int x){BigInteger res=new BigInteger("1");for(int i=1;i<=x;i++) {res=res.multiply(BigInteger.valueOf(i));res=res.mod(BigInteger.valueOf(1000000000));}return res.longValue();}
}

B、幸运数字 - 字符串 + 进制转换 暴力大法

思路：

可以偷懒用Java的进制转换api

注意对16进制转换时，a对应10，b对应11…… 

答案是：215040

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int cnt=0;int i=1;while(true){if(ck(i,Integer.toBinaryString(i))&&ck(i,Integer.toOctalString(i))&&ck(i,Integer.toHexString(i))&&ck(i,String.valueOf(i)))cnt++;if(cnt==2023) {System.out.println("!!"+i);break;}i++;}}public static boolean ck(int x,String s){int sum=0;for (char c:s.toCharArray())if(c>='a'&&c<='f') sum+=c-87;else sum+=c-'0';if(x%sum==0) return true;return false;}
}

C、数组分割 - 数学思维 + 乘法排列组合 

思路：

       这题我就想不出来（数学思维这种），做这题可以拓展一些思维，我每次见题第一反应都是暴力，因为题目要求是任取子集，也就是任意取元素，不要求元素连续，因此可以跳出数组遍历取值的思维

要让A0和A1均为偶数，我们可以将数组中元素分为【奇数】和【偶数】两堆

• 则取数时，在【偶数】堆可以任取，因为偶数+偶数=偶数
• 在【奇数】堆必须取偶数个，因为奇数+奇数=偶数
• 当然如果奇数堆元素个数为奇数，则该数组肯定无法满足题意，答案为0

假设【偶数】堆元素个数为s1，【奇数】堆元素个数为s2

• 在偶数堆的取法方案数     ans1 = 
• 在奇数堆取法方案数         ans2 = 

则答案为 ans1×ans2 = 

import java.util.*;public class Main {static int mod=1000000007;public static void main(String[] args) {Scanner sc=new Scanner(System.in);int t=sc.nextInt();while(t-->0){int n=sc.nextInt();int even=0,odd=0;for(int i=0;i<n;i++){int x=sc.nextInt();if(x%2==0) even++;else odd++;}if(odd%2==1){System.out.println(0);continue;}if(odd==0) odd=1; //防止出现负数int res=(int)(Math.pow(2,even)*Math.pow(2,odd-1)%mod);System.out.println(res);}}
}

D、矩形总面积 - 推导公式 + 找规律

 （1）暴力大法好 50%

import java.util.*;public class Main {static int n=10000;public static void main(String[] args) {Scanner sc=new Scanner(System.in);int[][] a=new int[n][n];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();int maxx=Math.max(Math.max(x1,x2),Math.max(x3,x4));int maxy=Math.max(Math.max(y1,y2),Math.max(y3,y4));for(int i=x1;i<x2;i++)for(int j=y1;j<y2;j++) a[i][j]+=1;for(int i=x3;i<x4;i++)for(int j=y3;j<y4;j++) a[i][j]+=1;long res=0;for(int i=0;i<=maxx;i++)for(int j=0;j<=maxy;j++) if(a[i][j]!=0) res++;System.out.println(res);}
}

（2）正解 100%

思路：

这题我记得考场上我写了一堆if else，一共写了前五题结果对了答案基本上没几个对的哈哈

大体思路：求出重叠部分左下角和右上角坐标，算出重叠面积，两个矩形面积-重叠就是答案

由图找规律可知，重叠部分：

• 左下角坐标opx1 = max{min(x1,x2)，min(x3,x4)} 
• 左下角坐标opy1 = max{min(y1,y2)，min(y3,y4)} 
• 右上角坐标opx2 = min{max(x1,x2)，max(x3,x4)} 
• 右上角坐标opy2 = min{max(y1,y2)，max(y3,y4)} 

因此重叠部分面积 = （opx2-opx1）×（opy1-opy2）

重叠的情况必为

opx2>opx1 && opy2>opy1

推导公式求解即可

注意用long 否则精度出现问题 

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);long x1=sc.nextInt(),y1= sc.nextInt();long x2=sc.nextInt(),y2= sc.nextInt();long x3=sc.nextInt(),y3= sc.nextInt();long x4=sc.nextInt(),y4= sc.nextInt();long opx1=Math.max(Math.min(x1,x2),Math.min(x3,x4));long opy1=Math.max(Math.min(y1,y2),Math.min(y3,y4));long opy2=Math.min(Math.max(y1,y2),Math.max(y3,y4));long opx2=Math.min(Math.max(x1,x2),Math.max(x3,x4));long s=(x2-x1)*(y2-y1)+(x3-x4)*(y3-y4);long op=0;if(opx2>opx1 && opy2>opy1) op=(opx2-opx1)*(opy2-opy1);long res=s-op;System.out.println(res);}
}

E、蜗牛 - （我以为是模拟其实是线性DP）

（1）自己写的（模拟） 27/100

思路：

当时比赛这题把我折磨死，记得当时也写了个模拟，样例过了，这次自己再写一遍模拟（思路很快）然后喜提27分哈哈

蓝桥杯2023年第十四届省赛真题-蜗牛 - C语言网

我写的模拟是贪心写法，也就是每一次进行两个选择：走平地or传送？

每次选最优解，已达到整体最优，但是思考想想：有可能是一直走平地最优，尽管第一次走传送比走平地更优，这样我的模拟就不全面了，这题也算练练我的模拟能力

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[n];double down=1.3,up=0.7,walk=0,cs=0,res=0;int cur=0,x=0,y=0;for(int i=0;i<n;i++) a[i]=sc.nextInt();res+=a[0];x=a[0];while(true){if(x==a[n-1]&&y==0) break; //如果抵达则退出int curdoor=sc.nextInt(),nextdoor=sc.nextInt(); //输入传送门位置walk=y/down+a[cur+1]-a[cur]; //走平地：a、从前一个传送门下来再爬来 b、如果直接就在平地，则y=0，即从前一个杆子底部爬来if(curdoor>y) cs=(curdoor-y)/up; //走传送门：分传送门在上or在下情况else cs=(y-curdoor)/down;if(cur==n-2) cs+=nextdoor/down; //如果是倒数第二根杆子往最后一根杆子走，则要从最后一个传送门下来x=a[cur+1];  //确定x y坐标，并每次取最小情况if(cs>walk){res+=walk;y=0;}else{res+=cs;y= cur==n-2? 0:nextdoor;}cur++;}System.out.println(String.format("%.2f",res));}
}

 （2）线性dp 100%

思路：

看了眼题解的dp法，跟我的模拟有异曲同工之妙，我感觉dp考虑的情况更全面

• dp[i][0]——蜗牛爬到第i根杆子底部的最短时间
• dp[i][1]——蜗牛爬到第i根杆子的传送门的最短时间

因此答案就是dp[n][0]

• 到第i根杆子底部有2种情况：
  • a、从前一根杆子底部爬来【dp[i-1][0]+x[i]-x[i-1]】
  • b、从前一根传送来，再从传送门下来【dp[i-1][1]+b[i-1]/down】
  • dp[i][0] = Math.min( dp[i-1][0]+x[i]-x[i-1] , dp[i-1][1]+b[i-1]/down );
• 到第i根杆子传送门有2种情况：
  • a、从第i根柱子底部爬上来【dp[i][0]+a[i]/up】
  • b、从前一根传送来，从这根上的一个传送门到另一个传送门【dp[i-1][1]+(a[i]>b[i-1]? (a[i]-b[i-1])/up:(b[i-1]-a[i])/down)】
  • dp[i][1] = Math.min(dp[i][0]+a[i]/up,dp[i-1][1]+(a[i]>b[i-1]? (a[i]-b[i-1])/up:(b[i-1]-a[i])/down));

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();double down=1.3,up=0.7;double[][] dp=new double[n+1][2];int[] x=new int[n+1],a=new int[n+1],b=new int[n+1];for(int i=1;i<=n;i++) x[i]=sc.nextInt();for(int i=1;i<=n-1;i++){a[i]=sc.nextInt();b[i]=sc.nextInt();}//dp[i][0]——蜗牛爬到第i根杆子底部的最短时间//dp[i][1]——蜗牛爬到第i根杆子的传送门的最短时间dp[1][0]=x[1];dp[1][1]=x[1]+a[1]/up;for(int i=2;i<=n;i++){dp[i][0]=Math.min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i-1]/down); //到第i根杆子底部有2种情况：a、从前一根杆子底部爬来 b、从前一根传送来，再从传送门下来dp[i][1]=Math.min(dp[i][0]+a[i]/up,dp[i-1][1]+(a[i]>b[i-1]? (a[i]-b[i-1])/up:(b[i-1]-a[i])/down)); //到第i根杆子传送门有2种情况：a、从第i根柱子底部爬上来 b、从前一根传送来，从这根上的一个传送门到另一个传送门}System.out.println(String.format("%.2f",dp[n][0]));}
}

G、买二赠一 - 二分 + 贪心（80%）

 

 

思路：

最优方案是每次买最大的两个，这样能保证白嫖的金额最大

因此先排序，然后倒着取两个最大的数 p1 p2（p1>p2），然后删去

再用二分找出≤p2/2的最大值，删去（相当于白嫖）

循环求和即可

不知道为啥这题都用二分优化了，还有20%超时

import java.util.*;public class Main {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();List<Integer> list=new ArrayList<>();for(int i=0;i<n;i++) {int x=sc.nextInt();list.add(x);}Collections.sort(list);long res=0;while(!list.isEmpty()){int p1=0,p2=0;p1=list.get(list.size()-1);list.remove(list.size()-1);if(list.size()-1>=0) //如果前面还有元素{p2=list.get(list.size()-1);list.remove(list.size()-1);int l=-1,r=list.size()-1;while(l<r){int mid=l+r+1>>1; //找出小于p2/2的最大值if(list.get(mid)<=p2/2) l=mid;else r=mid-1;}if(l!=-1) list.remove(l);}res+=p1+p2;}System.out.print(res);}}