蓝桥杯第 1 场算法双周赛解题报告

本文主要是介绍蓝桥杯第 1 场算法双周赛解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

整体评价

这是蓝桥云课的第一场公开周赛，还是挺用心的。因为第一场比赛，整体比赛难度还是有所放低。

A. 三带一

Q: 四张手牌，是否能构成3带1的牌型

签到题，有多种思路

最小表示式

排序后，一定呈现 AAAB, 或者 ABBB 型的牌，注意 A != B

计数统计

一定存在计数为3和计数为1的key，注意只有4张牌

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int t = sc.nextInt();while (t-- > 0) {char[] str = sc.next().toCharArray();Map<Integer, Integer> hash = new HashMap<>();for (char c: str) {hash.merge((int)c, 1, Integer::sum);}// 同时包含计数1和计数3，只有4张牌，则一定是3带1boolean res = hash.values().contains(1) && hash.values().contains(3);System.out.println(res ? "Yes" : "No");}}}

B. 数树数

Q: 满二叉树，根据指令左右向下，求最后的节点代表的数值

找规律的题，其实可以手玩一下，就能发现其中的窍门

其实用数组构建的堆，线段树等，都有类似的规律，父节点和子节点之间，其索引值倍增，偏差1

这题的规律为

向左， $a_{i+1}=2 * a_i - 1$

向右 $a_{i+1}=2 * a_i$

自顶向下模拟即可

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt();int q = sc.nextInt();for (int i = 0; i < q; i++) {char[] cmd = sc.next().toCharArray();long res = 1;for (char c: cmd) {if (c == 'L') {res = 2 * res - 1;} else {res = 2 * res;}}System.out.println(res);}}}

C. 分组

Q: 就是把一个数组分成k组，使得最大的一组高度差最小。

这种最大最小的问题，往往是二分的解法，一般百试不爽，^_^

可以先排序，然后在尝试分组

二分容易，但是核心的check逻辑，该如何组织呢？

假定一个高度差h，然后从左到右贪心，使得每一组成员越多越好，如果最终的组数g<=k, 说明这个高度差满足需求，反之则不行。

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;public class Main {static boolean check(int[] arr, int m, int k) {int i = 0;int tk = 0;while (i < arr.length) {int j = i + 1;tk++;while (j < arr.length && arr[j] - arr[i] <= m) {j++;}i = j;}return tk <= k;}public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt(), k = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}Arrays.sort(arr);int l = 0, r = arr[n - 1] - arr[0];while (l <= r) {int m = l + (r - l) / 2;if (check(arr, m, k)) {r = m - 1;} else {l = m + 1;}}System.out.println(l);}}

D. 健身

Q: 就是在几个离散的时间区间内，安排一些健身活动(某种健身活动无限续杯)，需要完整，求最大的收益和。

健身活动(无数量限制)，因此每个区间的最优解彼此独立，互不影响，而且总和就是最大的收益和。

那一个区间，如何求解呢？

本质还是一个

有容量上限的完全背包问题

所以这题的思路是

拆解离散的可用时间片段
完全背包(跑一次就行)

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt(), m = sc.nextInt(), x = sc.nextInt();int[][] ws = new int[m][2];List<Integer> arr = new ArrayList<>();for (int i = 0; i < x; i++) {int b = sc.nextInt();arr.add(b);}for (int i= 0; i < m; i++) {ws[i][0] = sc.nextInt();ws[i][1] = sc.nextInt();}// 抽取离散的空闲时间段Collections.sort(arr);List<Integer> empty = new ArrayList<>();for (int i = 0; i < arr.size() - 1; i++) {int v = arr.get(i + 1) - arr.get(i) - 1;if (v > 0) empty.add(v);}// 注意头尾if (arr.size() > 0) {if (arr.get(0) > 1) empty.add(arr.get(0) - 1);if (arr.get(arr.size() - 1) < n) empty.add(n - arr.get(arr.size() - 1));}// 完全背包long[] dp = new long[n + 1];for (int i = 0; i < m; i++) {int s = 1 << ws[i][0];for (int j = 0; j + s <= n; j++) {dp[j + s] = Math.max(dp[j + s], dp[j] + ws[i][1]);}}// 再来一个前缀预处理for (int i = 1; i <= n; i++) {dp[i] = Math.max(dp[i], dp[i - 1]);}long sum = 0;for (int e: empty) {sum += dp[e];}System.out.println(sum);}}

E. 契合匹配

Q: 求两个字符串，通过移动，是否可以匹配(相等)

当然这边的匹配，是大写字母匹配小写字母，稍微饶了一下。

这是道很典的字符串板子题

KMP
Z函数
字符串Hash

这些方法都可以，而且都是 $O(n)$ 的，不过这里可向左，也可以向右，所以这边需要特别注意下。

这边使用了字符串hash，而且这题单hash可以过，^_^.

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt();char[] str1 = sc.next().toCharArray();char[] str2 = sc.next().toCharArray();for (int i = 0; i < n; i++) {if (str2[i] >= 'a' && str2[i] <= 'z') {str2[i] = (char)(str2[i] - 'a' + 'A');} else {str2[i] = (char)(str2[i] - 'A' + 'a');}}long mod = (long)1e9 + 7;StringHash hash1 = new StringHash(new String(str1), 13, mod);StringHash hash2 = new StringHash(new String(str2), 13, mod);int inf = Integer.MAX_VALUE / 10;int ans = inf;long h1 = hash1.query(0, n - 1);if (h1 == hash2.query(0, n - 1)) {ans = 0;} else {for (int i = 0; i < n - 1; i++) {long h2 = hash2.rotate(i);if (h1 == h2) {ans = Math.min(ans, Math.min((i + 1), n - (i + 1)));}}}if (ans == inf) {System.out.println("No");} else {System.out.println("Yes");System.out.println(ans);}}static class StringHash {char[] str;long p, mod;int n;long[] pre; // hash前缀和long[] pow; // p的幂次public StringHash(String s, int p, long mod) {this.str = s.toCharArray();this.p = p;this.mod = mod;this.n = str.length;pre = new long[n + 1];pow = new long[n + 1];pow[0] = 1;for (int i = 1; i <= n; i++) {pow[i] = pow[i - 1] * p % mod;}for (int i = 0; i < str.length; i++) {pre[i + 1] = (pre[i] * p % mod + str[i]) % mod;}}long query(int l, int r) {long res = pre[r + 1] - pre[l] * pow[r - l + 1] % mod;return (res % mod + mod) % mod;}long rotate(int l) {if (l < 0 || l >= str.length - 1) {return query(0, str.length - 1);} else {long h1 = query(0, l);long h2 = query(l + 1, str.length - 1);return (h2 * pow[l + 1] % mod + h1) % mod;}}static long evaluate(String s, int p, long mod) {long h = 0;for (char c: s.toCharArray()) {h = (h * p % mod + c) % mod;}return h;}}}

F. 奇怪的线段

Q: 给定一些区间集合，查询a, b两点，其a在区间，b不在。求集合中，有多少区间符合条件？

区间的问题，可以往二维偏序的解法靠拢

因为查询很多，可以借助离线解法，把查询和被查询区间整合到一起。

这边提供一个离线解法，构建操作序列，并借助树状数组来统计

假设 $a < b$

对于查询(a, b)，构建元组

(1, a, b, i), type=1，表示查询

对于区间(x, y), 则构建两个元组

(0, x, y, _), type=0，表示添加区间

(2, y, _, _), type=2, 表示删除区间

按左端点作为一级排序，按操作类型作为二级排序

然后引入树状数组(需要离散化映射)，维护右端点的计数

这样天然保证了包含a点，而不包含b点，用树状数组范围查询一下即可。

而对于 $a > b$ 的情况

需要从右端点的切入并排序

注：这个解法，码量还是有点大，而且必须加快读。更好的解法，见官解：差分+容斥原理

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;public class Main {static void handle1(int[][] intervals, int[][] queries, int[] res) {Set<Integer> range = new TreeSet<>();int n = intervals.length;List<int[]> ops = new ArrayList<>();for (int i = 0; i < n; i++) {ops.add(new int[] {intervals[i][0], intervals[i][1], 0, i});ops.add(new int[] {intervals[i][1], -1, 2, i});range.add(intervals[i][1]);}// 离线, 在线int q = queries.length;for (int i = 0; i < q; i++) {if (queries[i][0] < queries[i][1]) {ops.add(new int[]{queries[i][0], queries[i][1], 1, i});range.add(queries[i][1]);}}int ptr = 0;Map<Integer, Integer> idMap = new HashMap<>();for (int k: range) {idMap.put(k, ++ptr);}int m = idMap.size();BIT bit = new BIT(m);Collections.sort(ops, Comparator.comparing((int[] x) -> x[0]).thenComparingInt(x -> x[2]));for (int[] e: ops) {int p = e[2];if (p == 0) {bit.update(idMap.get(e[1]), 1);} else if (p == 1) {int cnt = bit.query(idMap.get(e[1]) - 1);res[e[3]] = cnt;} else {bit.update(idMap.get(e[0]), -1);}}}static void handle2(int[][] intervals, int[][] queries, int[] res) {Set<Integer> range = new TreeSet<>();int n = intervals.length;List<int[]> ops = new ArrayList<>();for (int i = 0; i < n; i++) {ops.add(new int[] {intervals[i][1], intervals[i][0], 0, i});ops.add(new int[] {intervals[i][0], -1, 2, i});range.add(intervals[i][0]);}// 离线, 在线int q = queries.length;for (int i = 0; i < q; i++) {if (queries[i][0] > queries[i][1]) {ops.add(new int[]{queries[i][0], queries[i][1], 1, i});range.add(queries[i][1]);}}int ptr = 0;Map<Integer, Integer> idMap = new HashMap<>();for (int k: range) {idMap.put(k, ++ptr);}int m = idMap.size();BIT bit = new BIT(m);Collections.sort(ops, Comparator.comparing((int[] x) -> -x[0]).thenComparingInt(x -> x[2]));for (int[] e: ops) {int p = e[2];if (p == 0) {bit.update(idMap.get(e[1]), 1);} else if (p == 1) {int cnt = bit.query(m) - bit.query(idMap.get(e[1]));res[e[3]] = cnt;} else {bit.update(idMap.get(e[0]), -1);}}}public static void main(String[] args) {AReader sc = new AReader();int n = sc.nextInt(), q= sc.nextInt();int[][] intervals = new int[n][2];for (int i = 0; i < n; i++) {intervals[i][0] = sc.nextInt();intervals[i][1] = sc.nextInt();}// 离线, 在线int[][] queries = new int[q][2];for (int i = 0; i < q; i++) {queries[i][0] = sc.nextInt();queries[i][1] = sc.nextInt();}// 离散化 + 离线计算int[] res = new int[q];handle1(intervals, queries, res);handle2(intervals, queries, res);System.out.println(Arrays.stream(res).mapToObj(String::valueOf).collect(Collectors.joining("\n")));}static class BIT {int n;int[] arr;public BIT(int n) {this.n = n;this.arr = new int[n + 1];}void update(int p, int d) {while (p <= n) {this.arr[p] += d;p += p & -p;}}int query(int p) {int r = 0;while (p > 0) {r += arr[p];p -= p&-p;}return r;}}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }// 若需要nextDouble等方法，请自行调用Double.parseDouble包装}}