12届蓝桥杯省赛Java B 组Q1~Q4

题目链接Q1蓝桥云课ASCQ2蓝桥云课卡片Q3蓝桥云课直线Q4蓝桥云课货物摆放算法原理Q1解法作差时间复杂度O(1)思路很简单只需无脑算出L和A的差值加上65即可Q2解法找规律时间复杂度O(N)观察下图中k和n的对应变化因此我们仅需枚举k使得k的值能使(1k)k≥n此时的k就是所求最小的了Q3解法点斜式直线方程时间复杂度O(M²N²)这里M20,N21①遍历所有点对用两点确定一条直线②将直线转化为唯一的字符串表示通过约分斜率和截距③利用 Set 去重统计不重复的斜线数量④补充单独统计的横竖线得到最终结果其中约分的时候需要计算最大公约数其他用到最大公约数的题第 178 场双周赛Q2101005. 数对的最大公约数之和D.二分查找二分答案第K小/第K大——878. 第 N 个神奇数字A.每日一题——2654. 使数组所有元素变成 1 的最少操作次数D.二分查找二分答案第K小/第K大——1201. 丑数 III13届蓝桥杯省赛Java A 组Q1~Q4Q8的Q4Q4解法分解质因数隔板法时间复杂度O(√n)题目求多少个正整数三元组(L,W,H)满足L×W×Hn最暴力的解法就是枚举每个数使其凑成 i × j × k npublic class Main { public static void main(String[] args) { long cnt0; for(long i1;i2021041820210418L;i){ for(long j1;i*j2021041820210418L;j){ for(long k1;i*j*k2021041820210418L;k){ if(i*j*k2021041820210418L) cnt; } } } System.out.println(cnt*3); } }另外一种思路就是找质因数比如122×2×3对质因数2使用隔板法22| | 、| 22 | 、| | 22、2 | 2 |、| 2 | 2、2 | | 2共6种对质因数3使用隔板法3 | | 、| 3 | 、| | 3共3种所以总数6×318种举个例子22| |和3 | | 组合对应着(2²,2⁰,2⁰)×(3¹,3⁰,3⁰)(12,1,1)2 | 2 | 和 | | 3对应高中组合公式的从n2个空隙上挑2个放板子Java代码Q1public class Main { public static void main(String[] args) { System.out.println(L-A65); } }Q2import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int nsc.nextInt(); int k0; while(k*(k1)2*n) k; System.out.println(k); sc.close(); } }Q3import java.util.*; public class Main{ public static void main(String[] args){ SetString hashnew HashSet(); for(int x10;x120;x1){ for(int x20;x220;x2){ for(int y10;y121;y1){ for(int y20;y221;y2){ //横直线和竖直线后续处理因为没办法代入公式 if(x1x2||y1y2) continue; //计算直线斜率k int Yy2-y1; int Xx2-x1; //求最大公约数用于约分 int gcdKgcd(X,Y); //约分后的斜率 String k(Y/gcdK)/(X/gcdK); //通过ykxb推导出b // 由ykxb推导by1-k*x1(y1*Δx-x1*Δy)/Δx //b的分子 int b1y1*X-x1*Y; int b2X; //求最大公约数用于约分 int gcdbgcd(b1,b2); String b(b1/gcdb)/(b2/gcdb); String linekb; //将直线加入Set自动去重 hash.add(line); } } } } //斜线数量竖直线数量20水平线数量21 System.out.println(hash.size()2021); } //辗转相除法求最大公约数 private static int gcd(int a,int b){ return b0?a:gcd(b,a%b); } }Q4public class Main { public static void main(String[] args) { long n2021041820210418L; long ret1; //开始找质数 for(long i2;in/i;i){ if(n%i0){ //开始数这个质数在n里有多少 int cnt0; while(n%i0){ n/i; cnt; } //隔板法计算分法 ret*(cnt2)*(cnt1)/2; } } //如果最后剩下的n1说明它自己是个质数 if(n1) ret*3; System.out.println(ret); } }