Kickstart 2019

2019 Round D

1. X or What?

8pts, 19pts

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

int T, N, Q, P, V;
int nums[100010];
set<int> oddRankSet;
int bitsNum[1024];
int main() {
    cin >> T;
    for (int i = 0; i < 1024; i ++) {
        int n = 0;
        for (int j = 0; j < 10; j ++) n += 1 & (i >> j);
        bitsNum[i] = n;
    }
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        cin >> N >> Q;
        oddRankSet.clear();
        for (int i = 0; i < N; i ++) {
            int temp;
            cin >> temp;
            nums[i] = (bitsNum[temp] % 2);
            if (nums[i] == 1) oddRankSet.insert(i);
        }
        cout << "Case #" << caseRank << ": ";
        for (int i = 0; i < Q; i ++) {
            cin >> P >> V;
            if (bitsNum[V] % 2 == 0 && nums[P] == 1) oddRankSet.erase(P);
            if (bitsNum[V] % 2 == 1) oddRankSet.insert(P);
            nums[P] = bitsNum[V] % 2;
            int res = N;
            if (oddRankSet.size() % 2 == 1) {
                int d1 = *oddRankSet.begin() + 1;
                int d2 = N - *oddRankSet.rbegin();
                res = N - min(d1, d2);
            }
            cout << res << ' ';
        }
        cout << '\n';
    }
}

2. Latest Guests

12pts, 23pts

#include <iostream>
#include <vector>
#include <memory>
#include <unordered_map>
#include <cstring>
using namespace std;

int T, N, G, H;
long long M;
char D;
unordered_map<int, int> key2group;
unordered_map<int, vector<int>> group2people;
int clockwise[100010][2];
int anticlock[100010][2];
int result[100010];

int main() {
    cin >> T;
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        memset(clockwise, -1, 100010*2*sizeof(int));
        memset(anticlock, -1, 100010*2*sizeof(int));
        memset(result, 0, 100010*sizeof(int));
        int groupRank = 0;
        key2group.clear();
        group2people.clear();
        cin >> N >> G >> M;
        int leftA = N, rightC = -1;
        for (int i = 0; i < G; i ++) {
            cin >> H >> D;
            int key = D == 'A' ? -H : H;
            if (!key2group.count(key)) key2group[key] = groupRank ++;
            int group = key2group[key];
            group2people[group].push_back(i);
            if (group2people[group].size() > 1) continue;
            int length = M % N;
            H --;
            int desti = D == 'A' ? (H-length+N)%N : (H+length)%N;
            if (D == 'A') {
                anticlock[desti][0] = 0;
                anticlock[desti][1] = group;
                leftA = min(leftA, desti);
            } else {
                clockwise[desti][0] = 0;
                clockwise[desti][1] = group;
                rightC = max(rightC, desti);
            }
        }
        int step = M > N - 1 ? N - 1 : M, prevGroup = clockwise[rightC][1], dist = 0;
        for (int i = 0; rightC >= 0 && i < N - 1; i ++) {
            rightC = (rightC + N - 1) % N;
            if (clockwise[rightC][0] == 0) {
                dist = 0;
                prevGroup = clockwise[rightC][1];
                continue;
            }
            dist ++;
            if (dist > M) continue;
            clockwise[rightC][0] = dist;
            clockwise[rightC][1] = prevGroup;
        }
        dist = 0, prevGroup = anticlock[leftA][1];
        for (int i = 0; leftA < N && i < N - 1; i ++) {
            leftA = (leftA + 1) % N;
            if (anticlock[leftA][0] == 0) {
                dist = 0;
                prevGroup = anticlock[leftA][1];
                continue;
            }
            dist ++;
            if (dist > M) continue;
            anticlock[leftA][0] = dist;
            anticlock[leftA][1] = prevGroup;
        }
        for (int i = 0; i < N; i ++) {
            vector<int> groups;
            if (anticlock[i][0] != -1 && (clockwise[i][0] == -1 || anticlock[i][0] <= clockwise[i][0])) groups.push_back(anticlock[i][1]);
            if (clockwise[i][0] != -1 && (anticlock[i][0] == -1 || clockwise[i][0] <= anticlock[i][0])) groups.push_back(clockwise[i][1]);
            for (auto group : groups) {
                for (auto people : group2people[group]) result[people] ++;
            }
        }
        cout << "Case #" << caseRank << ": ";
        for (int i = 0; i < G; i ++) cout << result[i] << ' ';
        cout << '\n';
    }
}

3. Food Stalls

7pts, 31pts

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
int T, K, N;

long long leftCost[100010];
long long rightCost[100010];

int main() {
    cin >> T;
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        memset(leftCost, 0, 100010 * sizeof(long long));
        memset(rightCost, 0, 100010 * sizeof(long long));
        cin >> K >> N;
        vector<pair<int, int>> spots;
        for (int i = 0; i < N; i ++) {
            int temp; cin >> temp;
            spots.push_back({temp, 0});
        }
        for (int i = 0; i < N; i ++) {
            int temp; cin >> temp;
            spots[i].second = temp;
        }
        sort(spots.begin(), spots.end());
        multiset<long long> s;
        long long costSum = 0;
        for (int i = 0; i < N + K / 2 - K; i ++) {
            long long a = spots[i].first;
            long long b = spots[i].second;
            costSum += (b - a);
            s.insert(b - a);
            if (s.size() > K / 2) {
                costSum -= *s.rbegin();
                s.erase(s.find(*s.rbegin()));
            }
            if (s.size() == K / 2) leftCost[i] = costSum;
        }
        s.clear();
        costSum = 0;
        for (int i = N - 1; i >= K / 2; i --) {
            long long a = spots[i].first;
            long long b = spots[i].second;
            costSum += (b + a);
            s.insert(b + a);
            if (s.size() > K - K / 2) {
                costSum -= *s.rbegin();
                s.erase(s.find(*s.rbegin()));
            }
            if (s.size() == K - K / 2) rightCost[i] = costSum;
        }
        long long mx = 1e18;
        for (int i = K / 2; i < N + K/2 - K; i ++) {
            long long cost = spots[i].second;
            long long distance = spots[i].first;
            if (K % 2 == 1) cost -= distance;
            cost += ((i > 0 ? leftCost[i-1] : 0) + rightCost[i + 1]);
            if (mx > cost) mx = cost;
        }
        cout << "Case #" << caseRank << ": " << mx << '\n';
    }
}

---

2019 Round F

1. Cherries Mesh

9pts, 13pts

有N个樱桃，用糖线 (candy strand)连接起来，有红色和黑色两种糖线，其中红色甜度为2，黑色甜度为1，现在做出来的甜点甜度太高，希望删去若干线，使得樱桃连在一块，且甜度最低

一开始所有樱桃两两之间都有糖线，其中一些是黑色，其余是红色，输入格式如下

T个测例，对每个测例，先输入N和M，表示樱桃个数和黑线个数，剩下M行，每行两个数C和D，表示这条黑线连接的两个樱桃编号

思路

尽可能用黑线来将樱桃连起来，剩下的用红线连，一共一定是N-1条线，所以甜度就是2*(N-1)-黑线总条数

用并查集来做，如果黑线将两个集合合并起来，说明这条黑线可以用，否则则不能用，由此计算出黑线总条数即可

#include <cstdio>

int T, N, M, C, D;
int cherries[100010];
int find(int num) {
    if (cherries[num] != num)
        cherries[num] = find(cherries[num]);
    return cherries[num];
}

int main() {
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        scanf("%d%d", &N, &M);
        long long black = 0;
        for (int i = 1; i <= N; i ++) cherries[i] = i;
        for (int i = 0; i < M; i ++) {
            scanf("%d%d", &C, &D);
            int rc = find(C), rd = find(D);
            if (rc != rd) {
                black ++;
            }
            cherries[rc] = cherries[C] = rd;
        }
        long long result = N - 1;
        result *= 2;
        result -= black;
        printf("Case #%d: %lld\n", caseRank, result);
    }
}

2. Code-Eat Switcher

11pts, 25pts

#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int T, D, S;
ll C, E;
ll A, B;
int binarySearchLowerBound(const vector<ll>& v, ll target) {
    int l = 0, r = v.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if(target <= v[m]) r = m - 1;
        else l = m + 1;
    }
    return l;
}
int main() {
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        scanf("%d%d", &D, &S);
        vector<vector<ll>> slots;
        for (int i = 0; i < S; i ++) {
            scanf("%lld%lld", &C, &E);
            slots.push_back({E, C});
        }
        auto comp = [](vector<ll> a, vector<ll> b) -> bool { return a[0]*b[1] > b[0] * a[1]; };
        sort(slots.begin(), slots.end(), comp);
        vector<ll> prefixEating, prefixCoding;
        long long eating = 0, coding = 0;
        for (auto v : slots) {
            eating += v[0];
            coding += v[1];
            prefixEating.push_back(eating);
            prefixCoding.push_back(coding);
        }
        string result = "";
        for (int i = 0; i < D; i ++) {
            scanf("%lld%lld", &A, &B);
            if (prefixEating.back() < B || prefixCoding.back() < A) {
                result += "N";
                continue;
            }
            int rank = binarySearchLowerBound(prefixEating, B);
            ll eatingBase = rank > 0 ? prefixEating[rank - 1] : 0;
            B -= eatingBase;
            ll remain = prefixCoding.back() - prefixCoding[rank];
            A -= remain;
            if (A <= 0) {
                result += "Y";
                continue;
            }
            if (slots[rank][0] * A + slots[rank][1] * B <= slots[rank][0] * slots[rank][1])
                result += "Y";
            else result += "N";
        }
        printf("Case #%d: %s\n", caseRank, result.c_str());
    }
}

3. Street Checker

13pts, 29pts

#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
using ll = long long;

ll L, R;
int T;
const ll NN = 1000000000;
std::bitset<100000> isEven;
vector<ll> primes;
bool isPrime(ll num) {
    int ptr = 0;
    if (num == 1) return true;
    for (; ptr < primes.size(); ptr ++) {
        if (primes[ptr] >= num) break;
        if (num % primes[ptr] == 0) return false;
    }
    if (ptr < primes.size()) return primes[ptr] == num;
    return true;
}
int main() {
    for (ll i = 2; i * i <= NN; i ++) {
        if (!isEven[i]) {
            for (ll j = i * i; j < isEven.size() && j * j <= NN; j += i) {
                isEven[j] = true;
            }
            primes.push_back(i);
        }
    }
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank ++) {
        scanf("%lld%lld", &L, &R);
        ll result = 0;
        for (ll i = L; i <= R; i ++) {
            ll prev = result;
            if (i % 2 == 0) {
                int num = 0;
                ll temp = i;
                while (!(temp & 1)) {
                    num ++;
                    temp >>= 1;
                }
                if (num == 1) result ++;
                else if (num == 2 && isPrime(temp)) result ++;
                else if (i == 8) result ++;
            } else {
                if(isPrime(i)) result ++;
            }
        }
        printf("Case #%d: %lld\n", caseRank, result);
    }
}

---

2019 Round G

1. Book Reading

10pts, 15pts

有本$N$页的书，编号从1到N，其中若干页被撕掉，现在有$Q$名读者，每个人读若干页，具体规则为第$i$个人读$R_i$的整数倍的页，求这些人能读到的所有页数之和

输入格式

T 代表T个样例
之后T个样例，输入格式如下
N M Q在第一行输入
M个整数，表示丢掉的页
Q个整数，表示R1到Rn

• $1\le M \le N \le 10^5$
• $1\le Q \le 1000$

思路

预先计算即可，每个样例在确定$N$后，对从$1$到$N$的每个数，遍历其所有倍数，计算出所有可读的页数，复杂度为$N(\frac{1}{1}+\frac{1}{2}+...+\frac{1}{N})$，调和级数复杂度为$logN$，所以这个过程复杂度是$NlogN$，算上之后的读者查询，总复杂度是$NlogN+Q$，可以解题

在做ks时是先将每个数的所有因子找出来，然后在读入一个被撕掉的页后，更新其所有因子会读不到的页数，然后Q次查询时用$N/R$减这个数即可，复杂度基本接近，算因子复杂度基本是$\sqrt{N}logN$，之后更新复杂度可能会高一点，整体感觉不如上一种算法可控，因为上一种等于将所有页数存储下来，用空间来换取时间

#include <cstdio>
#include <vector>
using namespace std;

int T, N, M, Q;

int main() {
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank++) {
        scanf("%d%d%d", &N, &M, &Q);
        vector<int> page(N + 1, 1);
        for (int i = 0; i < M; i++) {
            int val;
            scanf("%d", &val);
            page[val] = 0;
        }
        vector<int> num(N + 1, 0);
        for (int i = 1; i <= N; i++)
            for (int j = i; j <= N; j += i)
                num[i] += page[j];
        long long res = 0;
        for (int i = 0; i < Q; i++) {
            int val;
            scanf("%d", &val);
            res += num[val];
        }
        printf("Case #%d: %lld\n", caseRank, res);
    }
}

2. The Equation

12pts, 20pts

宇宙的秘密由$N$个非负整数代表，一个宇宙是好的当且仅当存在一个非负整数$k$使以下式子成立

$(A_1\oplus k)+(A_2\oplus k)+...+(A_N\oplus k)\le M$

求最大k使一个宇宙是好的，如果不存在则返回-1

输入格式

T个测试样例
每个样例输入如下
N M在第一行输入
第二行包含N个整数，即一个宇宙的整数

• $1\le N \le 1000$
• $0\le M \le 10^{15}$
• $0\le A_i\le 10^{15}$

思路

分两部分讨论，然后贪心即可

根据数据范围，64位整数可以存下，首先对所有A记录每一位出现的1个数

对于超过$M$最高位的部分，每个数的异或结果都只能是0，所以要么所有数这位全是1，要么全是0

对于不高于$M$最高位的部分，首先判断该位可不可能置为1，这里还要提前算出f(i)，即i位为最高位时异或所得的最小值，也就是每个位0和1较少的那个异或结果置为1再求和；在判断时将当前位设为1，加上f(i-1)判断是否大于M即可，如果大于，这位只能置为0，如果置为0加上f(i-1)还大于M，那么不存在，直接返回-1

#include <cstdio>
#include <vector>
using namespace std;
using ll = unsigned long long;

int T, N;
ll M;
int main() {
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank++) {
        vector<ll> number(65, 0);
        scanf("%d%lld", &N, &M);
        int pos = 0;
        for (ll TMP = M; TMP > 0; TMP >>= 1) pos++;
        for (int i = 0; i < N; i++) {
            ll tmp;
            scanf("%lld", &tmp);
            int pos = 1;
            while (tmp > 0) {
                if (tmp & 1) number[pos]++;
                pos++;
                tmp >>= 1;
            }
        }
        vector<ll> value(65, 0);
        ll total = 0, rank = 1;
        for (int i = 1; i <= 64; i++) {
            ll t = (N - number[i] < number[i]) ? N - number[i] : number[i];
            total += rank * t;
            value[i] = total;
            rank <<= 1;
        }
        ll K = 0, sum = 0;
        rank = 1; rank <<= 63;
        bool solve = true;
        for (int i = 64; i >= 1; i--, rank >>= 1) {
            if (i > pos) {
                if (number[i] != 0 && number[i] != N) {
                    solve = false;
                    break;
                } else {
                    if (number[i] == N) K |= rank;
                }
            } else {
                ll t = N - number[i];
                if (t * rank + value[i - 1] + sum <= M) {
                    K |= rank;
                    sum += t * rank;
                } else {
                    if (sum + (N - t) * rank + value[i - 1] > M) {
                        solve = false;
                        break;
                    }
                    sum += (N - t) * rank;
                }
            }
        }
        if (solve) printf("Case #%d: %lld\n", caseRank, K);
        else printf("Case #%d: -1\n", caseRank);
    }
}

3. Shifts

20pts, 23pts

A和B是博物馆的两个Guard，接下来有$N$次轮换，每次轮换至少要有一个guard在工作，每次工作A和B分别会得到$A_i$和$B_i$的分数，要求分数总和大于$H$，求所有方案种类数

输入格式

T
N H
A_1 ... A_N
B_1 ... B_N

• small set: $1\le N \le 12$
• large set: $1\le N \le 20$
• $0\le H \le 10^9$
• $0 \le A_i \le 10^9$
• $0 \le B_i \le 10^9$

思路

依照题意，每次轮换有三种可能，A值班、B值班、A和B都值班，对于小数据集，可以枚举$3^12=531441$种可能，然后遍历检查每一种的A和B总分数是否达到H即可

但对于大数据集，无法暴力枚举来做，不过可以先将方案分成两部分，分别枚举，然后检查拼接两部分总分数都达到H的个数，具体来说，对前一半，记录H-A和H-B，即距离H还差多少分；而后一半直接存储A和B，将这样的分数对按照A进行排序，保证在两个分数都相等时，后一半在后面，即对一个后一半的数据组而言，所有可能和它组成合法结果的前一半数据组都在它前面，具体做法就是加入第三个字段，前一半是0后一半是1

之后就是检查前面哪些前一半的数据组可以匹配，这个因为A一定满足，只对B进行判断即可，这里用离散后的BIT即可

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
const int LIMIT = 120000;

int T, N;
ll H;
vector<vector<ll>> pairs;
vector<ll> ptsB;
vector<ll> A(21, 0), B(21, 0);
vector<ll> BIT;
void update(int i) {
    for (; i <= ptsB.size(); i += i & -i) BIT[i]++;
}
ll query(int i) {
    ll ans = 0;
    for (; i > 0; i -= i & -i) ans += BIT[i];
    return ans;
}
int main() {
    scanf("%d", &T);
    for (int caseRank = 1; caseRank <= T; caseRank++) {
        scanf("%d%lld", &N, &H);
        for (int i = 0; i < N; i++) scanf("%lld", &A[i]);
        for (int i = 0; i < N; i++) scanf("%lld", &B[i]);
        int number = 0;
        int N1 = N / 2, N2 = N - N1;
        int size1 = 1, size2 = 1;
        for (int i = 0; i < N1; i++) size1 *= 3;
        for (int i = 0; i < N2; i++) size2 *= 3;
        pairs.assign(size1 + size2, vector<ll>(3, 0));
        ptsB.assign(size1 + size2, 0);
        int rank1 = size1 / 3;
        for (int i = 0; i < N1; i++) {
            int rank = 0, r = 0;
            while (rank < size1) {
                ll numA = A[i], numB = B[i];
                if (r == 0) numB = 0;
                if (r == 1) numA = 0;
                for (int j = 0; j < rank1; j++) {
                    pairs[rank][0] += numA;
                    pairs[rank][1] += numB;
                    rank++;
                }
                r = (r + 1) % 3;
            }
            rank1 /= 3;
        }
        int rank2 = size2 / 3;
        for (int i = 0; i < N2; i++) {
            int rank = 0, r = 0;
            while (rank < size2) {
                ll numA = A[N1 + i], numB = B[N1 + i];
                if (r == 0) numB = 0;
                if (r == 1) numA = 0;
                for (int j = 0; j < rank2; j++) {
                    pairs[size1 + rank][0] += numA;
                    pairs[size1 + rank][1] += numB;
                    pairs[size1 + rank][2] = 1;
                    rank++;
                }
                r = (r + 1) % 3;
            }
            rank2 /= 3;
        }
        for (auto& v : pairs) {
            if (v[0] > H) v[0] = H;
            if (v[1] > H) v[1] = H;
        }
        for (int i = 0; i < size1; i++) {
            pairs[i][0] = H - pairs[i][0];
            pairs[i][1] = H - pairs[i][1];
        }
        for (int i = 0; i < pairs.size(); i++) ptsB[i] = pairs[i][1];
        sort(ptsB.begin(), ptsB.end());
        auto itr = unique(ptsB.begin(), ptsB.end());
        ptsB.resize(itr - ptsB.begin());
        sort(pairs.begin(), pairs.end());
        ll res = 0;
        BIT.assign(ptsB.size() + 1, 0);
        for (int i = 0; i < pairs.size(); i++) {
            int rank = lower_bound(ptsB.begin(), ptsB.end(), pairs[i][1]) - ptsB.begin() + 1;
            if (pairs[i][2] == 0) update(rank);
            else res += query(rank);
        }
        printf("Case #%d: %lld\n", caseRank, res);
    }
}