# Google Kick Start 2019 C轮 题解

GitHub传送门

## A.Wiggle Walk

Banny has just bought a new programmable robot. Eager to test his coding skills, he has placed the robot in a grid of squares with R rows (numbered 1 to R from north to south) and C columns (numbered 1 to C from west to east). The square in row r and column c is denoted (r, c).

Initially the robot starts in the square (S_R, S_C). Banny will give the robot N instructions. Each instruction is one of N, S, E or W, instructing the robot to move one square north, south, east or west respectively.

If the robot moves into a square that it has been in before, the robot will continue moving in the same direction until it reaches a square that it has not been in before. Banny will never give the robot an instruction that will cause it to move out of the grid.

Can you help Banny determine which square the robot will finish in, after following the N instructions?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the five integers N, R, C, S_R and S_C, the number of instructions, the number of rows, the number of columns, the robot’s starting row and starting column, respectively.

Then, another line follows containing a single string of N characters; the i-th of these characters is the i-th instruction Banny gives the robot (one of N, S, E or W, as described above).

Output

For each test case, output one line containing Case #x: r c, where x is the test case number (starting from 1), r is the row the robot finishes in and c is the column the robot finishes in.

Limits

Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ R ≤ 5 × 104. 1 ≤ C ≤ 5 × 104. 1 ≤ SR ≤ R. 1 ≤ SC ≤ C. The instructions will not cause the robot to move out of the grid.

Test set 1 (Visible)

Time limit: 20 seconds. 1 ≤ N ≤ 100.

Test set 2 (Hidden)

Time limit: 60 seconds. 1 ≤ N ≤ 5 × 104.

### Solution

#### 解法

• 对于第一个WE，机器人向左走1步，向右时需要走2步
• 对于第二个WE，机器人向左走3步，向右时需要走4步
• ……

• interval插入
• interval查找
• interval合并

• 存在interval[s_1, m-1]和[m+1,e_2]，那么需要合并得到[s_1,e_2]
• 仅存在interval[s_1, m-1]或[m+1,e_2]，那么需要合并得到[s_1,m]或[m,e_2]
• 不需要合并interval，直接插入[m,m]

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

vector<unordered_map<int, int>> rowsStart, rowsEnd, colsStart, colsEnd;

void insert(int x, int y)
{
bool l = rowsEnd[x].count(y - 1), r = rowsStart[x].count(y + 1);
if (l && r)
{
int ls = rowsEnd[x][y - 1], re = rowsStart[x][y + 1];
rowsStart[x][ls] = re, rowsEnd[x][re] = ls;
}
else if (l)
{
int ls = rowsEnd[x][y - 1];
rowsStart[x][ls] = y, rowsEnd[x][y] = ls;
}
else if (r)
{
int re = rowsStart[x][y + 1];
rowsEnd[x][re] = y, rowsStart[x][y] = re;
}
else
{
rowsEnd[x][y] = rowsStart[x][y] = y;
}

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

pair<int, int> calLocation(int m, int n, int x, int y, const string &instructions)
{
rowsStart.clear();
rowsEnd.clear();
colsStart.clear();
colsEnd.clear();
rowsStart.resize(m + 1);
rowsEnd.resize(m + 1);
colsStart.resize(n + 1);
colsEnd.resize(n + 1);

rowsStart[x][y] = y;
rowsEnd[x][y] = y;
colsStart[y][x] = x;
colsEnd[y][x] = x;

for (auto item : instructions)
{
switch (item)
{
case 'E':
if (rowsStart[x].count(y + 1))
y = rowsStart[x][y + 1] + 1;
else
y++;
break;
case 'W':
if (rowsEnd[x].count(y - 1))
y = rowsEnd[x][y - 1] - 1;
else
y--;
break;
case 'S':
if (colsStart[y].count(x + 1))
x = colsStart[y][x + 1] + 1;
else
x++;
break;
case 'N':
if (colsEnd[y].count(x - 1))
x = colsEnd[y][x - 1] - 1;
else
x--;
break;
}
insert(x, y);
}
return make_pair(x, y);
}

int main()
{
int t = 0;
cin >> t;
for (int i = 1; i <= t; ++i)
{
int n, r, c, s_r, s_c;
string instructions;
cin >> n >> r >> c >> s_r >> s_c >> instructions;

auto ret = calLocation(r, c, s_r, s_c, instructions);
cout << "Case #" << i << ": " << ret.first << "  " << ret.second << endl;
}
return 0;
}


## B.Circuit Board

Arsh recently found an old rectangular circuit board that he would like to recycle. The circuit board has R rows and C columns of squares.

Each square of the circuit board has a thickness, measured in millimetres. The square in the r-th row and c-th column has thickness Vr,c. A circuit board is good if in each row, the difference between the thickest square and the least thick square is no greater than K.

Since the original circuit board might not be good, Arsh would like to find a good subcircuit board. A subcircuit board can be obtained by choosing an axis-aligned subrectangle from the original board and taking the squares in that subrectangle. Arsh would like your help in finding the number of squares in the largest good subrectangle of his original board.

Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line containing three integers R, C and K, the number of rows, the number of columns, and the maximum difference in thickness allowed in each row.

Then, there are R more lines containing C integers each. The c-th integer on the r-th line is Vr, c, the thickness of the square in the r-th row and c-th column.

Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of squares in a good subrectangle.

Limits Time limit: 15 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 50. 1 ≤ R ≤ 300. 1 ≤ C ≤ 300. 0 ≤ Vi, j ≤ 103 for all i, j.

Test set 1 (Visible) K = 0.

Test set 2 (Hidden) 0 ≤ K ≤ 103.

### Solution

#### 解法 O(cr^2) time

• 求直方图的height数组：O(r^2) time
• 利用单调栈求最大矩阵面积：O(r) time

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int largestRectangleArea(vector<int> &heights)
{
if (heights.size() == 1)
return heights;
heights.emplace_back(-1);
int n = heights.size();
int maxArea = 0, i = 0;
stack<int> indexs;
while (i < n)
{
if (indexs.empty() || heights[i] >= heights[indexs.top()])
indexs.push(i++);
else
{
int j = indexs.top();
indexs.pop();
int cur = heights[j] * (indexs.empty() ? i : (i - indexs.top() - 1));
maxArea = max(maxArea, cur);
}
}
return maxArea;
}

int cal(int m, int n, const vector<vector<int>> &inputs, int k)
{
int maxArea = 0;
vector<int> heights(m, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
int pos = i;
int curMin = inputs[j][pos], curMax = inputs[j][pos];
pos++;
while (pos < n)
{
if (inputs[j][pos] > curMax)
curMax = inputs[j][pos];
else if (inputs[j][pos] < curMin)
curMin = inputs[j][pos];
if (curMax - curMin > k)
break;
pos++;
}
heights[j] = pos - i;
}
maxArea = max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}

int main()
{
int t = 0;
cin >> t;
for (int i = 1; i <= t; ++i)
{
int r, c, k;
cin >> r >> c >> k;
vector<vector<int>> inputs(r, vector<int>(c));
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
cin >> inputs[i][j];
}
}
auto ret = cal(r, c, inputs, k);
cout << "Case #" << i << ": " << ret << endl;
}
return 0;
}


## C.Catch Some

Problem Bundle is an animal researcher and needs to go observe K dogs. She lives on a horizontal street marked at metre increments with consecutive numbers 0, 1, 2, 3 and so on. She begins in her home, which is at position 0. There are also N dogs on the street. The i-th dog is Pi metres to the right of her home on the street (multiple dogs can share the same position).

Dogs come in different colors, which are denoted by positive integers. The i-th animal is of color Ai.

If Bundle is at her home, she can change the current color of her shirt. This is important since the dogs are very shy! Bundle can only observe a dog if she is at the same position as that dog, and is wearing a shirt of the same color as the dog.

It takes Bundle one second to move one metre to the left or right on the street. It takes her no time to change shirts or observe a dog.

What is the least amount of time it will take Bundle to observe K dogs? Note that she does not have to return home after observing K dogs.

Input The first line of the input gives the number of test cases, T. T test cases follow. Each testcase begins with a line containing the two integers N and K, the number of dogs on the number line and the number of dogs Bundle needs to observe, respectively. The second line contains N integers, the i-th of which is Pi, the position of the i-th dog. The third line contains N integers, the i-th of which is Ai, the color of the i-th dog.

Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the least time Bundle needs to observe K dogs.

Limits Time limit: 30 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ K ≤ N. 1 ≤ Ai ≤ 1000. 1 ≤ Pi ≤ 105.

Test set 1 (Visible) 1 ≤ N ≤ 50.

Test set 2 (Hidden) 1 ≤ N ≤ 1000.

### Solution

#### 解法 O(N^2) time

• 对于每种颜色，Bundle只会穿一次，不会反复换
• 若Bundle观察到位置j的某颜色的狗，则在此之前的同颜色的狗也一定全部被观察
• 不考虑最后一次观察（即不回家），观察某只狗的时间为其位置乘以2（note: 在该狗之前的同颜色的狗也在该时间内被观察）

• $dp[i][j]$代表在颜色1到颜色i中，观察了j条狗所用最短时间，其中没有包含最后一次观察的颜色
• $dp[i][j]$代表在颜色1到颜色i中，观察了j条狗所用最短时间，其中包含最后一次观察的颜色

#include <algorithm>
#include <climits>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int cal(const vector<int> &positions, const vector<int> &colors, int n, int k)
{
if (k < 1)
return 0;
unordered_map<int, vector<int>> dogs;
unordered_map<int, int> colorNo;
int no = 1;
for (int i = 0; i < n; ++i)
{
if (colorNo.count(colors[i]) == 0)
colorNo[colors[i]] = no++;
}
for (int i = 0; i < n; ++i)
{
dogs[colorNo[colors[i]]].emplace_back(positions[i]);
}
int c = dogs.size();
for (int i = 1; i <= c; ++i)
{
sort(dogs[i].begin(), dogs[i].end());
}
vector<vector<vector<long long>>> dp(c + 1, vector<vector<long long>>(n + 1, vector<long long>(2, INT_MAX)));
for (int i = 1; i <= c; ++i)
{
dp[i] = 0;
dp[i] = 0;
}
for (int i = 1; i <= dogs.size(); ++i)
{
dp[i] = 2 * dogs[i - 1];
dp[i] = dogs[i - 1];
}
if (c == 1)
return dp[c][k];
for (int i = 2; i <= c; ++i)
{
for (int j = 1; j <= k; ++j)
{
for (int m = 0; m <= j && m <= dogs[i].size(); ++m)
{
dp[i][j] = min(dp[i][j], dp[i - 1][j - m] + (m == 0 ? 0 : dogs[i][m - 1] * 2));
dp[i][j] = min(dp[i][j], dp[i - 1][j - m] + (m == 0 ? 0 : dogs[i][m - 1] * 2));
dp[i][j] = min(dp[i][j], dp[i - 1][j - m] + (m == 0 ? 0 : dogs[i][m - 1]));
}
}
}
return dp[c][k];
}

int main()
{
int t = 0;
cin >> t;
for (int i = 1; i <= t; ++i)
{
int n, k;
cin >> n >> k;
vector<int> positions(n, 0), colors(n, 0);
for (int j = 0; j < n; ++j)
{
cin >> positions[j];
}
for (int j = 0; j < n; ++j)
{
cin >> colors[j];
}
cout << "Case #" << i << ": " << cal(positions, colors, n, k) << endl;
}
return 0;
}