Kickstart Round D 2019 题解

1. X or What?

1.1 题目链接

[Kickstart Round D 2019 A. X or What?]

1.2 题意描述

Problem A. X or What

1.3 解题思路

xor-even 是指在二进制表示中,1的个数为偶数。

可以发现:两个数的异或和是不是 xor-even 跟这两个数本身是不是 xor-even 有关。换言之,如果两个数都有偶数个1或者都有奇数个1,那么他们异或和的二进制表示一定是偶数个1;当一个数有偶数个1,另一个数有奇数个1,那么异或和的二进制表示中一定是奇数个1。

所以,只需要维护 最左、最右的二进制表示中有奇数个1的数。

1.4 参考代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const long double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 1e5+5;
int T, N, Q, ans, A[MAXN];

int main() {
#ifdef __LOCAL_WONZY__
freopen("input-1.txt", "r", stdin);
#endif
cin >> T;
for(int cas = 1; cas <= T; ++cas) {
scanf("%d %d", &N, &Q);
set<int> pset;
int cnt = 0;
for(int i = 0; i < N; ++i) {
scanf("%d", &A[i]);
A[i] = __builtin_popcount(A[i]) & 1;
if(A[i]) pset.insert(i), ++cnt;
}
printf("Case #%d:", cas);
while(Q--) {
int p, v; scanf("%d %d", &p, &v);
v = __builtin_popcount(v) & 1;
if(A[p]) --cnt, pset.erase(p);
if(v) pset.insert(p), ++cnt;
A[p] = v;
if(cnt & 1) printf(" %d", max(N-(*pset.begin())-1, (*pset.rbegin())));
else printf(" %d", N);
}
printf("\n");
}
return 0;
}

2. Latest Guests

2.1 题目链接

[Kickstart Round D 2019 B. Latest Guests]

2.2 题意描述

Problem B. Latest Guests

2.3 解题思路

题目中,每个位置都只能记住最后一次被访问的客人(们)。

先求出每个客人,在 $M$ 时刻会到达哪个位置,然后从终点往起点移动,就可以把问题转化为每个位置只记住最先访问的客人。然后一次BFS,就可以求出每个位置最先被谁访问了。

2.4 参考代码

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
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 1e5+5;
int T, N, G, M, H[MAXN], ans[MAXN];
char op[5];
struct QNode {
int x, s, step;
char dir;
QNode() {}
QNode(int _x, int _s, int _step, char _dir) : x(_x), s(_s), step(_step), dir(_dir) {}
};

int main() {
#ifdef __LOCAL_WONZY__
freopen("input-2.txt", "r", stdin);
#endif
scanf("%d", &T);
for(int cas = 1; cas <= T; ++cas) {
scanf("%d %d %d", &N, &G, &M);
queue<QNode> que;
map<int, int> x_idx, i_idx;
for(int i = 1; i <= G; ++i) {
scanf("%d %s", &H[i], op);
if(op[0] == 'A') {
int x = (H[i]-1-M%N+N)%N+1;
if(x_idx.find(x) != x_idx.end()) i_idx[i]=x_idx[x];
else {
que.push(QNode(x, i, M, 'C'));
x_idx[x] = i;
i_idx[i] = i;
}
} else {
int x = (H[i]-1+M%N)%N+1;
if(x_idx.find(-x) != x_idx.end()) i_idx[i]=x_idx[-x];
else {
que.push(QNode(x, i, M, 'A'));
x_idx[-x] = i;
i_idx[i] = i;
}
}
ans[i] = 0;
}
vector<int> step(N+1, -1);
vector<bool> c_used(N+1, false), a_used(N+1,false);
while(!que.empty()) {
QNode u = que.front(); que.pop();
if(u.step < 0) continue;
if(u.dir == 'C' && c_used[u.x]) continue;
if(u.dir == 'A' && a_used[u.x]) continue;

if(u.dir == 'C') {
que.push(QNode(u.x%N+1, u.s, u.step-1, 'C'));
c_used[u.x] = true;
} else {
que.push(QNode((u.x-2+N)%N+1, u.s, u.step-1, 'A'));
a_used[u.x] = true;
}
if(step[u.x] != -1 && step[u.x] > u.step) continue;
else step[u.x] = u.step;
ans[i_idx[u.s]] += 1;
}
printf("Case #%d:", cas);
for(int i = 1; i <= G; ++i) {
printf(" %d", ans[i_idx[i]]);
}
printf("\n");
}
return 0;
}

3. Foot Stalls

3.1 题目链接

[Kickstart Round D 2019 C. Foot Stalls]

3.2 题意描述

Problem C. Foot Stalls

3.3 解题思路

假设 $x_0$ 表示 warehouse 的位置,$x_1\sim x_K$表示 $K$ 个 stalls 的位置。那么,题意就是求:

warehouse 的位置一定是 $K+1$ 个数的中位数。(证明简单。可以假设给定了 $K+1$ 个位置,现在需要确定 warehouse 的位置,使得花费最小。)

在 warehouse 左边的 $stall_i$ 对答案贡献为 $C_{x_i}-x_i$, 在 warehouse 右边的 $stall_i$ 对答案的贡献为 $C_{x_i}+x_i$。

现在按照坐标位置来枚举 warehouse,根据贡献的大小,用最大堆/优先队列维护左边 $\frac{K}{2}$ 个数,用有序数组维护右边 $\frac{K}{2}$ 个数,分别求出左边、右边最小的 $\frac{K}{2}$ 个数之和。

细节繁琐,详情见代码

3.4 参考代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 1e5 + 5;
int T, N, K;
struct Node {
ll x, c;
} nd[MAXN];
bool cmp_x(const Node& a, const Node& b) {
return a.x < b.x;
}

ll solve(int lcnt, int rcnt) {
priority_queue<ll> le;
vector<pair<ll, int>> ri;
ll lsum = 0, rsum = 0;
for(int i = 1; i <= lcnt; ++i) le.push(nd[i].c-nd[i].x), lsum += nd[i].c-nd[i].x;
for(int i = lcnt+2; i <= N; ++i) ri.push_back(make_pair(nd[i].c+nd[i].x, i));
sort(ri.begin(), ri.end());
for(int j = 0; j < rcnt; ++j) rsum += ri[j].first;
ll ret = lsum + rsum + nd[lcnt+1].c + (lcnt-rcnt)*nd[lcnt+1].x;

map<int, int> mp;
for(int j = 0; j < ri.size(); ++j) mp[ri[j].second] = j;
for(int i = lcnt+2, j=rcnt-1; N-i >= rcnt; ++i) {
int p = mp[i];
if(p <= j) {
++j;
while(j < ri.size() && ri[j].second == -1) ++j;
if(j >= ri.size()) break;
rsum += ri[j].first;
rsum -= nd[i].c + nd[i].x;
lsum += nd[i-1].c - nd[i-1].x;
le.push(nd[i-1].c - nd[i-1].x);
lsum -= le.top(); le.pop();
umin(ret, lsum + rsum + nd[i].c + (lcnt-rcnt)*nd[i].x);
} else {
ri[p].second = -1;
lsum += nd[i-1].c - nd[i-1].x;
le.push(nd[i-1].c - nd[i-1].x);
lsum -= le.top(); le.pop();
umin(ret, lsum + rsum + nd[i].c + (lcnt-rcnt)*nd[i].x);
}
}
return ret;
}

int main() {
#ifdef __LOCAL_WONZY__
freopen("input-3.txt", "r", stdin);
#endif
scanf("%d", &T);
for(int cas = 1; cas <= T; ++cas) {
scanf("%d %d", &K, &N);
for(int i = 1; i <= N; ++i) scanf("%lld", &nd[i].x);
for(int i = 1; i <= N; ++i) scanf("%lld", &nd[i].c);
sort(nd + 1, nd + N + 1, cmp_x);
ll ans = min(solve(K/2, K-K/2), solve(K-K/2, K/2));
printf("Case #%d: %lld\n", cas, ans);
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!