CF 1131 (Div.3) A-E
一句话总结：罚时吃到饱，个人感觉 B > C，D >> E
A
给定两个字符串 $a$ 和 $b$，判断这两个字符串的差集是否是 six
直接统计每个字母出现次数即可。
int c[27], d[27];
void solve() {
memset(c, 0, sizeof c);
memset(d, 0, sizeof d);
int n, m;
string a, b;
cin >> n >> m;
cin >> a;
cin >> b;
for (int i = 0; i < n; ++i) ++c[a[i] - 'a'];
for (int i = 0; i < m; ++i) ++d[b[i] - 'a'];
int f = 1;
for (int i = 0; i <= 26; ++i) {
if (i + 'a' == 's') { f &= (d[i] + 1 == c[i]); continue; }
if (i + 'a' == 'i') { f &= (d[i] + 1 == c[i]); continue; }
if (i + 'a' == 'x') { f &= (d[i] + 1 == c[i]); continue; }
f &= (d[i] == c[i]);
}
cout << (f ? "Yes" : "No") << "\n";
}
一开始读错题了，以为是判断 $b$ 是否是 $a$ 的子集，喜提 10min 罚时
B
很有意思的一道题
小 A 和小 B 进行石头剪刀布。给定三个数 $x$，$y$ 和 $z$，表示小 A 接下来会出 $x$ 次石头，$y$ 剪刀，$z$ 次布，但是顺序是未知的，要求构造一个长度为 $x + y + z$ 的序列，让小 B 有不输的策略。
赢的策略是无解的，但是不输的还是可以构造一下的。 记 $M$ 表示 $x$，$y$ 和 $z$ 中最大值对应的出招，那么输出 $x + y + z$ 个克 $M$的招即可。
证明：设 $m$表示克 $M$ 的招，$\mathbb{M}$ 表示克 $m$ 的招。出了 $x + y + z$ 个 $m$，保证小 B 能赢 $\max(x, y, z)$ 回合，平至少 $\min(x, y, z)$ 回，输至多 $x + y + z - \max(x, y, z) - \min(x, y, z)$ 回。而显然 $\max(x, y, z) \geq x + y + z - \max(x, y, z) - \min(x, y, z)$ 所以在这样的策略下，小 B 不输。
int a[3];
char s[7] = "RSP";
void solve() {
for (int i = 0; i < 3; ++i) read(a[i]);
int p = 0;
for (int i = 0; i < 3; ++i) if (a[i] > a[p]) p = i;
for (int i = 1; i <= a[0] + a[1] + a[2]; ++i) putc(s[(p - 1 + 3) % 3]);
putc('\n');
}
C
给定一个长度为 n 的正整数序列，每次可以把任意位置上的数拆成两个正整数加在它的两边（如果有一边没有数则这一边的数消失），拆完之后删除掉这个位置。问能否操作到只剩下一个数，如果不可以，输出 `-1`；如果可以，输出最后剩下那个数的最大值。
显然如果一个数的左边/右边没有数了，那么最好不要拆它，如果不得不拆的话，消失的那一部分为 1 是最优的，因为这样损失最小。
接下来想想无解的情况，如果任何数都不能拆，则必然不能达到只有一个数的局面，一旦有一个数大于 1，就可以拆它，让它左边/右边的数大于 1，然后继续拆。因此无解我们直接判断序列是否全 1 即可。
constexpr int N = 2e5 + 7;
int n, a[N];
void solve() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
int f = n != 2;
for (int i = 2; i < n; ++i) f &= a[i] == 1;
int g = (a[1] == 1 && a[n] == 1);
if (f & g) print(-1);
else {
if (n == 2) {
if (g) print(-1);
else print(a[1] + a[2] - 1);
} else {
if (f & !g) print(a[1] + a[n] - 1);
else {
int su = 0;
for (int i = 1; i <= n; ++i) su += a[i];
print(su - 1);
}
}
}
putc('\n');
}
赛时代码我多写了点 corner case，实际上并不必要
D
赛时没做出来
给定一个序列，一轮操作里包含下列动作：
- 选 k 个数，给他们上锁，让他们在下一轮操作内不被改变。这个动作代价为 k
- 给所有数 +1 或者 -1
- 解锁所有元素
可以进行任意次这样的操作，求让他们变得一样的最小代价以及达到这样的最小代价的最少操作数。
动作 1 比较复杂，考虑转化：在进行动作 2 之后，我们把这 k 个数受到的影响回退即可。
我们设最终值为 $s$，公共变化量为 $v$。那么总共代价至少为 $\sum_{i = 1}^n |a_i + s - v|$。令 $x = s - v$。则可以写成 $\sum_{i = 1}^n |a_i - x|$。
接下来一步是容易的，只要 $x$ 取中位数，即可让 $\sum_{i = 1}^n |a_i - x|$ 的值最小。
考虑最小的操作次数，记最大值为 $M$，最小值为 $m$。观察到在一次操作中两个元素之间的差最多变化 1，所以最小操作次数就是 $M - m$。
接下来构造以满足这个下界。
记中位数为 $mid$，先进行 $M - mid$ 次 +1 的操作，第 $t$ 次操作锁定所有满足 $a_i \geq m + t $ 的 $a_i$。再进行 $mid - m$ 次 -1 的操作，第 $t$ 次操作锁定所有满足 $a_i \leq m - t$的元素。
解释一下：在第一部分的操作中，对于某个 $a_i > m$，它恰好在 $t = 1, 2, …, a_i - m$ 这些操作中被锁定，一共被锁定了 $a_i - m$ 次。第二部分的操作也是这样。
最后的总操作次数即为 $(M - mid) + (mid - m) = M - m$。
constexpr int N = 2e5 + 7;
int n;
ll a[N];
void solve() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
sort(a + 1, a + n + 1);
ll x = n & 1 ? a[n / 2 + 1] : (a[n / 2] + a[n / 2 + 1]) / 2;
ll ans = 0;
for (int i = 1; i <= n; ++i) ans += abs(a[i] - x);
print(' ', ans, a[n] - a[1]);
putc('\n');
}
好题，赛时没想出来，积累了一种新的转化方法
E
一次操作可以使得相邻元素各自成为对方的相反数。问任意多次操作后，序列的和最大是多少。
构造 $b_i = (-1)^{i + 1} a_i$，在原序列上的操作 $-a_i \mapsto a_{i + 1}$ 和 $-a_{i + 1} \mapsto a_i$ 就变成了 $b_i \mapsto b_{i + 1}$ 和 $b_{i + 1} \mapsto b_i$，即交换相邻元素。
而由冒泡排序我们知道，我们可以通过这样的交换来让序列变得有序，也可以让一个数去向任意位置。最后要求原序列的和，我们有 $\sum_{i = 1} ^ n a_i = \sum_{i = 1} ^ n (-1)^{i + 1} b_i$。那么我们把 b 重新排序，把大的放在奇数位，小的放在偶数位即可最大化和。实现上排个序，然后前半部分的和减去后半部分的和即可。
constexpr int N = 2e5 + 7;
int n, a[N];
void solve() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= n; ++i) if (!(i & 1)) a[i] = -a[i];
sort(a + 1, a + n + 1);
ll r1 = 0, r2 = 0;
for (int i = 1; i <= n / 2; ++i) r1 += a[i];
for (int i = n / 2 + 1; i <= n; ++i) r2 += a[i];
print(r2 - r1), putc('\n');
}