# Google Kick Start 2020 Round E 题解
# Problem A - Longest Arithmetic (opens new window)
# 题目描述
给定一个长度为()的数组,找出其中最长的由数组连续元素构成的等差数列。
# 题解
显然,前两个数字可以构成一个等差数列,所以我们从第三个数字开始。
如果当前数字和前一个数字的差,与前一个数字与再前面一个数字的差相等,就可以把当前数字接到前一个等差数列的后面,从而当前等差数列的长度增加。否则,我们需要开始一个新的等差数列,将计数器重新置为。
总时间复杂度为。
参考代码(Python)
t = int(input())
for case_num in range(1, t + 1):
n = int(input())
a = list(map(int, input().split()))
ans = 2
cnt = 2
for i in range(2, n):
if a[i] - a[i - 1] == a[i - 1] - a[i - 2]:
cnt += 1
else:
cnt = 2
ans = max(ans, cnt)
print("Case #{}: {}".format(case_num, ans))
2
3
4
5
6
7
8
9
10
11
12
13
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve(int case_num) {
int n;
read(n);
vector<int> a(n);
for (int i = 0; i < n; ++i)
read(a[i]);
int ans = 2, current = 2;
for (int i = 2; i < n; ++i) {
if (a[i] - a[i - 1] == a[i - 1] - a[i - 2])
current++;
else
current = 2;
ans = max(ans, current);
}
printf("Case #%d: %d\n", case_num, ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Problem B - High Buildings (opens new window)
# 题目描述
有座建筑物排成一排,小A从最左边往右看,小B从最右边往左看。已知建筑物的遮挡规则为:如果一个建筑物左边没有严格高于它的建筑物,它就能在左边被看到;如果右边没有严格高于它的建筑物,就能在右边被看到。小A发现自己能看到座建筑物,小B发现自己能看到座建筑物,他俩交换了一下信息,发现有座建筑物是他俩都能看到的。问:是否存在一种可能的建筑物高度设置方案(建筑物的高度必须是范围内的整数),使得他们的信息成立?如果可能,输出任意一种方案;如果不可能,输出无解。
数据范围:
# 题解
这题并不难,但是需要考虑到每一种情况,所以即使排名靠前的参赛者,也有很多人这一题吃了WA。
首先,有一种显而易见的无解情形。小A和小B共同看到的有座,那么小A单独看到的有座,小B单独看到的有座,因此,这里就有了座不同的建筑物。如果,那么显然不存在合法的情形。
还有一种容易被遗漏的无解情形。如果而,那么无论我们将最高的建筑物放在哪一个位置,小A和小B中总有一个人会看到超过一个建筑物,从而和不能同时成立。
接下来考虑有解时的布局。因为如果、互换,我们只需要将所有建筑物按倒序排列即可,所以下面我们假定。
座共同看到的建筑物,肯定是最高的,同时它们的高度应该都一样。不妨将它们的高度设为。
直观的想法是把这座连续地排列在中间,但这可能会带来问题。比如,而时,我们如果把两个连续排列,则无论怎么排列,和都会有一个人无法被满足。因此,我们考虑将这座最高的建筑物分两组排列。这样,我们正好可以把既没有被小A看到,也没有被小B看到的座放在这两部分之间,并且高度设置为。然后我们在两边分别放和独自看到的建筑物,并把高度统一设置为(这里至少需要设置为,原因在下面会解释)。这样就能够满足要求了。
有一种特殊情况是,这时我们没有办法分出两组来。我们用表示两者都没有看到的建筑物,则可能的情形有
这两种。注意,因为我们已经排除了且这一情形,所以此时必然有,也即。但是是有可能的,也就是说有可能为。这时,如果我们采用第二种方案,小A就会看到本来不应该看到的,这样就错了。因此,我们需要保证小A那一侧至少有一个,也就是要采用上面的第一种方案。但这时,我们还需要保证小B不能看见,因此我们需要有,这也就是上面要把高度设置为的原因。
所以,我们最后的放置方法为:
特别的,时,就是,但我们可以逐一验证的情形,去掉无解的情况之后,其他情形,我们的放置方法都是成立的。
当然,如果我们前面交换过和,最后还需要倒序输出。
总时间复杂度为。
参考代码(Python)
t = int(input())
for case_num in range(1, t + 1):
n, a, b, c = map(int, input().split())
if a + b - c > n or (a == b and a == c and c < min(n, 2)):
print("Case #{}: IMPOSSIBLE".format(case_num))
continue
rev = False
if a > b:
tmp = a
a = b
b = tmp
rev = True
arrangement = [n - 1] * (a - c) + [n] + [1] * (n - (a + b - c)) + \
[n] * (c - 1) + [n - 1] * (b - c)
if rev:
arrangement = arrangement[::-1]
ans = ' '.join(map(str, arrangement))
print("Case #{}: {}".format(case_num, ans))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, a, b, c;
read(n), read(a), read(b), read(c);
if (a + b - c > n || a < c || b < c) {
printf("IMPOSSIBLE\n");
return;
}
if (a == c && b == c && c < min(n, 2)) {
printf("IMPOSSIBLE\n");
return;
}
bool rev = false;
if (a > b)
swap(a, b), rev = true;
vector<int> ans;
int ra = a - c, rb = b - c;
for (int i = 0; i < ra; ++i)
ans.emplace_back(n - 1);
ans.emplace_back(n);
for (int i = 0; i < n - ra - rb - c; ++i)
ans.emplace_back(1);
for (int i = 0; i < c - 1; ++i)
ans.emplace_back(n);
for (int i = 0; i < rb; ++i)
ans.emplace_back(n - 1);
if (rev)
reverse(ans.begin(), ans.end());
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# Problem C - Toys (opens new window)
# 题目描述
编号为的()个玩具排成一圈,每个玩具有一个玩耍时间(表示小朋友会持续玩这个玩具的时间),还有一个冷却时间(表示小朋友两次玩这个玩具之间至少需要间隔的时间)。现在小朋友从号玩具开始按顺序玩起,当他第一次遇到一个还没有到冷却时间的玩具时,他就会停下来。问,最少去掉其中的几个玩具,可以让小朋友无限地玩下去,或者玩的时间最长?
# 题解
显然,第一次玩一个玩具的时候是不存在冷却时间这一说法的。对于之后的玩耍,两次玩同一个玩具之间的间隔里必然玩了其他所有玩具,所以我们不妨将冷却时间这一概念用公式进行一下表达,一个玩具能被再次玩耍的前提条件是:
移项后得到:
从这里,我们隐约可以看出,需要把作为一个重要的量来进行考虑。
假设现在所有玩具都满足,小朋友就可以无限地玩下去。而如果有玩具不满足,小朋友就必定会在再次玩那个玩具之前停止。下面,因为存在删除的情况,我们用代表当前剩余玩具的玩耍时间之和。
首先,我们考虑能否通过删除一些玩具,让小朋友能够无限玩下去。我们应该优先删除什么样的玩具呢?考虑某个玩具,它满足。如果我们不删除,而是删除了其他玩具,则会减小,而不变,因此我们不可能通过删除其他玩具使得该玩具能够满足冷却时间条件。因此,我们必须删除该玩具。所以,我们可以将这些玩具按照进行降序排列,从最大的不符合条件的开始删除,在删除的过程中同时更新,直到剩下所有玩具都满足条件(我们得到了问题的解:删除刚才那些元素可以使得小朋友无限地玩下去),或者所有玩具都被删除(不可能使得小朋友无限地玩下去)。
如果不可能使得小朋友无限玩下去,我们可以发现,小朋友最多玩同一个玩具两次。因为,如果小朋友玩了某一个玩具三次,就代表所有玩具都至少被玩了两次,说明冷却时间条件都可以被满足,可以无限玩下去,这就与假设矛盾了。
我们不妨考虑哪些玩具可以被玩两次。玩两次,意味着这一玩具需要满足冷却时间条件。从上面解决无限循环部分的经验,我们可以想到用一个大根堆维护当前被选择玩两次的玩具的。
我们从所有玩具都只玩了一次的状态开始。最初没有玩具被删除,,此时的总玩耍时间,已删除玩具的个数。
当我们考虑第个玩具时,如果,代表这一玩具当前能够满足冷却时间条件,所以我们把它加入大根堆,同时更新,并更新答案。反之,如果它不能满足,则我们不能取这一玩具,此时我们首先要从中去掉(因为我们一开始玩了一次这个玩具,而删除后就一次都不能玩了),同时要更新。因为变小了,原本大根堆中的满足冷却时间条件的玩具,可能不再满足,所以我们要从最大的开始逐个删除,在每次删除时,要从中去掉(因为在我们原本的规划中,这个玩具玩了两次,而删除后就一次都不能玩了),同时继续更新,然后继续判断大根堆中的玩具是否都满足冷却时间条件,这样循环下去,直到大根堆中所有玩具都满足条件,或大根堆为空(不再有玩了两次的玩具)。
在整个过程中,我们需要记录能够得到的最长玩耍时间和对应的删除次数。因为我们一直在删除,而没有重新添加过,所以只有在时才需要进行更新。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n;
read(n);
vector<int> e(n + 1), r(n + 1);
priority_queue<pair<int, int>> pq;
ll sum = 0;
for (int i = 1; i <= n; ++i) {
read(e[i]), read(r[i]);
pq.push({e[i] + r[i], i});
sum += e[i];
}
ll csum = sum;
while (!pq.empty()) {
int val = pq.top().first, i = pq.top().second;
if (val <= csum)
break;
else {
pq.pop();
csum -= e[i];
}
}
if (!pq.empty()) {
printf("%d INDEFINITELY\n", n - (int)pq.size());
return;
}
ll max_val = csum = sum, min_del = 0, cdel = 0, cval = sum;
for (int i = 1; i <= n; ++i) {
if (e[i] + r[i] <= csum) {
cval += e[i];
pq.push({e[i] + r[i], i});
if (cval > max_val) {
max_val = cval;
min_del = cdel;
}
} else {
csum -= e[i];
cval -= e[i];
cdel++;
while (!pq.empty() && pq.top().first > csum) {
int val = pq.top().first, j = pq.top().second;
pq.pop();
csum -= e[j];
cval -= 2 * e[j];
cdel++;
}
}
}
printf("%lld %lld\n", min_del, max_val);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# Problem D - Golden Stone (opens new window)
# 题目描述
有座城市被条无向边联通,保证任意两座城市之间相互可达。一共有种石头,每个城市可以获取其中的若干种,但没有城市能获取第种石头。另外,有种配方,每个配方最多需要三块石头作为原料(三块石头可能相同,也可能不同),可以产出一块新石头。题目保证第种石头可以被生产出来。小明每次可以带着一块石头在城市间穿梭,带着一块石头经过一条边,需要消耗一个单位的能量。小明在根据配方制作石头时,必须手头同时有所有的原料(不能有些在这个城市,另一些在另一个城市)。问小明最少需要多少能量,可以生产出一块第种石头。如果答案大于等于,则输出。
# 题解
这一题看起来非常复杂。相对容易想到的是用表示在第个城市制造(或直接获得)一块第种石头的代价,最后我们要求的就是。如果把二元组看成节点,这一问题有可能被转化为一个最短路径问题。
路径的转移有两种情况:
- 我们根据某一配方,在第个城市制造出一种新石头。这样可以转移到状态。
- 我们带着这块石头去另一个城市。这样可以转移到状态。
第二种转移很好处理,直接把当前的花费加一即可,麻烦的是如何对配方进行处理。这一块我在比赛时并没能很好地处理。比赛后,我读了前几名的代码,其中让我印象最深刻是第一名的ecnerwala (opens new window)的代码。他处理配方的方法非常漂亮。他是怎么做的呢?
我们用数组记录第种配方需要的原料数目,用二维数组记录第种石头在哪些配方里被用到了(如果在某个配方里被用了多次,就记录多次),用数组记录在第个城市已经收集了第种配方的原料的数目,用数组记录在第个城市收集第种配方的原料的成本。
关键点在于,在Dijkstra算法求最短路径的过程中,每一个状态只会被松弛一次。所以说,我们可以在松弛时,根据,将第种石头加入到对应的和中。如果当前,这就表示第种配方已经具备了在城市进行制作的条件,我们就可以尝试进行第一种转移。因为这是第一次该配方能够在该城市被制作(在此之前还未被满足),所以Dijkstra算法的性质可以保证,我们的这一方案,一定是在城市制作第种配方的最优方案。
这一算法的总时间复杂度为。
下面的代码是我比赛后参考ecnerwala (opens new window)的代码重写的版本。
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e12;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
int n, m, s, r;
int hash(int si, int ni) const { return si * (n + 1) + ni; };
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
read(n), read(m), read(s), read(r);
vector<vector<int>> adj(n + 1), needed_by_recipe(s + 1);
vector<vector<ll>> stone_cost(s + 1, vector<ll>(n + 1, INF)),
recipe_cost(r, vector<ll>(n + 1));
vector<vector<int>> ingredients_got(r, vector<int>(n + 1));
vector<int> ingredients_need(r), product(r);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
for (int i = 0; i < m; ++i) {
int u, v;
read(u), read(v);
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
for (int city = 1; city <= n; ++city) {
int stone_num;
read(stone_num);
for (int j = 0; j < stone_num; ++j) {
int stone;
read(stone);
stone_cost[stone][city] = 0;
pq.push({0, hash(stone, city)});
}
}
for (int i = 0; i < r; ++i) {
read(ingredients_need[i]);
for (int j = 0; j < ingredients_need[i]; ++j) {
int ingredient;
read(ingredient);
needed_by_recipe[ingredient].emplace_back(i);
}
read(product[i]);
}
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
ll c = top.first;
int u = top.second;
int stone = u / (n + 1), city = u % (n + 1);
if (c != stone_cost[stone][city])
continue;
for (int recipe : needed_by_recipe[stone]) {
ingredients_got[recipe][city]++;
ll nc = recipe_cost[recipe][city] += c;
if (ingredients_got[recipe][city] == ingredients_need[recipe]) {
if (nc < stone_cost[product[recipe]][city]) {
stone_cost[product[recipe]][city] = nc;
pq.push({nc, hash(product[recipe], city)});
}
}
}
for (int nxt : adj[city]) {
if (c + 1 < stone_cost[stone][nxt]) {
stone_cost[stone][nxt] = c + 1;
pq.push({c + 1, hash(stone, nxt)});
}
}
}
ll ans = *min_element(stone_cost[1].begin(), stone_cost[1].end());
printf("%lld\n", ans == INF ? -1 : ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
比赛时,我使用的是另一种思路。在每次迭代中,遍历所有的配方,如果某一配方当前可以被制作,就尝试在每一个城市制作它,如果更新了之前的状态,就再尝试把这一配方的产物搬运到其他所有城市,更新在其他城市获取这一产物的代价。如果某次迭代中,没有任何状态被更新,就终止迭代。
这种方法的时间复杂度我无法准确给出,但肯定是比较高的。可能比赛的评测数据并没有特别刁钻的,所以最后勉强通过了。姑且也放在这里,供大家批评。
参考代码(C++,我自己比赛时的解答)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e12;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
struct Recipe {
vector<int> in;
int out;
};
class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, m, s, r;
read(n), read(m), read(s), read(r);
vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF)),
cost(s + 1, vector<ll>(n + 1, INF));
vector<ll> lo(s + 1, INF);
vector<Recipe> recipes;
for (int i = 0; i < m; ++i) {
int u, v;
read(u), read(v);
dist[u][v] = dist[v][u] = 1;
}
for (int k = 1; k <= n; ++k) {
dist[k][k] = 0;
for (int i = 1; i <= n; ++i) {
if (i == k)
continue;
for (int j = 1; j <= n; ++j) {
if (j == k || j == i)
continue;
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int i = 1; i <= n; ++i) {
int c;
read(c);
for (int j = 0; j < c; ++j) {
int si;
read(si);
lo[si] = 0;
cost[si][i] = 0;
for (int k = 1; k <= n; ++k)
cost[si][k] = min(cost[si][k], dist[i][k]);
}
}
for (int i = 0; i < r; ++i) {
int k;
read(k);
vector<int> v(k);
for (int j = 0; j < k; ++j)
read(v[j]);
sort(v.begin(), v.end());
int result;
read(result);
recipes.push_back({v, result});
}
bool changed = true;
auto valid = [&](Recipe &r) {
for (int i : r.in)
if (lo[i] == INF)
return false;
return true;
};
while (changed) {
changed = false;
for (auto &recipe : recipes) {
if (!valid(recipe))
continue;
for (int i = 1; i <= n; ++i) {
ll c = 0;
for (int si : recipe.in)
c += cost[si][i];
if (c < cost[recipe.out][i]) {
changed = true;
lo[recipe.out] = min(lo[recipe.out], c);
cost[recipe.out][i] = c;
for (int j = 1; j <= n; ++j)
cost[recipe.out][j] = min(cost[recipe.out][j], c + dist[i][j]);
}
}
}
}
printf("%lld\n", lo[1] == INF ? -1 : lo[1]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120