 Codeforces Round 1064 (Div. 2）)
A. Same Difference
显然最后只会变成原串的最后一个字符，考虑其在串中出现次数即可。
#include <bits/stdc++.h>
using namespace std;
string s;
int cnt[26], len;void prepare() {cin >> len >> s;memset(cnt, 0, sizeof(cnt));for (int i = 0; i < len; i++) {cnt[s[i] - 'a']++;}
}void calculate() {cout << len - cnt[s[len - 1] - 'a'] << '\n';
}void solve() {int t;cin >> t;while (t--) {prepare(), calculate();}
}int main() {solve();return 0;
}
B. Tab Closing
答案只有可能是 \(1\) 或 \(2\)。
考虑分情况取值，如果中途长度取值改变说明是 \(2\) 次操作。如果说 \(a \leq b\) 一定是一直取 \(\frac{a}{m}\)；同时考虑临界点 \(b = \frac{a}{m}\)，\(m\) 的取值如果小于 \(n\) 则也会出现多的一次操作。
#include <bits/stdc++.h>
using namespace std;
int n, a, b, m1, m2, st;void prepare() {scanf ("%d %d %d", &a, &b, &n);
}void calculate() {if (a <= b || a / b >= n) {printf ("1\n");}else {printf ("2\n");}
}void solve() {int t;scanf ("%d", &t);while (t--) {prepare(), calculate();}
}int main() {solve();return 0;
}
C. Cyclic Merging
因为要动态维护，并且每次取最小，考虑直接用 set 维护一个 \((\max(a_i, a_{rhs_i}), i)\) 的二元组，每次取最小更新答案的同时更新左右两边 \(lhs_i,rhs_i\) 的取值（因为是环初始 \(lhs_1 = n, rhs_n = 1\)）。
具体可以看代码。
#include <bits/stdc++.h>
#define mkp make_pair
using namespace std;
using pii = pair<int, int>;
int n, a[200005], lhs[200005], rhs[200005];
long long ans;
set<pii> s;void prepare() {scanf ("%d", &n);for (int i = 1; i <= n; i++) {scanf ("%d", &a[i]);if (i >= 2 && i <= n - 1) {lhs[i] = i - 1, rhs[i] = i + 1;}}lhs[1] = n, rhs[1] = 2;lhs[n] = n - 1, rhs[n] = 1;s.clear();for (int i = 1; i <= n; i++) {s.emplace(max(a[i], a[rhs[i]]), i);}
}void calculate() {ans = 0;while ((int)s.size() > 1) {int i = (*s.begin()).second;int l = lhs[i], r = rhs[i];s.erase(mkp(max(a[l], a[i]), l)), s.erase(mkp(max(a[i], a[r]), i));ans += max(a[i], a[r]), a[r] = max(a[i], a[r]);lhs[r] = l, rhs[l] = r;s.emplace(max(a[l], a[r]), l);}printf ("%lld\n", ans);
}void solve() {int t;scanf ("%d", &t);while (t--) {prepare(), calculate();}
}int main() {solve();return 0;
}
D. Marble Council
我们考虑当前放在 \(S\) 中的数的限制。
直接在值域上考虑。记 \(ton_x\) 表示 \(x\) 的出现次数，因为存在于 \(s\) 中的数一定是对应的划分出的非空集的众数，那么就有限制 \(\sum\limits_{x \in S}{ton_x} \geq \max\limits_{x \notin S}\{ton_x\}\)，否则不合法。
不难发现本质上是在选满足限制的子序列，考虑记 \(f_{i, j}\) 表示前 \(i\) 个数中选出来的子序列每个数的出现次数和为 \(j\) 的贡献。每个出现的 \(x\) 都可以被放进 \(S\) 里，故一种 \(S\) 的贡献是 \(\prod\limits_{x \in S}{ton_x}\)。那么有转移：\(f_{i, j} = f_{i - 1, j} + f_{i - 1, j - ton_i} \times ton_i\)。
最后答案为 \(\sum\limits_{i = \max\{ton_x\}} ^ {n} {f_{n, i}}\)。
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, a[5005], ton[5005];
long long dp[5005], ans;void init() {memset(dp, 0, sizeof(dp));memset(ton, 0, sizeof(ton));
}void prepare() {scanf ("%d", &n);for (int i = 1; i <= n; i++) {scanf ("%d", &a[i]), ton[a[i]]++;}sort(ton + 1, ton + n + 1);
}void calculate() {dp[0] = 1;for (int i = 1; i <= n; i++) {if (!ton[i]) {continue;}for (int j = n; j >= ton[i]; j--) {dp[j] = (dp[j] + dp[j - ton[i]] * ton[i] % mod) % mod;}}ans = 0;for (int i = ton[n]; i <= n; i++) {ans = (ans + dp[i]) % mod;}printf ("%lld\n", ans);
}void solve() {int t;scanf ("%d", &t);while (t--) {init(), prepare(), calculate();}
}int main() {solve();return 0;
}
E. Binary Wine
小清新小贪心。
哈基米哈基米
从高到低位考虑 \(c\)，显然高位需要更大的 \(a_i\) 去补。如果当前 \(c\) 这一位没有可用的 \(a_i\)，显然需要修改来补，那么修改最大的 \(a_i\) 肯定是最优的。那么可以发现最多只需要最大的 \(\log V\) 个 \(a_i\) 即可。记当前这一位是第 \(d\) 位。
-
\(a_i \geq 2^d\)，直接补上了这一位。
-
\(a_i < 2^d\)，修改到补上这一位为止，对答案产生 \(2^d - a_i\) 的贡献。
每次询问直接暴力遍历 + 修改即可。注意每次还原被操作的数组。
#include <bits/stdc++.h>
#define INF32 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
char *p1, *p2, buf[10000001];int read() {int res = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {f = ch == '-' ? -1 : 1;ch = getchar();}while (ch >= '0' && ch <= '9') {res = res * 10 + (ch ^ 48);ch = getchar();}return res * f;
}int n, q, idx, a[500005], b[500005];
long long ans;void prepare() {n = read(), q = read();for (int i = 1; i <= n; i++) {a[i] = read();}sort(a + 1, a + n + 1, greater<int>());
}void calculate() {while (q--) {int c;c = read(), idx = ans = 0;for (int i = 1; i <= min(30, n); i++) {b[++idx] = a[i];}for (int i = 30; ~i; i--) {if ((c >> i) & 1) {int id = 0;long long cost = INF64, used = 0;for (int j = 1; j <= idx; j++) {if (b[j] >= (1 << i)) {used = 0;}else {used = ((1 << i) - b[j]);}if (used <= cost) {cost = used, id = j;}}b[id] += cost, ans += cost, b[id] -= (1 << i);}}printf ("%lld\n", ans);}
}void solve() {int t;t = read();while (t--) {prepare(), calculate();}
}int main() {solve();return 0;
}