河南农业大学2023春蓝桥杯赛前训练第一场

A 滑板上楼梯

贪心

要求最少次数，尽量多跳三阶的，不能连续跳三阶，三阶后面一定要跟着一个一阶，相当于直接跳四阶
每次跳四阶都是两步（3、1），如果 % 4 之后，正好剩下 3 ，则直接跳一个三阶，否则要一阶一阶跳

import java.util.Scanner;public class Main {private static int N;private static long n;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextLong();long ans = 0;ans += n / 4;ans *= 2;n %= 4;if (n == 3) ans += 1;else ans += n;System.out.println(ans);}
}

B 牛牛的加法

字符串模拟加法

两个字符串分别存储两个数字，因为没有进位，直接从最长的字符串的最后，倒序处理即可，每次取和的模

/*** @author :Changersh* @date : 2023/1/14 15:44*/import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N = (int) 2e5 + 10;private static String s;private static int[] a = new int[N], b = new int[N];public static void main(String[] args) {s = sc.next();int x = s.length();for (int i = 0, j = x - 1; j >= 0; j--, i++) {a[i] = s.charAt(j) - '0';}s = sc.next();int y = s.length();for (int i = 0, j = y - 1; j >= 0; j--, i++) {b[i] = s.charAt(j) - '0';}int len = Math.max(x, y);for (int i = 0; i < len; i++) {a[i] = (a[i] + b[i]) % 10;}while (len > 0 && a[len - 1] == 0) len--;for (int i = len - 1; i >= 0; i--) out.print(a[i]);if (len == 0) out.println(0);out.close();}
}

C 石子合并

贪心

两堆合并，得到的价值是两堆价值的和，并且拿走少的那堆，求最大价值
把所有的都和最大的那个合并即可
注意：会溢出，要用 long

import java.util.*;public class Main {private static int N = (int) 2e5 + 10, n, m, k;private static int[] a;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();a = new int[n];for (int i = 0; i < n; i++) a[i] = sc.nextInt();Arrays.sort(a);long ans = 0, t = a[n - 1];for (int i = 0; i < n - 1; i++) ans += (t + a[i]);System.out.println(ans);}
}

D 黑白边

kruskal + 并查集

用 0 代表黑边，我们就按这个排序，优先选择所有的黑边，然后按大小遍历所有的边。
如果该边的两个端点不在同一个集合，就用并查集到同一个集合，cnt++，cnt记录下该集合中的点的个数
ans记录白边个数，因为黑边0，白边1，直接ans+=edge.w 即可

import java.io.*;
import java.util.*;
import java.lang.*;class Edge {public Edge(int x, int y, int w) {this.x = x;this.y = y;this.w = w;}int x, y, w;
}public class Main {private static int N = (int) 2e5 + 10, n, m;private static int[] f = new int[N];private static Edge[] edges;public static void main(String[] args) {n = sc.nextInt();m = sc.nextInt();for (int i = 0; i <= n; i++) f[i] = i; // 初始化edges = new Edge[m];for (int i = 0; i < m; i++) {int x = sc.nextInt();int y = sc.nextInt();int w = sc.nextInt();edges[i] = new Edge(x, y, w);}Arrays.sort(edges, (a, b) -> (a.w - b.w));int cnt = 0, ans = 0;for (int i = 0; i < m; i++) {int fx = find(edges[i].x);int fy = find(edges[i].y);if (fx != fy) {ans += edges[i].w;cnt++;f[fx] = fy;}if (cnt == n - 1) break;}if (cnt == n - 1) out.println(ans);else out.println(-1);out.close();}private static int find(int x) {if (x != f[x]) f[x] = find(f[x]);return f[x];}
}

E 滑板比赛

贪心

将两个人的动作值分别从小到大排序，双指针就行，计算 牛牛大于牛妹的次数

import java.util.*;public class Main {private static int N = (int) 2e5 + 10, n, m;private static int[] a;private static int[] b;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();a = new int[n];b = new int[m];for (int i = 0; i < n; i++) a[i] = sc.nextInt(); // niufor (int i = 0; i < m; i++) b[i] = sc.nextInt(); // meiArrays.sort(a);Arrays.sort(b);int ans = 0, l = 0, r = 0;while (l < n && r < m) {if (a[l] > b[r]) {ans++;l++;r++;} else {l++;}}System.out.println(ans);}
}

F 最好的宝石

不会，线段树

G GCD

线性筛求素数

求长尾 k 的最小子集，每个长为 k 的子集中，都至少有一对 x y，gcd(x,y) > 1
k 肯定大于所有素数的个数，且要包括 1，统计素数的时候把 1 也统计上，得到ans
这个是所有最大公因数是 1 的，此时只要加上一个非素数，即可满足条件

结果 = ans + 1
如果ans > n 不满足，输出 -1
否则，输出 ans

import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N = (int) 1e5 + 10, n, tot;private static int[] p = new int[N];private static boolean[] vis = new boolean[N];/*** ans = 素数个数 + 1* ans > n 时 返回 -1*/public static void main(String[] args) {n = sc.nextInt();euler();  // 筛素数int ans = 1;for (int i = 1; i <= n; i++) {if (!vis[i]) ans++; // 素数 ++}if (ans > n) out.println(-1);else out.println(ans);out.close();}private static void euler() {for (int i = 2; i <= n; i++) {if (!vis[i]) p[tot++] = i;for (int j = 0; j < tot && p[j] <= n / i; j++) {vis[i * p[j]] = true;if (i % p[j] == 0) break;}}}
}

H 第k小

堆

只存储最小的 k 个即可

import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N = (int) 1e5 + 10, n, m, k;private static PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (-(a - b)));/*** 发现只需要存储前 k 个即可* 倒序存储 只要 size > k 就一直 pop*/public static void main(String[] args) {n = sc.nextInt();m = sc.nextInt();k = sc.nextInt();for (int i = 0; i < n; i++) pq.add(sc.nextInt());int opt;while (m-- > 0) {while (pq.size() > k) pq.poll();opt = sc.nextInt();if (opt == 1) {int x = sc.nextInt();pq.add(x);}else {if (pq.size() == k) out.println(pq.peek());else out.println(-1);}}out.close();}
}

I 小游戏

dp

拿和不拿，两种状态
选择拿，只能拿前面不拿的
选择不拿，在前一个 拿和不拿之间，取一个 max

import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N = (int) 2e5 + 10, n, m;private static int[] a = new int[N];private static long[][] f = new long[N][2]; // 选 / 不选/***  dp，因为范围小，所以遍历整个范围，a[i] 存储的是 值为 i 的数的个数*/public static void main(String[] args) {n = sc.nextInt();for (int i = 0; i < n; i++) {int x = sc.nextInt();a[x]++;}for (int i = 1; i <= 200000; i++) {f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); // 不选，前一个可选可不选f[i][1] = f[i - 1][0] + a[i] * i;}out.println(Math.max(f[200000][0], f[200000][1]));;out.close();}
}

J 区间异或

二分

区间长度是 3000，可以预处理出来每个区间的异或和，放到b中
b[i] 存的是，区间长度为 i 的最大的异或和

因为要求异或和大于 x 的最小区间，则小区间的异或值如果大于大区间，则是覆盖了大区间的，我们两两取最大值，可以构造出来一个递增的序列，满足了二分答案的条件，对于每此询问，二分答案即可。

import java.io.*;
import java.util.*;
import java.lang.*;public class Main {private static int N = (int) 2e5 + 10, n, m;private static int[] a = new int[N];private static int[] b = new int[N];/*** 预处理：区间的异或和*/public static void main(String[] args) {n = sc.nextInt();m = sc.nextInt();for (int i = 1; i <= n; i++) a[i] = sc.nextInt();// 预处理for (int i = 1; i <= n; i++) {int ans = 0;for (int j = i; j <= n; j++) {ans ^= a[j];b[j - i + 1] = Math.max(b[j - i + 1], ans);}}// 取自己和前面的最大值，得到一个非递减的序列for (int i = 2; i <= n; i++) b[i] = Math.max(b[i], b[i - 1]);while (m-- > 0) {int x = sc.nextInt();if (x > b[n]) {out.println(-1);continue;}int l = 1, r = n;int ans = -1;while (l <= r) {int mid = l + ((r - l) >> 1);if (b[mid] >= x) {r = mid - 1;ans = mid;}else l = mid + 1;}out.println(ans); // 长度从 0 开始了}out.close();}
}