Google Kick Start 2019 Round C 题解

趁着今年退役，打了不少的比赛。而上个周末，更是两天打了五场比赛，结果搞得头晕眼花。

Kick Start 是知名的谷歌校招轮，去年本身水平就不足，所以瞎打了一下，最后成绩也比较不好看。而今年算是稍微有了一点实力，所以就有时间就跟着打。

这一轮的题目实际上比较经典然后偏实现一点，就让我这个代码手捡了个漏。最后补题这场也比 AB 两轮简单，所以赶快趁着新鲜写一下题解。

A. Wiggle Walk

题意

给定一个 $R\times C$ 的网格，机器人一开始在 $(S_R,S_C)$ 上，给定 $N$ 长度的程序，机器人按照程序走。过程中，如果机器人遇到了一个已经走过的格子，就会直接跳过去，一直走到某一个之前没有到过的格子为止。求机器人最终停下来的位置。

题解

有史以来最猛的 A 题？Visible Set 通过率 70%，Hidden Set 通过率只有可怜的 18%。

最直观的做法就是模拟，用一个二维的 vis 记录一下怎么走的，每一次暴力往前走即可。容易发现，最坏的情况就是 EWEWEWEWEWE 这种来回走，复杂度能到达 $\mathcal{O}(N^2)$。由于 Visible Set 中 $N\le 100$，可以过。

容易观察到的是，我们每次往某个方向走只会有两种情况：前面这格没走过，前面有一条线段。那么我们只需要针对每行每列维护这些线段即可。

如果我们把单独的一个点看做一个长度为 $1$ 的线段，那么线段合并只有三种情况：

• 左右均有线段 $(l_s,r-1)$ 以及 $(l+1, r_e)$。此时我们只需要把这条线段完整的合并成 $(l_s,r_e)$ 即可。
• 仅单侧有线段。那么把这条线段向左/右扩展 $1$ 的长度就可以了。
• 否则，插入当前点。

走的时候直接查询前面有没有线段就行，然后把走完的点插进去。

由于我们至多有 $N$ 步，所以只会有 $N$ 个状态，至多涉及 $N$ 条线段，内存上不会有问题。

这题的难点就是怎么用一个好一点的结构去存以及维护线段。我的做法是维护每条线段的起点和终点，然后起点指向终点终点指向起点，这样就好更新了。

核心的插入点的代码在下面：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void insert(int x, int y) {
  // Insert Y
  bool l = Rs[x].count(y - 1), r = Re[x].count(y + 1);
  if (l && r) {
    int ls = Rs[x][y - 1], re = Re[x][y + 1];
    Re[x][ls] = re, Rs[x][re] = ls;
  } else if (l) {
    int ls = Rs[x][y - 1];
    Rs[x][y] = ls, Re[x][ls] = y;
  } else if (r) {
    int re = Re[x][y + 1];
    Rs[x][re] = y, Re[x][y] = re;
  } else {
    Re[x][y] = Rs[x][y] = y;
  }

  l = Cs[y].count(x - 1), r = Ce[y].count(x + 1);
  if (l && r) {
    int ls = Cs[y][x - 1], re = Ce[y][x + 1];
    Ce[y][ls] = re, Cs[y][re] = ls;
  } else if (l) {
    int ls = Cs[y][x - 1];
    Cs[y][x] = ls, Ce[y][ls] = x;
  } else if (r) {
    int re = Ce[y][x + 1];
    Cs[y][re] = x, Ce[y][x] = re;
  } else {
    Ce[y][x] = Cs[y][x] = x;
  }
}

我用了一堆 map，容易观察到我们对每一步至多涉及五次查询/修改操作，所以总复杂度是 $\mathcal{O}(N\log N)$。当然，用哈希结构能优化到 $\mathcal{O}(N)$，不过既然前面的复杂度够了我就懒得改了。

B. Circuit Board

题意

给定一个 $R\times C$ 大小的矩阵，求其中最大的矩形，满足每一行的极差（最大值和最小值的差）不超过 $K$。

题解

这个题其实是个知名题目的变种题，我当时读完 A 感觉不太行然后跑来看 B 发现好像是真的就写了一发，然后就过了。

首先根据题意，我们发现每一行都是独立的，所以我们可以针对每一行来进行考虑。针对每一行，如果我们决定了列数（即决定了最右侧的起始列），那么我们可以从这一列出发找到以这一列最长的矩形使得极差满足题目要求。

有了上面的观察，我们现在把这个矩阵转置一下，那么我们之前找到的矩形变成了什么？直方图（或者叫柱状图）！而对于一个确定的直方图找最大的矩形面积已经是一个经典问题了，如果你不知道的话可以来 这里 做一下，简单的单调栈就可以了。

然后这个题就做完了。枚举每一列然后再对每一行去找最长的矩形，之后就是经典问题处理。总复杂度 $\mathcal{O}(RC^2)$。用 ST 表做 RMQ 可以优化到 $\mathcal{O}(RC\log C)$，用两个单调队列可以优化到 $\mathcal{O}(RC)$，都是很有趣的优化方法，但是复杂度够了，优化我懒就不写了（好像上面就提到过了_(:зゝ∠)_）。

C. Catch Some

题意

在一条一维沿 $x$ 轴正方向的数轴上有 $N$ 条狗，每条狗在不同的位置且是不同的颜色。Bundle 想要观察 这些狗，规则是当且仅当 Bundle 身上穿的 T 恤颜色和狗的颜色相同时，狗才会出现。Bundle 只能在家里换 T 恤，Bundle 的家在 $x=0$ 的位置。假如 Bundle 想要观察 $K$ 条狗，最短的时间是多少？其中，每移动（向左向右）消耗 $1$ 个单位时间，换 T 恤不消耗任何时间。

题解

我把 A 写完正解我就跑路去打计蒜之道了，之后剩半个小时回来读了读题感觉没思路就放了。实际上赛后看了看，就是一道不算很复杂的 dp，但是思路很有趣。

一个简单的观察是，针对每种颜色，我们只会穿一次 T 恤，而不会来回换；另一个观察是，如果我们不考虑我们最后一次观察（可以不用回家），我们观察某种颜色的狗 $k$ 只所需要的时间是这条狗的位置乘以 $2$。

这启发我们这么设计状态：$\text{dp}[i][j]$ 表示对于前 $1\sim i$ 种颜色，我们观察了 $j$ 条狗所用的最短时间。那么，转移方程实际上非常容易写出来： $$ \text{dp}[i][j] = \min_{k\le\text{len}(t_i)}\{\text{dp}[i-1][j-k]+2\times t_{i,k}\} $$ 其中 $\text{len}(t_i)$ 表示颜色为 $i$ 的狗的数目，而 $t_{i,k}$ 代表按升序排列后，颜色为 $i$ 的第 $k$ 条狗所在的位置。

上述过程是 $\mathcal{O}(N^2)$ 的。然而，我们漏了一个点：最后观察的狗的颜色。那么，我们还需要枚举最后观察的狗的颜色，根据这个颜色来修改 dp 过程，总复杂度扩展到了 $\mathcal{O}(N^3)$，只能通过 Visible Set。

现在我们来扩展状态：$\text{dp}[i][j][0/1]$ 表示对于前 $1\sim i$ 种颜色，我们观察了 $j$ 条狗所用的最短时间。其中，当第三位为 $0$ 时，代表我们 $1\sim i$ 中没有任何一种颜色是我们最后观察的，而 $1$ 则相反。

那么 $\text{dp}[i][j][0]$ 的方程不变，我们来讨论 $\text{dp}[i][j][1]$ 的方程。容易观察到，$\text{dp}[i][j][1]$ 包含两种情况：前面已经有了最后观察的颜色，和当前这种颜色是最后观察的颜色。那么，如果我们前面已经有了最后观察的颜色，当前的颜色必然是要回家的，所以是 $\text{dp}[i-1][j-k][1]+2\times t_{i,k}$；而假如前面没有遇到过最后观察的颜色，那么我们当前的颜色就不需要回家，直接观察完就可以了，所以是 $\text{dp}[i-1][j-k][0]+t_{i,k}$。

所以最后总的方程就是： $$ \text{dp}[i][j][p]=\begin{cases} \min_{k\le\text{len}(t_i)}\{\text{dp}[i-1][j-k][p]+2\times t_{i,k}\}&,p=0 \\\min\begin{cases} \min_{k\le\text{len}(t_i)}\{\text{dp}[i-1][j-k][0]+t_{i,k}\} \\\min_{k\le\text{len}(t_i)}\{\text{dp}[i-1][j-k][1]+2\times t_{i,k}\} \end{cases}&,p=1 \end{cases} $$ 答案就是 $\text{dp}[c][K][1]$，其中 $c$ 是不同的颜色的数目。

离散化一下狗的种类，然后直接 dp 就可以了。复杂度 $\mathcal{O}(N^2)$。