【蓝桥杯】第十六届蓝桥杯 JAVA B组记录

试题 A: 逃离高塔

在这里插入图片描述

很简单，签到题，但是需要注意精度，用int会有溢出风险

答案：202

package lanqiao.t1;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static class io {static InputStreamReader ins = new InputStreamReader(System.in);static StreamTokenizer in = new StreamTokenizer(ins);static BufferedReader br = new BufferedReader(ins);static PrintWriter out = new PrintWriter(System.out);static int readInt() throws IOException {in.nextToken();return (int) in.nval;}}public static void main(String[] args) {long n = 2025;long ans = 0;for (long i = 1; i <= n; i++) {long num = i * i * i;if (num % 10 == 3) {ans++;}}io.out.println(ans);io.out.flush();}
}

试题 B: 消失的蓝宝

在这里插入图片描述

读完一遍题，发现就是求N的最小，这里令两个日期分别为 a，b，那么就是
（n + a）%b == 0
(n+b)%a==0
第一眼想的是中国剩余定理，但是后面一看可以暴力
可以转换为求（n+a）%b == 0 ,那么（n+a）一定是 b的倍数，那么就可以转为为：
求 (kb - 9999) % a == 0 ，把k求出来直接反推就行了]

答案: 409876661809331


package lanqiao.t2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static class io {static InputStreamReader ins = new InputStreamReader(System.in);static StreamTokenizer in = new StreamTokenizer(ins);static BufferedReader br = new BufferedReader(ins);static PrintWriter out = new PrintWriter(System.out);static int readInt() throws IOException {in.nextToken();return (int) in.nval;}}public static void main(String[] args) {long x = 20250412, y = 20240413;boolean flag = true;for (int i = 9999; i <= 99999999 && flag; i++) {long num = i * y;io.out.println(num);io.out.flush();if ((num - 9999) % x == 0) {io.out.println(i);io.out.flush();break;}}io.out.flush();}}

试题 C: 电池分组

在这里插入图片描述

俺位异或，就是将两个数转成二进制，如果相同的位数都为1，那么结果这一位就是1，其余就是0
有两种想法，一种是统计二进制每一位有多少个，如果最后所有位数都是偶数，那么就是可以的，否则就不行
另外一种就是第一种的简化，如果两组的异或结果相同，那么两个再异或一定为0，所以只需要看是否异或起来结果为0就行


public class Main {static class io {static InputStreamReader ins = new InputStreamReader(System.in);static StreamTokenizer in = new StreamTokenizer(ins);static BufferedReader br = new BufferedReader(ins);static PrintWriter out = new PrintWriter(System.out);public static int readInt() throws IOException {in.nextToken();return (int) in.nval;}}public static void main(String[] args) throws IOException {int t = io.readInt();while (t-- > 0) {int n = io.readInt();int num = 0;for (int i = 1; i <= n; i++) {num = num ^ io.readInt();}if (num == 0) {io.out.println("YES");} else {io.out.println("NO");}io.out.flush();}}
}

试题 D: 魔法科考试

在这里插入图片描述

题意就是用 a数组和b数组进行两两组合，如果为质数，并且小于等于n+m，那么就是有效的，问一共有多少种，其实真正的复杂度在于如何去判断质数，如果暴力那肯定不行，所以需要预处理，用质数筛预处理就行了


public class Main {static class io {static InputStreamReader ins = new InputStreamReader(System.in);static StreamTokenizer in = new StreamTokenizer(ins);static BufferedReader br = new BufferedReader(ins);static PrintWriter out = new PrintWriter(System.out);public static int readInt() throws IOException {in.nextToken();return (int) in.nval;}}static Set<Integer> set = new TreeSet<Integer>();static {int num = 400000;int cnt = 0;int[] st = new int[num + 1];int[] prime = new int[num + 1];for (int i = 2; i <= num; i++) {if (st[i] == 0) {st[i] = 1;prime[cnt++] = i;set.add(i);}for (int j = 0; j < cnt && i * prime[j] <= num; j++) {st[i * prime[j]] = 1;if (i % prime[j] == 0) {break;}}}}public static void main(String[] args) throws IOException {int n = io.readInt(), m = io.readInt();int[] a = new int[n], b = new int[m];for (int i = 0; i < n; i++) {a[i] = io.readInt();}for (int i = 0; i < m; i++) {b[i] = io.readInt();}Arrays.sort(a);Arrays.sort(b);Set<Integer> ans = new HashSet<Integer>();for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int num = a[i] + b[j];if (num > n + m)break;if (set.contains(num)) {ans.add(num);}}}io.out.print(ans.size());io.out.flush();}
}

试题 E: 爆破

在这里插入图片描述

题意分析：将所有圆链接起来，所用的长度最小，首先想到的就是最小生成树，那么直接用prim或者kruskal算法，那么莫如何转换为算法的模型呢，如果两个圆相交，那么这两个圆心连城的边就是0，如果未相交，那么就是圆心距离-r1-r2,然后建图即可


public class Main {static class io {static InputStreamReader ins = new InputStreamReader(System.in);static StreamTokenizer in = new StreamTokenizer(ins);static BufferedReader br = new BufferedReader(ins);static PrintWriter out = new PrintWriter(System.out);public static int readInt() throws IOException {in.nextToken();return (int) in.nval;}}static class Point {int no;int x;int y;int r;public Point(int no, int x, int y, int r) {this.no = no;this.x = x;this.y = y;this.r = r;}}static int N = 5010;static class Edge implements Comparable<Edge> {int a;int b;double c;public Edge(int a, int b, double c) {this.a = a;this.b = b;this.c = c;}@Overridepublic int compareTo(Edge o) {return Double.compare(this.c, o.c);}}static int[] fa;static int find(int x) {return fa[x] == x ? fa[x] : (fa[x] = find(fa[x]));}public static void main(String[] args) throws IOException {int n = io.readInt();fa = new int[n + 1];for (int i = 1; i <= n; i++) {fa[i] = i;}Point[] points = new Point[n + 1];for (int i = 1; i <= n; i++) {points[i] = new Point(i, io.readInt(), io.readInt(), io.readInt());}int cnt = 0;Edge[] edges = new Edge[n * n];for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {Point point1 = points[i], point2 = points[j];int r1 = point1.r, r2 = point2.r;double dis = Math.sqrt((point1.x - point2.x) * (point1.x - point2.x) + (point1.y - point2.y) * (point1.y - point2.y));if (r1 + r2 < dis) {double d = dis - r1 - r2;edges[cnt++] = new Edge(i, j, d);} else {edges[cnt++] = new Edge(i, j, 0);}}}Arrays.sort(edges, 0, cnt);double ans = 0;for (int i = 0; i < cnt; i++) {Edge edge = edges[i];int f1 = find(edge.a), f2 = find(edge.b);if (f1 == f2)continue;ans += edge.c;fa[f1] = f2;}io.out.printf("%.2f", ans);io.out.flush();}
}