14届蓝桥杯省赛Java B 组Q1+Q3+Q10

题目链接Q1蓝桥云课幸运数字洛谷P12324 [蓝桥杯 2023 省 Java B] 幸运数字Q3蓝桥云课矩形总面积洛谷P12326 [蓝桥杯 2023 省 Java B] 矩形总面积Q10蓝桥云课阶乘求和洛谷P12323 [蓝桥杯 2023 省 Java B] 阶乘求和算法原理Q1解法模拟时间复杂度O(1)找了半天没找到规律就直接模拟吧~由于题目已经给出了前10个数那么我们枚举时就接着枚举就行了当枚举到数 i 时最笨的方法①将 i 转成2进制判断2进制各位数字之和是否满足②将 i 转成10进制判断2进制各位数字之和是否满足③将 i 转成8进制判断8进制各位数字之和是否满足④将 i 转成16进制判断16进制各位数字之和是否满足博主替大家尝试了这会导致严重的超时因为转换进制时会涉及到大量的StringBuffer、字符串反转、字符遍历等慢操作其实我们转念一想上述的进制转换完全没必要二进制可以快速用Integer.bitCount(i)计算出各位的数字之和其余进制直接累加%各进制的余数即可8进制就%816进制就%16因为就算你把这个数转成了16进制里面的a、b、c、d、e、f一样要转换回来而这个值就是原本的10、11、12、13、14、15Q3解法平面几何时间复杂度O(1)计算两个矩形的面积没有难度s1(x2-x1)×(y2-y1)s2(x4-x3)×(y4-y3)难在如何去找重叠区域的面积如果一个个枚举的话很麻烦且容易出错其实我们通过观察可以发现在重叠区域处重叠区域左边界max(两矩形左边界)重叠区域右边界min(两矩形右边界)因此宽度右-左重叠区域下边界max(两矩形下边界)重叠区域上边界min(两矩形上边界)因此高度上-下若长度0且宽度0则说明重叠区域存在总面积s1s2-重叠面积否则说明不存在两者存在负数与0取最大值总面积s1s2-0Q10解法一暴力求解时间复杂度O(n³(logn)²)BigInteger 基础创建方式内置常量直接使用无需创建BigInteger.ZERO; // 代表数值0 BigInteger.ONE; // 代表数值1 BigInteger.TEN; // 代表数值10通过基本数据类型创建valueOf 方法// 通过long类型数值创建BigInteger对象 BigInteger num1 BigInteger.valueOf(100); BigInteger num2 BigInteger.valueOf(2024);通过字符串创建构造方法// 创建超大整数远超long的取值范围 BigInteger bigNum new BigInteger(123456789012345678901234567890);核心四则运算// 先定义两个基础大数用于演示 BigInteger a BigInteger.valueOf(15); BigInteger b BigInteger.valueOf(4); // 1. 加法a b BigInteger addResult a.add(b); // 结果19 // 2. 减法a - b BigInteger subResult a.subtract(b); // 结果11 // 3. 乘法a * b BigInteger mulResult a.multiply(b); // 结果60 // 4. 除法a / b取整数部分向下取整 BigInteger divResult a.divide(b); // 结果3 // 5. 取模/取余a % b结果恒为非负数 BigInteger modResult a.mod(b); // 结果3高频实用数学方法BigInteger a BigInteger.valueOf(6); BigInteger b BigInteger.valueOf(9); BigInteger exponent BigInteger.valueOf(3); BigInteger mod BigInteger.valueOf(7); // 1. 幂运算a的n次方n为int类型 BigInteger powResult a.pow(3); // 6^3216 // 2. 相反数-a BigInteger negateResult a.negate(); // -6 // 3. 绝对值 BigInteger absResult a.negate().abs(); // 6 // 4. 最大公约数GCD BigInteger gcdResult a.gcd(b); // 6和9的最大公约数3位运算方法BigInteger a BigInteger.valueOf(8); // 二进制1000 BigInteger b BigInteger.valueOf(4); // 二进制0100 a.and(b); // 按位与0000 → 0 a.or(b); // 按位或1100 → 12 a.xor(b); // 按位异或1100 → 12 a.not(); // 按位取反类型转换方法BigInteger num BigInteger.valueOf(1000); // 1. 转换为字符串最常用无溢出风险 String str num.toString(); // 2. 转换为long类型数值超过long范围会溢出慎用 long longVal num.longValue(); // 3. 转换为int类型数值超过int范围会溢出慎用 int intVal num.intValue(); // 4. 转换为double类型 double doubleVal num.doubleValue();解法二找规律时间复杂度O(1)通过D.二分查找二分答案第K小/第K大——793. 阶乘函数后 K 个零这篇博客可知阶乘结果中末尾0的个数与因数5的个数有关当末尾0的个数超过9时后面再算后9位也必然是0因此我们完全没必要算202320232023这么大的数的阶乘我们通过上述规律可得出阶乘中因数5的个数51个、102个、153个、204个、256个、307个、358个、409个因此我们仅需算到40的阶乘即可细节①25多出2个因数5而不是1个的原因255×5②计算阶乘过程中要及时取模避免long溢出Java代码Q1import java.util.Scanner; public class Main { //暴力模拟的超时代码 private static final char[] chars{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}; public static void main(String[] args) { int cnt10; for(int i127;;i){ //获取该数2进制 String twturn(i,2); if(!check(tw,i)) continue; if(!check(String.valueOf(i),i)) continue; //获取该数8进制 String eiturn(i,8); if(!check(ei,i)) continue; //获取该数16进制 String siturn(i,16); if(!check(si,i)) continue; cnt; if(cnt2023){ System.out.println(i); break; } } } //转换进制 private static String turn(int n,int r){ StringBuffer curnew StringBuffer(); int tn; while(t0){ int remt%r; if(r16) cur.append(chars[rem]); else cur.append(rem0); t/r; } return cur.reverse().toString(); } //判断该数十进制能否能否整除该进制位各位数之和 private static boolean check(String x,int n){ //获取该数在该进制下各位数字之和 int sum0; for(int i0;ix.length();i){ char remx.charAt(i); sum(rem0rem9)?rem-0:rem-a10; } return n%sum0; } }import java.util.*; public class Main { //优化后的AC代码 public static void main(String[] args) { int cnt10; for(int i127;;i){ //判断2进制 if(i%Integer.bitCount(i)!0) continue; //判断10进制 if(!check(i,10)) continue; //判断8进制 if(!check(i,8)) continue; //判断16进制 if(!check(i,16)) continue; cnt; if(cnt2023){ System.out.println(i); break; } } } //判断该数十进制能否能否整除该进制位各位数之和 private static boolean check(int n,int r){ //获取该数在该进制下各位数字之和 int sum0; int tn; while(t0){ int remt%r; sumrem; t/r; } return n%sum0; } }Q3import java.util.*; public class Main { public static void main(String[] args) { Scanner scnew Scanner(System.in); int x1sc.nextInt(),y1sc.nextInt(); int x2sc.nextInt(),y2sc.nextInt(); int x3sc.nextInt(),y3sc.nextInt(); int x4sc.nextInt(),y4sc.nextInt(); //转成long再接收防止溢出 long s11L*(x2-x1)*(y2-y1),s21L*(x4-x3)*(y4-y3); //判断是否有重叠部分 //计算重叠部分的宽度 //重叠区域左边界max(两矩形左边界)重叠区域右边界min(两矩形右边界) int widthMath.max(0,Math.min(x2,x4)-Math.max(x1,x3)); //计算重叠部分的高度 int heightMath.max(0,Math.min(y2,y4)-Math.max(y1,y3)); long s3width0height0?1L*width*height:0; System.out.println(s1s2-s3); sc.close(); } }Q10import java.util.*; import java.math.BigInteger; public class Main { //解法一暴力求解 public static void main(String[] args) { BigInteger aBigInteger.valueOf(1); BigInteger sumBigInteger.ZERO; for(int i2;i2024;i){ sumsum.add(a); aa.multiply(BigInteger.valueOf(i)); } String retsum.toString(); System.out.println(ret.substring(ret.length()-9)); } }import java.util.*; public class Main { //解法二找规律 public static void main(String[] args) { long sum0; for(int i1;i40;i){ //求阶乘 long a1; for(int j1;ji;j){ a*j; a%1_000_000_000;//取模防溢出 } suma; } System.out.println(sum%1_000_000_000); } }