A. Pizza Time
题意：有\(n\)个物品，每次分成三部分，你拿走最少的一部分，第二大的丢弃，最大的保留下一轮。求你最多可以拿到多少。
我们可以分\(1, 1, n - 2\)。这样我们得到\(\lfloor \frac{n-3}{2} \rfloor\)个，然后剩下\(3\)个可以拿一个。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::cout << (n - 3) / 2 + 1 << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Strange MachineB. Strange Machine
题意：有\(n\)个指令，如果指令是\(A\)就把当前数减一，如果是\(B\)就把当前数除二向下取整，这些指令循环执行。\(q\)次查询求把一个数变成\(0\)的操作数。
如果有除二的指令，则最多执行\(log\)轮，直接模拟即可。
如果没有，则只有减一的指令，答案就是这个数本身。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, q;std::cin >> n >> q;std::string s;std::cin >> s;int cntb = std::ranges::count(s, 'B');while (q -- ) {int a;std::cin >> a;if (cntb == 0) {std::cout << a << "\n";} else {int ans = 0;for (int i = 0; a ; i = (i + 1) % n) {if (s[i] == 'A') {-- a;} else {a /= 2;}++ ans;}std::cout << ans << "\n";}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Maximum GCD on Whiteboard
题意：有\(n\)个数，你可以删除最多\(k\)个。对于剩下的数你可以进行以下操作：把这个数分成三个数，这三个的和等于这个数，然后把最大最小的两个数加入，删除当前数。求可以达到达到全局\(gcd\)最大是多少。
观察一下什么数可以分出来两个都有因子\(d\)的数，这个数要么是\(d\)的倍数，可以不操作；否则设这个数是\(x\)，则可以分成这三个数：\(d, d + x\% d, x - d - x \% d\)。那么要求这个数大于等于\(4d\)。那么可以计算\([d, 4d]\)中有多少数不是\(d\)的倍数，这些数也要删去。
则可以枚举答案，看需要删去的数的个数是不是小于等于\(k\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> sum(2 * n + 1);for (int i = 0; i < n; ++ i) {int x;std::cin >> x;++ sum[x];}for (int i = 1; i <= 2 * n; ++ i) {sum[i] += sum[i - 1];}for (int i = n; i >= 1; -- i) {int cnt = sum[i - 1];if (i * 2 <= 2 * n) {cnt += sum[i * 2 - 1] - sum[i];} if (i * 3 <= 2 * n) {cnt += sum[i * 3 - 1] - sum[i * 2];}if (i * 4 <= 2 * n) {cnt += sum[i * 4 - 1] - sum[i * 3];}if (cnt <= k) {std::cout << i << "\n";return;}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D. Find the Last NumberD. Find the Last Number
题意：交互题。有一个隐藏排列，你每次可以让\(p_i(i<n)\)和一个数进行按位与操作，如果结果不为\(0\)则返回\(1\)，则返回\(0\)。最多\(2n\)次询问求出\(p_n\)。
可以按位问，计算出这一位在剩下的数里有多少数是\(1\)多少是\(0\)，然后把通过查询所有剩下的数可以知道\(p_n\)这一位是什么，那么其它数可以丢弃，剩下的数进行下一位的操作。这样每一位操作后剩下的数都会减半，最终询问数不超过\(2n\)。这里口胡一下证明，大概就是一开始\([1, n]\)里第\(0\)位是\(1\)的个数和是\(0\)的个数相差不超过\(1\)，然后我们选择其中一个集合后，因为里面第\(0\)位都相同那么可以都除一个\(2\)再看第\(0\)位，这样相当于把\([1, n]\)放缩到了\([1, \frac{n}{2}]\)，然后继续看第\(0\)位，那么显然差距也不超过\(1\)。那么这样从小到大按位做大概每次剩下的数会减半。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int ask(int i, int x) {std::cout << "? " << i << " " << x << std::endl;int res;std::cin >> res;return res;
}void solve() {int n;std::cin >> n;int m = 0;for (int i = 20; i >= 0; -- i) {if (n >> i & 1) {m = i;break;}}int f[20][2]{};for (int i = 1; i <= n; ++ i) {for (int j = 0; j <= m; ++ j) {f[j][i >> j & 1] += 1;}}std::vector<int> a;for (int i = 1; i < n; ++ i) {a.push_back(i);}auto b = a;b.push_back(n);int tot = 0;std::vector<int> st(n + 1);for (int i = 0; i <= m && b.size() > 1; ++ i) {std::vector<int> na[2];for (auto & x : a) {na[ask(x, 1 << i)].push_back(x);}if (na[0].size() < f[i][0]) {a = na[0];std::vector<int> nb;for (auto & x : b) {if (x >> i & 1) {st[x] = 1;for (int j = i + 1; j <= m; ++ j) {-- f[j][x >> j & 1];}} else {nb.push_back(x);}}b = nb;} else {a = na[1];std::vector<int> nb;for (auto & x : b) {if (x >> i & 1) {nb.push_back(x);} else {st[x] = 1;for (int j = i + 1; j <= m; ++ j) {-- f[j][x >> j & 1];}}}b = nb;}}for (int i = 1; i <= n; ++ i) {if (!st[i]) {std::cout << "! " << i << std::endl;return;}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}