被菜哭A
由题，一个塔至多叠 \(\lfloor \frac dm \rfloor + 1\) 个箱子，那么答案为 \(\lceil \frac{n}{\lfloor \frac dm \rfloor + 1} \rceil\)。
B
注意到 \(\forall x\ge 10, F(x)<x\)。当 \(x\in [1, 9]\) 时才有 \(F(x) = x\)。那我们的目标变成让 \(F(x)\le 9\)。
对每一位操作造成的影响独立，考虑贪心。造成增益最大的方法自然是最高位变 \(1\)，其余位变 \(0\)，贪心地选出收益最高的位，直至 \(F(x)\le 9\) 即可。
调试的时候删掉了排序，莫名其妙地调了 5min，有点搞笑。
#include <bits/stdc++.h>
#define pb emplace_backint main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t;std::cin >> t;while (t--) {std::string s;std::cin >> s;int n = s.length();std::vector<int> c(n);int tot = 0;for (int i = 0; i < n; ++i) {c[i] = s[i] - '0';tot += c[i];if (i == 0) --c[i];}std::sort(c.begin(), c.end(), std::greater<int>());int ans = 0;for (int i = 0; i < n; ++i) {if (tot > 9) tot -= c[i], ++ans;else break;}std::cout << ans << '\n';}return 0;
}
C
有解的充要条件为 \(s\equiv 0\pmod{\operatorname{lowbit}(m)}\)。最基本的构造是用 \(\frac s{\operatorname{lowbit}(m)}\) 个 \(\operatorname{lowbit}(m)\)。
一种贪心的考量是，尝试用 \(m\) 的尽量高位取代若干个 \(\operatorname{lowbit}(m)\)。
考虑二分答案 \(n\)，那么 \(m\) 中的每个位至多取 \(n\) 个，从高到低贪心取，能凑够 \(s\) 则 check 成功。
#include <bits/stdc++.h>
#define pb emplace_backusing i64 = long long;void work() {i64 s, m;std::cin >> s >> m;i64 l = 1, r = 1e18;auto chk = [&](i64 x) {i64 cur = s;for (int bit = 59; ~bit; --bit) {if (~m >> bit & 1) continue;i64 r = std::min(cur >> bit, x);cur -= r << bit;}return cur == 0;};while (l <= r) {i64 mid = (l + r) >> 1;if (chk(mid)) {r = mid - 1;} else {l = mid + 1;}}if (!chk(l)) return std::cout << "-1\n", void();std::cout << l << '\n';return;
}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t;std::cin >> t;while (t--) work();return 0;
}
D
问题看着挺唬人，但事实上我们可以这样理解：
\(b\) 序列中有 \(A\) 个数是 \(a\) 序列元素的公倍数，\(B\) 个数不是 \(a\) 序列任意元素的倍数，\(C=m-A-B\) 个数是 \(a\) 中一部分元素（但不是全部）的公倍数。
Alice 可以从 \(A, C\) 中拿，Bob 可以从 \(B, C\) 中拿，谁先取不了数谁输。
\(A\) 只需要知道 \(a\) 序列的公倍数便可求出，\(B\) 只需要做一个 \(\mathcal O((n+m)\ln (n+m))\) 类似筛法的过程即可维护，\(C\) 自然得出。
注意这个过程的数量非常敏感，由于 \(C\) 是公共的，Alice 和 Bob 一定会尽量先取 \(C\) 中的数。那么 Alice 分得 \(C-\lfloor \frac C2 \rfloor\) 个数，Bob 分得 \(\lfloor \frac C 2 \rfloor\) 个数。剩下的就是拼谁的数多。Alice 的获胜条件为 \(A+C-\lfloor \frac C2 \rfloor>B+\lfloor \frac C2 \rfloor\)，反之 Bob 获胜。
求公倍数的过程注意，如果公倍数已经大于 \(n+m\) 就不再处理，否则可能会爆。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec secondusing i64 = long long;
using pii = std::pair<int, int>;int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);
}i64 lcm(int x, int y) {return (i64)x / gcd(x, y) * y;
}void work() {int n, m;std::cin >> n >> m;std::vector<int> a(n), b(m);i64 t = 1;for (auto& x : a) std::cin >> x;for (auto& x : b) std::cin >> x;std::vector<bool> vis(n + m + 1, 0);for (auto& x : a) {vis[x] = 1;if (t <= n + m) t = lcm(t, x);}for (int i = 1; i <= n + m; ++i)if (vis[i]) for (int j = i + i; j <= n + m; j += i)vis[j] = true;int A = 0, B = 0, C = 0;for (auto& x : b) {if ((i64)x % t == 0) {++A;} else if (vis[x]) {++C;} else {++B;}}B += C >> 1, A += C - (C >> 1);std::cout << (A > B ? "Alice\n" : "Bob\n");return;
}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int t;std::cin >> t;while (t--) work();return 0;
}
E
我们只需要对 \(i\ge 3\) 的每个 \([1, i]\) 前缀做一遍这个问题，这意味着可能需要一些动态加入元素的数据结构。
回到博弈的过程，考虑一层一层拆解。当 \(a\) 选定后，若 \(b<a\)，则期望得分为 \(\frac 1{i-2}\sum\limits_{c<b} b-c\)。若 \(b>a\)，则期望得分为 \(\frac 1{i-2}\sum\limits_{c>b}c-b\)。显然不需要关注 \(\frac 1{i-2}\)，只需要考虑和式里的贡献。
把贡献放在数轴上理解，也即，\(<b\) or \(>b\) 的数到 \(b\) 的贡献之和。简单画个图理解一下就能发现，Bob 选择的一定是 \(a\) 的前驱、后继中贡献较大的那个。
我们记 \(L_b = \sum\limits_{c<b} b-c, R_b = \sum\limits_{c>b}c-b\)，可以发现 \(L\) 序列单调递增，\(R\) 序列单调递减。
取 \(ans_a = \max(L_{\mathrm{prev}(a)}, R_{\mathrm{suff}(a)})\)。\(ans\) 序列的图像相当于把 \(R\) 的图像向左平移再和 \(L\) 取 max，呈现类似 \(y=|x-k|\) 的 "山谷" 状。
我们要找到 \(\min(ans_a)\)，也就是要找到 "谷底" \(a\)，满足 \(L_{\mathrm{prev}(a)}< R_{\mathrm{suff}(a)}\)，而 \(L_a\ge R_{\mathrm{suff}(\mathrm{suff}(a))}\)。显然可以二分得出。
现在考虑维护，先对原序列离散化，可以只用一个树状数组，但我赛时没想太多，\(L, R\) 数组分别用了一个树状数组维护。以 \(L\) 为例，树状数组上维护的是 \(\le b\) 的 \(\sum_c c\) 和 \(\sum_c 1\)（也即元素和、数量）。
我们还需要一个支持查询前缀里第 \(k\) 大的方式，以支持查询前驱、后继，在 \(L\) 对应的树状数组上使用树状数组倍增的 trick 维护即可。
时间复杂度 \(\mathcal O(n\log^2 n)\)。两个 log 分别来自二分和树状数组。代码对于久疏训练的我来说不算好写。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec secondusing i64 = long long;
using pii = std::pair<int, int>;constexpr int mod = 998244353;
constexpr int maxn = 2e5 + 5;
constexpr i64 inf = 1e18;int n, inv[maxn], idx[maxn];
struct fenwick1 {int c[maxn];i64 sum[maxn];fenwick1() {}void mdf(int x, i64 y) {for (; x <= n; x += x & -x) {++c[x], sum[x] -= y;}return;}i64 query(int x, i64 val) {i64 ans = 0, cnt = 0;for (; x; x -= x & -x) {ans += sum[x];cnt += val * c[x];}return cnt + ans;}int find(int k) {int ans = 0;for (int i = 18; ~i; --i) {int nxt = ans + (1 << i);if (nxt <= n && c[nxt] < k) {ans = nxt;k -= c[nxt];}}return ans + 1;}
} tr1;
struct fenwick2 {int c[maxn];i64 sum[maxn];fenwick2() {}void mdf(int x, i64 y) {for (; x; x -= x & -x) {--c[x], sum[x] += y;}}i64 query(int x, i64 val) {i64 ans = 0, cnt = 0;for (; x <= n; x += x & -x) {ans += sum[x];cnt += val * c[x];}return cnt + ans;}} tr2;void add(int& x, int y) { if ((x += y) >= mod) x -= mod; return; }
void sub(int& x, int y) { if ((x -= y) < 0) x += mod; return; }i64 a[maxn], c[maxn];int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n;inv[1] = 1;for (int i = 1; i <= n; ++i) std::cin >> a[i], c[i] = a[i];for (int i = 2; i <= n; ++i) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;std::sort(c + 1, c + n + 1);for (int i = 1; i <= n; ++i) idx[i] = std::lower_bound(c + 1, c + 1 + n, a[i]) - c;auto addv = [&](int x) {tr1.mdf(x, c[x]);tr2.mdf(x, c[x]);return;};addv(idx[1]), addv(idx[2]);for (int i = 3; i <= n; ++i) {addv(idx[i]);int l = 1, r = i;auto qryl = [&](int x) {if (x <= 1) return 0ll;int p = tr1.find(x - 1);return tr1.query(p, c[p]);};auto qryr = [&](int x) {if (x >= i) return 0ll;int p = tr1.find(x + 1);return tr2.query(p, c[p]);};auto qry = [&](int x) {return std::max(qryl(x), qryr(x));};while (l <= r) {int mid = (l + r) >> 1;if (qryl(mid) < qryr(mid)) {l = mid + 1;} else {r = mid - 1;}}i64 ans = std::min(qry(r), qry(r + 1));std::cout << ans % mod * inv[i - 2] % mod << '\n';}return 0;
}
F
wo hao cai, shang xin le.