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

本文主要是介绍第12届蓝桥杯java A组做题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A题：相乘

请添加图片描述

package JAVA12l蓝桥杯;
//求2021的逆元public class 相乘 {static int mod = (int)1e9 + 7;public static long qmi(long a,int k,int p){long res = 1;while(k > 0){if(k % 2 == 1) res = res * a % p;a = a * a % p;k >>= 1;}return res;}public static void main(String[] args){long ans = 999999999 * qmi(2021, mod - 2, mod) % mod;System.out.print(ans);}
}

B题：直线

package JAVA12l蓝桥杯;
import java.util.*;
//直线：枚举斜率k和截距b，两者有一个不同的即不同
//如果 k = (y2 - y1)/(x2 - x1)
/// b = (x2 * y1 - x1 *x2)/(x2 - x1)
public class 直线 {static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}public static void main(String[] args) {Set<String> Set= new TreeSet<>();for (int x1 = 0; x1 < 20; x1++)for (int y1 = 0; y1 < 21; y1++)for (int x2 = 0; x2 < 20; x2++)for (int y2 = 0; y2 < 21; y2++)if (x1 != x2) {int a = y2 - y1;int b = x1 - x2;int c = x2 * y1 - x1 * y2;int gcdn = gcd(a,gcd(b, c));Set.add(a / gcdn +","+b / gcdn +"," + c/gcdn);}System.out.println(Set.size() + 20);}
}

C题货物摆放

请添加图片描述

package JAVA12l蓝桥杯;
//枚举因子,写该代码之前计算过了 因子数量130左右
//
public class 货物摆放 {static int N = 200,cnt  = 0;static long[] factor = new long[N];public static void main(String[] args){long n = Long.parseLong("2021041820210418");for(int i = 1;i <= n / i;i++){if(n % i == 0){factor[++cnt] = i;if(i * i != n) factor[++cnt] = n /i;}}long res = 0;for(int i = 1;i <= cnt;i++)for(int j = 1;j <= cnt; j++)if(n % (factor[i] * factor[j]) == 0) res++;System.out.print(res);}
}

D题路径

请添加图片描述

package JAVA12l蓝桥杯;import java.util.*;// 图的边初始化可以如果小于等于21 i* j /gcd（i，j) else  2e9；
// 最短路问题，用dijkstra 邻接矩阵版
// 最短路每次选一个当前为更新且距离源点最短的点
public class 路径 {static int N = 2030,dis[] = new int[N];static int[][] g = new int[N][N];static boolean[] st = new boolean[N];static int dijkstra(int n){Arrays.fill(dis,(int) 2e9);dis[1] = 0;for(int i = 1;i <= n;i++){int t = -1;for(int j = 1;j <= n;j++)if(!st[j] && (t == -1 || dis[t] > dis[j]))t = j;if(t == -1) break;st[t] = true;for(int j = 1;j <= n;j++)if(dis[j] > dis[t] + g[t][j])dis[j] = dis[t] + g[t][j];}return dis[n];}static int gcd(int a,int b){if(b == 0) return a;else return gcd(b, a % b);}public static void main(String[] args){for(int i = 1;i <= 2021;i++)for(int j = i + 1;j <= 2021;j++)if(j - i <= 21)g[i][j] = g[j][i] = i * j / gcd(i, j);else g[i][j] = g[j][i] =(int) 2e9;System.out.print(dijkstra(2021));}
}

E题回路计算

请添加图片描述

package JAVA12l蓝桥杯;
import java.util.*;
// dp[i][j] 代表在i号教学楼，访问教学楼状态为j的不同方案
// 包括不包括 i？包括
// dp[i | 1 << k][j] = dp[i][j] += dp[i & ~(1 << (j - 1))][k];
// 最后将所有能dp[1 << 21) - 1]加起来，
public class 回路计算 {public static boolean[][] canGo = new boolean[22][22];public static long[][] dp = new long[1 << 21][22];public static void main(String[] args) {// 先填表判断哪些楼之间有路for (int i = 1; i <= 21; i++) {for (int j = 1; j <= 21; j++) {if (gcd(i, j) == 1) {canGo[i][j] = true;}}}dp[1][1] = 1;for (int i = 1; i < (1 << 21); i++) {for (int j = 1; j <= 21; j++) {// j楼在i这种状态里 -- i的第j位是1if ((i & (1 << (j - 1))) > 0) {// dp[i][j] += dp[状态i中的j去掉][从那些楼可以到j]// dp[i][j] = 没有走j之前的状态能够走到j的所有可能的和for (int k = 1; k <= 21; k++) {if (canGo[k][j]) {dp[i][j] += dp[i & ~(1 << (j - 1))][k];}}}}}long res = 0;for (int i = 1; i <= 21; i++) {res += dp[(1 << 21) - 1][i];}System.out.println(res);}public static int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}
}

F题最小砝码

请添加图片描述

package JAVA12l蓝桥杯;
// 找规律题 1个砝码表示最多的权重为1 两个最多表示的权重 1 3 
//3个最多表示的权重 为 1 3 9  
//4个最多表示的权重为 1 3 9 27
//可以看出来砝码权重分别为3^i ，用循环求出最少砝码
//3 ，4个如何找，可写程序砝码可表示的数
// 分别用三层循环和四层循环加一个check（)函数，枚举当前砝码最多表示的权重为多少选最大的参数// 这题本质是考三进制，在有减，不取，加的操作下，n 个数位能表示 0～1+3 + 9 +3^n - 1的数
// 二进制在有不取，加的操作下最多能表表示0 ～ 2 ^n - 1的数
import java.util.Scanner;public class 最小砝码 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.close();int sum = 0;for (int i = 0; ; i++) {int a = (int) Math.pow(3, i);sum += a;if (sum >= n) {System.out.println(i + 1);break;}}}
}

G题左孩子右兄弟

请添加图片描述

package JAVA12l蓝桥杯;import java.util.*; 
// dp[u] 代表本子树节点的最大高度 d[u] 代表儿子
// dp[u] = max(dp[son]) + d[u]
// 这里我们可以在dfs 中维护dp[u]
//这里的dp是不是多余的？
//是的，因为每个叶节点只被访问一次public class 左孩子右兄弟 {static int N = (int)1e5 + 10,dp[] = new int[N];static int[] h = new int[N], ne = new int[N], e = new int[N], d = new int[N];static int idx = 0, ret = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);Arrays.fill(h, -1);Arrays.fill(dp, -1);int n = sc.nextInt();for(int i = 2; i <= n; ++i) {int x = sc.nextInt();add(x, i); d[x]++;}System.out.println(dfs(1));sc.close();}public static void add(int a, int b) {e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}public static int dfs(int u) {if(dp[u] != -1) return dp[u];int ret = 0;for(int i = h[u]; i != -1; i = ne[i]) {int j = e[i];ret = Math.max(ret, dfs(j));}return dp[u] = ret + d[u];} 
}

试题H：异或数列

请添加图片描述

package JAVA12l蓝桥杯;//从最高位考虑开始开始考虑
//1.若cnt为偶数，则该位所有数亦或的结果为0
//2.若当cnt为奇数时，最后一个1谁拿谁获胜
//2.1若0的个数为偶数（总数为奇数），a先手拿1必胜
//2.2若0的个数位奇数（总数为偶数），a先手拿1则b拿0，a先手拿0则b拿1b后手必胜！
//2.3特别的,需要特判cnt为1的情况先手必胜！
//3.若每一位的1个数都为偶数则平手
// 这里推荐俩题关于异或的 ：
// https://www.acwing.com/problem/content/145/ 
// https://atcoder.jp/contests/abc347/tasks/abc347_dimport java.util.Scanner;
public class 异或数列 {static final int N = 2_000_005;static int mod = 1_000_000_007;static int n, m, k, S, T;static int[] a = new int[N];public static void main(String[] args) {int tt = sc.nextInt();while (tt-- > 0)solve();sc.close();}static void solve() {n = sc.nextInt();for (int i = 1; i <= n; ++i)a[i] = sc.nextInt();for (int i = 20; i >= 0; --i) {int cnt = 0;for (int j = 1; j <= n; ++j)if (((a[j] >> i) & 1) == 1)cnt++;if (cnt % 2 == 0)continue;if (n % 2 == 1 || cnt == 1) {System.out.println(1);return;} else {System.out.println(-1);return;}}System.out.println(0);}static Scanner sc = new Scanner(System.in);
}

请添加图片描述
60% 我的评价是见好就收


import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {//这么短的，可惜超时了4个用例Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();Integer[] arr=new Integer[n];for(int i=1;i<=n;i++) {arr[i-1]=i;}int [][] arr1=new int[m][2];for(int i=0;i<m;i++) {arr1[i][0]=sc.nextInt();arr1[i][1]=sc.nextInt();}sc.close();for(int i=0;i<m;i++) {if(arr1[i][0]==0) {Arrays.sort(arr,0,arr1[i][1],(a,b)->b-a);//降序}else{Arrays.sort(arr,arr1[i][1]-1,n);//升序}}for(int i=0;i<n;i++) {System.out.print(arr[i]+" ");}}
}

100% 这是写一小时调俩多小时的，考场最好见好就收，目前码力不足以在考场上解决此问题

package JAVA12l蓝桥杯;
import java.util.*;public class 双向排序 {static final int N = 100005;static int n, m;static int[] sum0 = new int[N << 3];static int[] sum1 = new int[N << 3];static boolean[] all0 = new boolean[N << 3];static boolean[] all1 = new boolean[N << 3];static int[] a = new int[N];static int pos = 0;static void init(int l, int r, int p) {if (l == r) {sum0[p] = 0;sum1[p] = 1;} else {int mid = (l + r) >> 1, ps = p << 1;init(l, mid, ps);init(mid + 1, r, ps | 1);sum0[p] = sum0[ps] + sum0[ps | 1];sum1[p] = sum1[ps] + sum1[ps | 1];}}static void pd(int p) {if (all0[p]) {sum0[p] += sum1[p];sum1[p] = 0;all0[p] = false;all0[p << 1] = all0[p << 1 | 1] = true;all1[p << 1] = all1[p << 1 | 1] = false;} else if (all1[p]) {sum1[p] += sum0[p];sum0[p] = 0;all1[p] = false;all1[p << 1] = all1[p << 1 | 1] = true;all0[p << 1] = all0[p << 1 | 1] = false;}}static int chg1(int num, int l, int r, int p) {if (num == 0) return 0;pd(p);if (num >= sum1[p]) {all0[p] = true;return num - sum1[p];}sum1[p] -= num;sum0[p] += num;int mid = (l + r) >> 1, ps = p << 1;return chg1(chg1(num, l, mid, ps), mid + 1, r, ps | 1);}static int chg2(int num, int l, int r, int p) {if (num == 0) return 0;pd(p);if (num >= sum0[p]) {all1[p] = true;return num - sum0[p];}sum0[p] -= num;sum1[p] += num;int mid = (l + r) >> 1, ps = p << 1;return chg2(chg2(num, l, mid, ps), mid + 1, r, ps | 1);}static void upd(int l, int r, int p) {pd(p);if (l == r) {a[++pos] = sum1[p];return;}int mid = (l + r) >> 1, ps = p << 1;upd(l, mid, ps);upd(mid + 1, r, ps | 1);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();init(1, n, 1);int mid = 1;while (m-- > 0) {int p = scanner.nextInt();int q = scanner.nextInt();if (p == 0) {if (q >= mid) {chg1(q - mid + 1, 1, n, 1);mid = q + 1;}} else {if (q < mid) {chg2(mid - q, 1, n, 1);mid = q;}}}upd(1, n, 1);for (int i = n; i >= 1; --i) {if (a[i] == 0) System.out.print(i + " ");}for (int i = 1; i <= n; ++i) {if (a[i] != 0) System.out.print(i + " ");}}
}