Google Kickstart 2019 Round C 题解
2019-06-19 本文已影响0人
舒也ella
1. Wiggle Walk
Problem：
在一个(R, C)矩阵，机器人从(SR, SC)出发，根据给定的指令 N, S, E or W沿指定的方向走一步，如果当前格子已经访问过则沿同一方向直至走到未访问过的位置，所给数据保证机器人不会走出边界，求机器人最终位置
Solution：
小数据的数据范围为1 ≤ N ≤ 100，大数据的数据范围为1 ≤ N ≤ 5 × 10^4。首先尝试暴力的方法，每走到一个位置判断该位置是否已经访问过。由于1 ≤ R ≤ 5 × 10^4, 1 ≤ C ≤ 5 × 10^4，因此开全局R*C的二维数组内存会爆掉，我们转而使用set存放每次已经访问的位置pair，set每次查找操作的时间复杂度为，但每次查找最坏情况下可能走过整个矩阵的长或宽，因此总的时间复杂度为
，对于大数据会超时。
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int, int> pii;
int r, c;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
int sr, sc;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
for (int t = 1; t <= T; ++t) {
int n;
cin >> n >> r >> c >> sr >> sc;
set<pii> visited;
visited.emplace(pii(sr, sc));
for (int i = 0; i < n; ++i) {
char x;
cin >> x;
set<pii>::iterator it;
if (x == 'N') {
do {
sr += dy[0];
sc += dx[0];
it = visited.find(pii(sr, sc));
} while (it != visited.end());
} else if (x == 'S') {
do {
sr += dy[1];
sc += dx[1];
it = visited.find(pii(sr, sc));
} while (it != visited.end());
} else if (x == 'E') {
do {
sr += dy[2];
sc += dx[2];
it = visited.find(pii(sr, sc));
} while (it != visited.end());
} else if (x == 'W') {
do {
sr += dy[3];
sc += dx[3];
it = visited.find(pii(sr, sc));
} while (it != visited.end());
}
visited.emplace(pii(sr, sc));
}
cout << "Case #" << t << ": " << sr << " " << sc <<endl;
}
return 0;
}
要对上述代码进行优化，我们可以考虑消去每次查找的那个循环使得总的时间复杂度降低为，这样需要将每个已被访问的独立的点存放为每个已被访问的连续区间，这样我们的代码需要支持两类操作：一类是当查询一个新点位置时，直接确定最终走到的位置，即判断该位置沿指定方向上是否存在相邻的已访问的区间；另一类是当插入一个新点之后，更新相关的区间，可能是合并入现有的一个区间，也可能需要合并现有的两个区间。
// wiggleWalk.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int, int> pii;
const int N = 110, INF = 1e9;
int r, c;
int sr, sc;
set<pii> row[N], col[N];
int move(set<pii> &segs, int x, int dir) {
auto i = segs.lower_bound({ x, x });
if (dir == 1) {
if (x == (i->first - 1))
return i->second + 1;
return x + 1;
}
else if (dir == -1) {
i--;
if (x == (i->second + 1))
return i->first - 1;
return x - 1;
}
return -1;
}
void insert(set<pii> &segs, int x) {
auto i = segs.lower_bound({ x, x });
auto j = i--;
bool left = i->second == x - 1;
bool right = j->first == x + 1;
if (left && right) {
segs.insert({ i->first, j->second });
segs.erase(i);
segs.erase(j);
}
else if (left) {
segs.insert({ i->first, x });
segs.erase(i);
}
else if (right) {
segs.insert({ x, j->second });
segs.erase(j);
}
else {
segs.insert({ x, x });
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
for (int t = 1; t <= T; ++t) {
int n;
cin >> n >> r >> c >> sr >> sc;
for (int i = 1; i <= r; ++i) {
row[i].clear();
row[i].insert({ -INF, -INF });
row[i].insert({ INF, INF });
}
for (int i = 1; i <= c; ++i) {
col[i].clear();
col[i].insert({ -INF, -INF });
col[i].insert({ INF, INF });
}
int dr, dc;
for (int i = 0; i < n; ++i) {
char x;
cin >> x;
if (x == 'N') {
dc = sc;
dr = move(col[sc], sr, -1);
}
else if (x == 'S') {
dc = sc;
dr = move(col[sc], sr, 1);
}
else if (x == 'E') {
dr = sr;
dc = move(row[sr], sc, 1);
}
else if (x == 'W') {
dr = sr;
dc = move(row[sr], sc, -1);
}
insert(row[sr], sc);
insert(col[sc], sr);
sr = dr;
sc = dc;
}
cout << "Case #" << t << ": " << sr << " " << sc << endl;
}
return 0;
}
注意上述代码中：每次清空对应行列的set数组并插入哨兵以避免边界情况的处理；insert时传入的是原始的位置而不是下一步的位置注意区分。类似题目有Leetcode 352 维护一系列不相交的区间。
2. Circuit Board
Problem：
给定大小为（R,C）的矩阵，求出一个最大子矩阵使得矩阵内的每行的元素值差距不超过K
Solution：
- 由于数据范围在300内，因此
的算法可过，采用暴力枚举即可。如何用三层循环枚举所有可能的子矩阵情况：首先枚举子矩阵的宽度len，然后对每个固定的宽度枚举列的起始位置，最后一层枚举最长的连续满足条件的行数。这样问题可以转换为如何在最后一层循环中用O(1)的时间判断出可行的最大行数。
要在O(1)的时间判断出可行的最大行数，可以在三重循环遍历的同时维护两个二维数据 minv[i,j]表示从(i,j)向右延伸宽度len的区间内的最小值，maxv[i,j]表示从(i,j)向右延伸宽度len的区间内的最大值。代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n, m;
int a[N][N];
int minv[N][N], maxv[N][N];
int main() {
int T;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
int k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
minv[i][j] = maxv[i][j] = a[i][j];
}
}
int res = n; // len == 1
for (int len = 2; len <= m; ++len) {
for (int i = 1; i + len - 1 <= m; ++i) {
for (int j = 1, s = 0; j <= n; ++j) {
// update maxv & minv on this line
int &mn = minv[j][i], &mx = maxv[j][i];
mn = min(mn, a[j][i + len - 1]);
mx = max(mx, a[j][i + len - 1]);
if (mx - mn <= k) {
s++;
res = max(res, s * len);
} else {
s = 0;
}
}
}
}
printf("Case #%d: %d\n", t, res);
}
}
注意上述代码中的引用，实现对minv和maxv的修改。
-
使用单调栈可以将算法时间复杂度优化到
。具体方法对矩阵每一个点求出其向左延伸的最大长度，预处理时间
。
-
分组背包
