第14届java A组蓝桥杯做题记录

A题特殊日期

请添加图片描述

package Java14省赛.Java研究生组;import java.time.Year;
//特殊判断一下2月份，leaf 为true + 1
import java.util.*;import 蓝桥杯.dfs_n皇后;
public class 特殊日期 {static int sum(int d){int res = 0;while(d > 0){res += d % 10;d /= 10;}return res;}static boolean check(int y,int m,int d){return sum(y) == (sum(m) + sum(d));}public static void main(String[] args){int []month = {0,31,28,31,30,31,30,31,31,30,31,30,31};int ans = 0;for(int year = 1900;year < 10000;year++){boolean leaf = ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));for(int m = 1;m <= 12;m ++){for(int d = 1;d <= month[m];d ++)if(check(year, m, d)) ans++;if(leaf && m == 2 && check(year, m, 29)) ans++;}}System.out.print(ans);	}
}

B题与或异或

请添加图片描述


import java.util.*;
// 可以枚举op的序列,检验是否ans[4][0] == 1
//op的枚举树是个满三叉树
public class Main {static int cnt = 0;public static void main(String[] args){int[][] arr = new int[5][5];arr[0][0] = 1;arr[0][1] = 0;arr[0][2] = 1;arr[0][3] = 0;arr[0][4] = 1;dfs(arr,1,0);System.out.print(cnt);}static void dfs(int[][] arr,int i,int j){if(i == 5) {if(arr[4][0] == 1)cnt++; return;}for(int k = 0;k < 3;k++) {if(k == 0) arr[i][j] = arr[i - 1][j] & arr[i - 1][j + 1];else if(k == 1) arr[i][j] = arr[i - 1][j] | arr[i - 1][j + 1];else arr[i][j] = arr[i - 1][j] ^ arr[i - 1][j + 1];if(i + j == 4) dfs(arr, i + 1, 0);else dfs(arr, i, j + 1);}}
}

C题平均

请添加图片描述

import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n=scanner.nextInt();int c=n/10;long sum=0;PriorityQueue<Integer>[] pqs=new PriorityQueue[10];for (int i = 0; i < 10; i++) {pqs[i]=new PriorityQueue<Integer>(); }for (int i = 0; i < n; i++) {int a=scanner.nextInt();int b=scanner.nextInt();pqs[a].add(b);}for (int i = 0; i < 10; i++) {while (pqs[i].size()>c) {sum+=pqs[i].poll();}}System.out.print(sum);}    
}

D题棋盘

请添加图片描述

package Java14省赛.Java研究生组;import java.util.Scanner;// d[i][j] 代表着以(i,j)为顶点的数所有+1，
// 二维差分与二维前缀和相对应 
public class 棋盘 {static int N = 2010;static int[][] d = new int[N][N];public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(),m = scanner.nextInt();for(int i = 0;i < m;i++){int x1 = scanner.nextInt(),y1 = scanner.nextInt();int x2 = scanner.nextInt(),y2 = scanner.nextInt();d[x1][y1] ++;d[x2 + 1][y2 + 1]++;d[x1][y2 + 1]--; d[x2 + 1][y1]--;}for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)d[i][j] += (d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]);for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++)if(d[i][j] % 2 == 1) System.out.print(1);else System.out.print(0);System.out.println();}}
}

E 互质的个数

请添加图片描述

package Java14省赛.Java研究生组;
import java.util.*;
//phi(x） = x *.... *(i - 1)/ i;i 为质因数
//a^b的质因数与a的质因数相同
//试除法求a的质因数 x *.... *(i - 1)/ i
public class 互质的个数 {static int mod = 998244353;static long qmi(long a,long k){long res = 1;while(k > 0){if(k % 2 == 1) res = res * a % mod;a = a * a % mod;k >>= 1;}return res % mod;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);long a = scanner.nextLong(),b = scanner.nextLong();long k = qmi(a, b - 1) % mod, ans = a;for(int i = 2;i <= a / i;i++){if(a % i == 0){while(a % i == 0) a /= i;ans = ans /i *(i - 1);}}if(a > 1) ans = ans / a *( a- 1);System.out.print(ans * k % mod);}
}

F阶乘的和

package Java14省赛.Java研究生组;//m如果有 n个且n % (m + 1) == 0,则最大因子至少因子是m + 1的阶乘
//如果有m如果有 n个但n % （m + 1) != 0,则最大因子是m import java.util.Scanner;public class  阶乘的和{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();long[] arr = new long[n];long min = Integer.MAX_VALUE;long countMin = 0;for(int i = 0; i < arr.length; i++){arr[i] = scan.nextLong();min = Math.min(min, arr[i]);}while(true){countMin = countMin / min;for(int i = 0; i < arr.length; i++){if(arr[i] == min) countMin++;}if(countMin % (min + 1) == 0 && min != 0){min++;}else{break;}}scan.close();System.out.println(min);}
}
![请添加图片描述](https://img-blog.csdnimg.cn/direct/244cd2f88265415a84bd45588faf9022.png)

G题小蓝的旅行

请添加图片描述
a little 难写，先更思路

// 1.如果没有油箱限制，我们只需贪心从第i个加油站到第i+ 1个加油站
// 可以从前i个加油站中选择花费最小的即可，如果花费最小的加油站累计加油超过限制删除即可
// 2.有油箱限制的情况下，我们只需加上从j到i最大剩余量 + 加油量不能超过超过油箱
// 而在j加的油在j+1这些加油站的油箱都会整体上在j加油站上加油
// 我们树状数组维护的每个加油站的剩余油量，如果我从i到不了i + 1，我从中选择一个花费最少的j，
// 加油，加油有限制，不能超过加油站剩余的量和容量- Max[j , i]   ，
// 加完油，加油站的油量更新达到各个加油站的油量更新

H 太阳

请添加图片描述

package Java14省赛.Java研究生组;
import java.util.*;
// 由于太阳的高度大于线段计算出线段两端点在x坐标上的投影坐标
// 按照y的坐标降序Line查看是否区间覆盖
// 如何计算在x坐标上的投影？ x1 - y1 * (x1 - x2) /(y1 - y2);
// 如何查看区间是否被覆盖呢？可以用Treemap表示，key 表示左边界，value表示右边界
// Treemap是底层红黑树，是有序的，可以轻易的找到比他只小一点的左边界，然后比较即可public class 太阳 {static TreeMap<Double, Double> map = new TreeMap<Double, Double>();static double shadow(double x1,double y1,double x2,double y2){return x1 - y1 * (x1 - x2) /(y1 - y2);}private static void addRange(double l,double r)//合并区间{var L = map.floorEntry(l);var R = map.floorEntry(r);if(L != null && l < L.getValue()) l = L.getKey();if(R != null && r < R.getValue()) r = R.getValue();map.subMap(l, r).clear();map.put(l, r);}public static boolean queryRange(double left, double right) {var l = map.floorEntry(left);return l != null && l.getValue() >= right;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(),x = scanner.nextInt(),y = scanner.nextInt();List<Line> lines= new ArrayList<Line>();for(int i = 0;i < n;i++){int xi = scanner.nextInt(),yi = scanner.nextInt(),l = scanner.nextInt();lines.add(new Line(xi, yi, l));}lines.sort((l1,l2) -> Integer.compare(l2.y, l1.y));int res = 0;for(Line line:lines) {double l = shadow(line.lx,line.y, x, y);double r = shadow(line.rx,line.y, x, y);if(!queryRange(l, r)) res++;addRange(l, r);}System.out.println(res);}private static class Line {int lx, y, rx, length;public Line(int x, int y, int length) {this.length = length;lx = x;this.y = y;rx = x + length;}}
}

I高塔

请添加图片描述

package Java14省赛.Java研究生组;
// 如何处理组合数，这很重要
//C(n + m)(2 * n) * A[j](j =1 ~n) + [C(i + m)(2 * i) - C(i + m - 1)(2 * i) ]*=A[j]    (j =1 ~n)(i = 1 ~ n- 1)
// 上面的分析需用到生成函数，参考文章 https://blog.csdn.net/qq_44729222/article/details/130176129
//lucas定理,当a,b较大时，而p较小时
//C[a][b] = C[a / p][b / p] * C[a % p][b % p]
import java.util.*;public class 高塔
{static int N = 200100,mod = 998244353;static long[] A = new long[N];private static long lucas(long a, long b, int p) {if(a<p&&b<p) return C(a,b,p);return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;}private static long C(long a, long b,int p) {if(b>a) return 0;long res = 1,i,j;for(i = 1,j = a; i <= b; i ++, j--) {res = res*j%p;res = res*qmi(i,p-2,p)%p;}return res % mod;}private static long qmi(long a, int k, int m) {long res = 1;while(k!=0) {if((k&1)==1)res = res * a % m;a = a*a %m;k>>=1;}return res % mod;}public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(), m = scanner.nextInt();A[0] = 1;long ans = 0;for(int i = 1;i <= n;i++) A[i] = A[i - 1] * scanner.nextLong() % mod;	//System.out.print(lucas(24, 18, mod));long tmp = m % mod;long qq = tmp * tmp % mod;for(int i = 1;i < n;i++){ans = (ans + A[i] * tmp) %mod;tmp = (tmp * ((qq + mod * 500 - i * i)%mod)%mod) * (qmi((long)(4 * i * i + 2 * i), mod - 2, mod)) % mod;}ans = ans + A[n] * lucas(m + n, 2 * n, mod) % mod;System.out.print(ans);}
}