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