牛客周赛 Round 21 解题报告 | 珂学家

前言

alt

整体评价

从A题中的Baidu, 可以猜到这场有几道题来自于百度校招。

其实B题有点意思，如果把十字星的范围放大，那就可以成为一个hard题。

D题也挺意思的，大概有两种思路，一种是从左到右枚举右端点，增量累加，一种是贡献思路。

欢迎关注

珂朵莉牛客周赛专栏

珂朵莉牛客小白月赛专栏

A. 小红的Baidu

字符串s，重排后，可以等价于“Baidu”

思路，最小化表达式

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;public class Main {// Java 对 char数组，比较特殊static String expression(String s) {return s.chars().sorted().mapToObj(x -> "" + ((char)x)).reduce("", (a, b) -> a + b);}public static void main(String[] args) {// Baidu的最小表达式String p1 = expression("Baidu");Scanner sc = new Scanner(new BufferedInputStream(System.in));int t = sc.nextInt();while (t-- > 0) {String s = sc.next();String p2 = expression(s);if (p1.equals(p2)) {System.out.println("Yes");} else {System.out.println("No");}}}}

B. 小红盖章

因为十字星的影响范围小，所以可以正向模拟即可。

但是如果这题十字星的范围很大，那又该如何求解呢？

这题，可以用逆向思路，即后续操作的优先级最大，后续操作会覆盖前面的。

但是仅有逆向思维是不够的，还需要对范围遍历进行优化，这需要借助数据结构。

构建横向W个链式并查集，纵向H个链式并查集，根据逆序优先，把遍历的代价(4K)降到均摊O(1)
treeset, 均摊代价为 $O (l o g n)$

这边还是正向解法

import java.io.*;
import java.util.*;public class Main {static int[][] dirs = new int[][] {{-1, 0}, {-2, 0}, {1, 0}, {2, 0},{0, -1}, {0, -2}, {0, 1}, {0, 2}};public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int h = sc.nextInt(), w = sc.nextInt();int k = sc.nextInt();char[][] grid = new char[h][w];for (int i = 0; i < h; i++) {Arrays.fill(grid[i], '.');}// 正向操作for (int i = 0; i < k; i++) {int y = sc.nextInt() - 1, x = sc.nextInt() - 1;char g = sc.next().charAt(0);grid[y][x] = g;for (int j = 0; j < dirs.length; j++) {int y0 = y + dirs[j][0];int x0 = x + dirs[j][1];if (y0 >= 0 && y0 < h && x0 >= 0 && x0 < w) {grid[y0][x0] = g;}}}for (int i = 0; i < h; i++) {System.out.println(new String(grid[i]));}}}

逆序+链式并查集

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;public class Main {// 链式并查集static class Dsu {int n;int[] arr;public Dsu(int n) {this.n = n + 1;this.arr = new int[n + 2];Arrays.fill(arr, -1);}int leader(int u) {if (arr[u] == -1) return u;return arr[u] = leader(arr[u]);}// 向右合并void merge(int u) {int ai = leader(u);int bi = leader(ai + 1);arr[ai] = bi;}}static class Tx {int x, y;char s;public Tx(int x, int y, char s) {this.x = x;this.y = y;this.s = s;}}public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int h = sc.nextInt(), w = sc.nextInt();int k = sc.nextInt();char[][] grid = new char[h][w];for (int i = 0; i < h; i++) {Arrays.fill(grid[i], '.');}Dsu[] rows = new Dsu[h];Arrays.setAll(rows, x -> new Dsu(w));Dsu[] cols = new Dsu[w];Arrays.setAll(cols, x -> new Dsu(h));Tx[] ops = new Tx[k];for (int i = 0; i < k; i++) {int x = sc.nextInt() - 1, y = sc.nextInt() - 1;char g = sc.next().charAt(0);ops[i] = new Tx(x, y, g);}int E = 2; // 十字的边长// 逆序for (int i = k - 1; i >= 0; i--) {Tx op = ops[i];// 水平方向Dsu row = rows[op.x];int s = Math.max(op.y - E, 0);int e = Math.min(op.y + E, w - 1);while (true) {int y0 = row.leader(s);if (y0 > e) break;if (grid[op.x][y0] == '.') {grid[op.x][y0] = op.s;}row.merge(y0);}// 垂直方向Dsu col = cols[op.y];s = Math.max(op.x - E, 0);e = Math.min(op.x + E, h - 1);while (true) {int x0 = col.leader(s);if (x0 > e) break;if (grid[x0][op.y] == '.') {grid[x0][op.y] = op.s;}col.merge(x0);}}for (int i = 0; i < h; i++) {System.out.println(new String(grid[i]));}}}

C. 小红的数组修改

枚举每个位子被修改，然后计算在限制内，可以修改几种方式，能满足需求。

这边有3个限制

被改变的数，必须小于等于p
必须改变，不能为原先的值
改变后，数组和为k的倍数

假设数组累加和S

则改变后

S - arr[i] + y = k * x

取模变换

(arr[i] - S) mod k = y mod k，且0 < y <= p, y != arr[i]

求得，r = (arr[i] - S) mod k, r为非负整数

转化为 y = k * t + r, 此时 0 < y <= p, 求t的非整数解个数

因为y<=p, 因此个数为基本盘为 (p - r) / k

但是这里面有两个边界

如果r>0, 则修改方案需要额外 +1
如果arr[i] % k == r, 则需要额外 -1

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();int p = sc.nextInt();int x = sc.nextInt();long acc = 0;long[] arr = new long[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextLong();acc += arr[i];}// 枚举long res = 0;for (int i = 0; i < n; i++) {long left = (acc - arr[i]) % x;// r为对应的同余long r = (left == 0) ? 0 : (x - left);if (p >= r) {res += (p - r) / x;if (r > 0) res++; // 需要补上1个// 需要去除相等的情况if (arr[i] <= p && arr[i] % x == r) res--;}}System.out.println(res);}}

D. 括号匹配问题

大致有两种思路，但无一例外都借助stack来实现。

以往做括号相关的题时，往往会引入stack来实现，这次也是如此。

方法1：递推函数

S(i) 为以i节点为右端点的所有子区间的（）配对数

则S(i+1) 和 S(i) 的递进关系如何维护？

如果str[i+1]为’(’

那么 S(i+1)=S(i), 即配对数完全复制，但是没有新增加

如果str[i+1]为’)‘

那这个’)', 可与左侧多余的’（‘构建一个新的配对关系，那具体能贡献多少个新增呢？这又如何维护呢？

其实可以手玩一下，就能发现，在i处增加一个’(', 相当于stack push(i+1)个，而消耗匹配一个，相当于stack pop栈顶。

因此 S(i + 1) = S(i) + 2 * stack.pop()

而最终的结果为 $\sum S(i)$

import java.io.BufferedInputStream;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));char[] str = sc.next().toCharArray();int n = str.length;long res = 0;long s = 0;Deque<Integer> stack = new ArrayDeque<>();// 可能要数据结构辅助for (int i = 0; i < n; i++) {char c = str[i];if (c == '(') {stack.push((i + 1));} else if (c == ')') {if (!stack.isEmpty()) {int v = stack.pop();s += 2l * v;}}res += s;}System.out.println(res);}}

方法2：贡献法

看了下前排大佬，基本都是贡献法

就是找到一个新()匹配, 其可以在多少个区间中重复贡献。

也是基于stack

匹配的时候， $\sum stack.pop() * (n - i)$

import java.io.BufferedInputStream;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));char[] str = sc.next().toCharArray();int n = str.length;long res = 0;Deque<Integer> stack = new ArrayDeque<>();// 可能要数据结构辅助for (int i = 0; i < n; i++) {char c = str[i];if (c == '(') {stack.push((i + 1));} else if (c == ')') {if (!stack.isEmpty()) {int v = stack.pop();res += 2l * v * (n - i);
;               }}}System.out.println(res);}}