# # Google Kick Start 2019 Round D 题解

## # Problem A - X or What? (opens new window)

### # 题目描述

$N$个数，进行$Q$次单点修改，在每次修改后，给出当前异或和的二进制表示中$1$的个数为偶数的最长子数组的长度。

### # 题解

#include <bitset>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

inline int odd(int x) { return bitset<12>(x).count() % 2; }

int main() {
int t;
cin >> t;
for (int case_num = 1; case_num <= t; ++case_num) {
cout << "Case #" << case_num << ": ";
int n, q;
cin >> n >> q;
vector<int> a(n);
set<int> odds;
int tot = 0;
for (int i = 0; i < n; ++i) {
int ai;
cin >> ai;
a[i] = odd(ai);
tot += a[i];
if (a[i])
odds.insert(i);
}
for (int i = 0; i < q; ++i) {
int p, v;
cin >> p >> v;
int new_val = odd(v);
tot += new_val - a[p];
if (a[p])
odds.erase(p);
if (new_val)
odds.insert(p);
a[p] = new_val;
int ans = tot % 2 == 0 ? n : max(*odds.rbegin(), n - *odds.begin() - 1);
cout << ans << " ";
}
cout << endl;
}
}

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
31
32
33
34
35
36
37
38
39
40
41
42
43

## # Problem B - Latest Guests (opens new window)

### # 题目描述

$N$座塔楼围成环形，$G$个游客各自从某一塔楼出发，有一些人按照顺时针行进，另一些人按照逆时针行进。所有人的速度都一样，所有塔楼之间距离都相等，每过一分钟，所有人都会到达其方向上的下一座塔楼。每个塔楼的守卫只会记住最后一次来访的客人，如果最后一次是多人来访，他会记住所有的客人。求过了$M$分钟后，每个客人被多少个守卫记住。

### # 题解

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int main() {
int t;
cin >> t;
for (int case_num = 1; case_num <= t; ++case_num) {
cout << "Case #" << case_num << ": ";
int n, g, m;
cin >> n >> g >> m;
map<int, int> C, A;
vector<pair<int, int>> ct(n, make_pair(-1, -1)), at(n, make_pair(-1, -1));
vector<pair<int, char>> p;
for (int i = 0; i < g; ++i) {
int hi;
char c;
cin >> hi >> c;
hi--;
p.emplace_back(hi, c);
if (c == 'C')
C[hi] = 0;
else
A[hi] = 0;
}

// Handle clockwise
int pos = -1;
for (auto pc : C) {
int pe = (pc.first + m) % n;
ct[pe] = {pc.first, m};
if (pos == -1)
pos = pe;
}
if (pos != -1) {
int lp = ct[pos].first, lt = ct[pos].second;
for (int i = 1; i < n; ++i) {
lt--, pos--;
if (pos < 0)
pos = n - 1;
if (lt > ct[pos].second)
ct[pos] = make_pair(lp, lt);
else
lp = ct[pos].first, lt = ct[pos].second;
}
}

// Handle anticlockwise
pos = -1;
for (auto pc : A) {
int pe = (pc.first - m) % n;
if (pe < 0)
pe += n;
at[pe] = {pc.first, m};
if (pos == -1)
pos = pe;
}
if (pos != -1) {
int lp = at[pos].first, lt = at[pos].second;
for (int i = 1; i < n; ++i) {
lt--, pos++;
if (pos >= n)
pos = 0;
if (lt > at[pos].second)
at[pos] = make_pair(lp, lt);
else
lp = at[pos].first, lt = at[pos].second;
}
}

// Compare the latest clockwise guest and anticlockwise guest.
for (int i = 0; i < n; ++i) {
if (at[i].second > ct[i].second)
A[at[i].first]++;
else if (at[i].second < ct[i].second)
C[ct[i].first]++;
else {
A[at[i].first]++;
C[ct[i].first]++;
}
}
for (int i = 0; i < g; ++i) {
if (p[i].second == 'C')
cout << C[p[i].first] << " ";
else
cout << A[p[i].first] << " ";
}
cout << endl;
}
}
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
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

## # Problem C - Food Stalls (opens new window)

### # 题解

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
int t;
cin >> t;
for (int case_num = 1; case_num <= t; ++case_num) {
cout << "Case #" << case_num << ": ";
int k, n;
cin >> k >> n;
k++;
vector<pair<int, int>> pos(n);
for (int i = 0; i < n; ++i)
cin >> pos[i].first;
for (int i = 0; i < n; ++i)
cin >> pos[i].second;
sort(pos.begin(), pos.end());
ll ans = 1e18;
int L = k / 2, R = k - k / 2 - 1;
ll lsum = 0, rsum = 0;
set<pair<ll, int>> lheap, rheap, r2;
vector<ll> c(n);
for (int i = 0; i < L; ++i) {
ll cost = pos[i].second + pos[L].first - pos[i].first;
c[i] = cost;
lheap.emplace(cost, i);
lsum += cost;
}
for (int i = L + 1; i < n; ++i) {
ll cost = pos[i].second + pos[i].first - pos[L].first;
c[i] = cost;
rheap.emplace(cost, i);
rsum += cost;
if (rheap.size() > R) {
r2.insert(*rheap.rbegin());
rsum -= rheap.rbegin()->first;
rheap.erase(*rheap.rbegin());
}
}
ll extra = 0;
for (int mid = L; mid + R < n; ++mid) {
ans = min(ans, lsum + extra * (L - R) + rsum + pos[mid].second);
if (mid + 1 < n) {
lheap.emplace(pos[mid].second - extra, mid);
lsum += pos[mid].second - extra;
lsum -= lheap.rbegin()->first;
lheap.erase(*lheap.rbegin());
if (rheap.count(make_pair(c[mid + 1], mid + 1))) {
rheap.erase(make_pair(c[mid + 1], mid + 1));
rsum -= c[mid + 1];
rheap.insert(*r2.begin());
rsum += r2.begin()->first;
r2.erase(*r2.begin());
} else {
r2.erase(make_pair(c[mid + 1], mid + 1));
}
extra += pos[mid + 1].first - pos[mid].first;
}
}
cout << ans << endl;
}
}

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
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