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 参考代码

#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 参考代码

#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 的位置。那么，题意就是求：

$$\begin{align}
\min \left\lbrace C_{x_0}+\sum\limits_{1\le i\le K}(C_{x_i}+\lvert x_i-x_0\rvert)\right\rbrace
\end{align}$$

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 参考代码

#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;
}