# Google Kick Start 2020 Round F 题解
# Problem A - ATM Queue (opens new window)
一个人要用轮才能取到。所以我们可以把变为二元组,然后排序就可以得到最终的序列。
因为进行了排序,最终的时间复杂度为。
参考代码(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, x;
read(n), read(x);
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i) {
int a;
read(a);
v.emplace_back((a - 1) / x + 1, i);
}
sort(v.begin(), v.end());
for (auto vi : v)
printf("%d ", vi.second + 1);
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
# Problem B - Metal Harvest (opens new window)
首先,我们对所有区间进行排序。因为区间不会有重叠,所以我们可以逐个处理。在这个过程中,我们一直记录着当前最后一个覆盖的右端点。
对于每个区间,如果它已经被最后一个覆盖完全覆盖,我们不需要进行任何操作。否则,我们需要对一段长度为的区间进行覆盖,这需要个机器人。在添加了这些机器人后,我们将更新为。
因为进行了排序,最终的时间复杂度为。
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
using ll = int64_t;
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, k;
read(n), read(k);
vector<pair<ll, ll>> v;
for (int i = 0; i < n; ++i) {
ll s, e;
read(s), read(e);
v.emplace_back(s, e);
}
sort(v.begin(), v.end());
ll ans = 0, r = 0;
for (auto vi : v) {
if (vi.second > r) {
ll l = max(r, vi.first);
ll len = vi.second - l;
ll num = (len - 1) / k + 1;
r = l + num * k;
ans += num;
}
}
printf("%d\n", 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
# Problem C - Painters' Duel (opens new window)
博物馆的结构可以用一个有个节点,同时每个节点拥有不超过条边的无向图来表示。
最困难的是如何表示当前游戏的局面。因为最多只有个房间,一个位整数就可以满足我们的需要。我们可以用最后位记录房间的状态,位记录(后动的人)的位置,位记录(先动的人)的位置。如果一个房间已经被画过,或者正在维修,就将对应的位置为。
接下来就可以用DFS来进行求解。
每一步有三种情况:
- 可以移动。从所有可选的房间中,我们需要找到一个可以最小化下一步得分的房间(因为在下一步中和的身份会互换)。
- 无法移动,而可以移动。直接交换和,进入下一步操作。
- 和都无法移动。这是边界条件,返回。
当然,我们会进行记忆化,以避免重复的计算。
理论的时间复杂度为,这很大,但就像许多DFS问题一样,许多状态并不会被访问到,所以这一方法已经足够通过所有的测试。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
const ll mask = (1 << 10) - 1;
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;
}
ll encode(ll state, ll a, ll b) { return state | (a << 50) | (b << 40); }
class Solution {
vector<vector<int>> adj;
unordered_map<ll, int> memo;
void connect(int u, int v) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
int dfs(ll state, ll a, ll b) {
ll code = encode(state, a, b);
if (memo.count(code))
return memo[code];
bool a_can_move = false, b_can_move = false;
int lo = 100;
for (int u : adj[a]) {
if (state & (1ll << u))
continue;
a_can_move = true;
int result = dfs(state | (1ll << u), b, u);
lo = min(lo, result);
}
if (a_can_move) {
memo[code] = 1 - lo;
return memo[code];
}
for (int u : adj[b]) {
if (state & (1ll << u))
continue;
b_can_move = true;
break;
}
if (!b_can_move) {
memo[code] = 0;
return 0;
}
memo[code] = -dfs(state, b, a);
return memo[code];
}
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int s, ra, pa, rb, pb, c;
read(s), read(ra), read(pa), read(rb), read(pb), read(c);
int n = s * s;
adj = vector<vector<int>>(n + 1);
auto encode = [&](int i, int j) { return (i - 1) * (i - 1) + j; };
vector<bool> ban(n + 1);
for (int i = 0; i < c; ++i) {
int ri, pi;
read(ri), read(pi);
ban[encode(ri, pi)] = true;
}
for (int i = 1; i <= s; ++i)
for (int j = 1; j <= i * 2 - 1; ++j) {
int u = encode(i, j);
if (j < i * 2 - 1) {
int v1 = encode(i, j + 1);
if (!ban[v1])
connect(u, v1);
}
if (j % 2 == 1 && i < s) {
int v2 = encode(i + 1, j + 1);
if (!ban[v2])
connect(u, v2);
}
}
ll start = 0;
for (int i = 1; i <= n; ++i)
if (ban[i])
start |= (1ll << i);
ll a = encode(ra, pa), b = encode(rb, pb);
start |= (1ll << a);
start |= (1ll << b);
printf("%d\n", dfs(start, a, b));
}
};
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
# Problem D - Yeetzhee (opens new window)
一个关键点是:除非当前状态已经不合法,否则我们不应当重新投掷骰子(严格证明暂时无法给出)。
在这一前提之下,我们就可以进行动态规划了。和C题一样,难点在于如何表示状态,并判断一个状态是否合法。
我们可以使用前缀和来表示状态。令表示出现次数不超过次的数字的数目。比如说,如果最终的目标是(这说明)同时,则目标状态的前缀和为(因为最大的频率是,所以将数组在处截断),而初始状态的前缀和为 。对于任何一个合法的中间状态,其所有位置都不应小于目标状态的对应位置,因为在转移过程中,前缀和中的元素只会减小而不会增大。
在每次转移中,我们枚举所有当前的合法状态。对于一个状态,其中表示前缀和,表示这一状态的概率,表示到达这一状态掷骰子次数的期望,我们首先找出所有可能的更新。一个更新是合法的,当且仅当至少有一个数字出现了次(也即),同时。我们可以求出所有“好”的数字的个数。则我们在这一步掷骰子次数的期望为。而这一个更新会被记录为。
接下来,我们应用所有的更新。对于一个新状态,它的概率为所有以其为目标的更新的概率之和,而它的期望为所有以其为目标的更新的期望的加权和(权值为归一化概率,也即需要把每一个概率值除以总概率)。
时间复杂度的计算是比较困难的。但是因为的划分数大约为量级,在整个动态规划过程中并不会产生太多的状态,因此可以顺利地通过所有测试。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <map>
#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, m, k;
read(n), read(m), read(k);
vector<int> a(k);
vector<int> cnt(n + 1);
for (int i = 0; i < k; ++i)
read(a[i]), cnt[a[i]]++;
int hi = a.back();
vector<int> target(hi + 1);
target[0] = m - k;
for (int i = 1; i <= hi; ++i)
target[i] = target[i - 1] + cnt[i];
map<vector<int>, double> p, e;
vector<int> raw(hi + 1, m);
p[raw] = 1, e[raw] = 0;
for (int i = 1; i <= n; ++i) {
map<vector<int>, double> np, ne;
vector<pair<vector<int>, pair<double, double>>> updates;
for (const auto &pr : p) {
const vector<int> &state = pr.first;
double pi = pr.second;
double ei = e[state];
int good = 0;
vector<pair<int, int>> choices;
for (int j = 0; j < hi; ++j) {
if (state[j] == target[j])
continue;
int rem = state[j] - (j == 0 ? 0 : state[j - 1]);
if (!rem)
continue;
good += rem;
choices.emplace_back(j, rem);
}
for (auto choice : choices) {
int j = choice.first, c = choice.second;
vector<int> nxt(state);
nxt[j]--;
double pnxt = pi * c / good;
np[nxt] += pnxt;
updates.emplace_back(nxt, make_pair(pnxt, ei + (double)m / good));
}
}
for (const auto &update : updates) {
const vector<int> &nxt = update.first;
double pnxt = update.second.first, enxt = update.second.second;
ne[nxt] += pnxt / np[nxt] * enxt;
}
p = move(np);
e = move(ne);
}
double ans = 0;
for (auto pr : e)
ans += pr.second * p[pr.first];
printf("%.8f\n", 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