Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)（A~E）

t宝酱紫喜欢出这种分类讨论的题？！

A1. Non-alternating Deck (easy version)

给出n张牌，按照题目给的顺序分给两人，问最后两人手中各有几张牌。

思路：模拟。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int t, n;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;n --;ll cnta = 1, cntb = 0;int cnt = 0, res = 0;for(int i = 2; n > 0; i ++) {if(cnt == 2) res ^= 1, cnt = 0;if(res == 0)cntb += std::min(n, i), n -= std::min(n, i);elsecnta += std::min(n, i), n -= std::min(n, i);cnt ++;}std::cout << cnta << ' ' << cntb << '\n';}return 0;
}

A2. Alternating Deck (hard version)

在A1的基础上分了两种颜色，问最后每人手中每种颜色有几张。

思路：还是模拟。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int t, n;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;int pos = 1, cntp = 0, cnt = 0, res = 0;int cntaw = 0, cntab = 0, cntbw = 0, cntbb = 0;for(int i = 1; i <= n; i ++) {if(cntp == pos) {res ++;pos ++;cntp = 0;if(res & 1)cnt ^= 1;}if(!cnt) {if(i & 1)cntaw ++;elsecntab ++;}else {if(i & 1)cntbw ++;elsecntbb ++;}cntp ++;}std::cout << cntaw << ' ' << cntab << ' ' << cntbw << ' ' << cntbb << '\n'; }return 0;
}

B. Cake Assembly Line

给出一个蛋糕的位置序列和加巧克力的机器头的位置序列，调整两条线的相对顺序，是否可以满足机器头加入巧克力全部位于蛋糕上的要求。

思路：从头开始找范围的交集，如果交集不为空集就可以满足。当然，机器头的半径如果大于蛋糕的半径，那一定是不可以的。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n, w, h;
ll a[N], b[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> w >> h;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}for(int i = 1; i <= n; i ++) {std::cin >> b[i];}if(w < h) {std::cout << "NO" << '\n';continue;}ll L = a[1] - w + h, R = a[1] + w - h;for(int i = 2; i <= n; i ++) {ll lb = L + b[i] - b[i - 1], rb = R + b[i] - b[i - 1];// std::cout << lb << ' ' << rb << '\n';ll l = a[i] - w + h, r = a[i] + w - h;// std::cout << l << ' ' << r <<'\n';L = std::max(l, lb), R = std::min(r, rb);// L = std::max(l, L);// R = std::min(R, r);// std::cout << l << ' ' << r << ' ' << L << ' ' << R << '\n';}std::cout << (L <= R ? "YES" : "NO") << '\n';}return 0;
}

C. Monsters (easy version)

给出一个序列的怪物的生命值，有两种操作，一是对其中一个怪物打击，使得它的生命值-1；二是对于所有的怪物进行打击，每一个都-1，如果在一次打击中有怪物生命值降为0，则可以重复该操作。求操作一使用次数最少是多少。

思路：最优的操作是使得操作数组存在1~x连续序列，数字必须从1开始，尽可能使得数字变大，不能通过一次操作二减去的那只能操作一减去了。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}std::sort(a + 1, a + 1 + n);ll pos = 1, ans = a[1] - pos;for(int i = 2; i <= n; i ++) {if(a[i] == pos)continue;pos ++;ans += (a[i] - pos);}std::cout << ans << '\n';}return 0;
}

D. Letter Exchange

给出m个有三个字符的字符串，每次可以用两个字符串交换字符，问最少交换几次，可以的使得每个字符串的三个字符都不一样。

思路：大佬的思路

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int t, n;
std::string s;struct node {int a, b;char c, d;
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;char ch[4] = "win";const std::array<int, 3> all1 = {1, 1, 1};while(t --) {std::cin >> n;std::map<std::array<int, 3>, std::vector<int>> mp;int sum = 0;for(int i = 1; i <= n; i ++) {std::cin >> s;std::array<int, 3> cnt = {};for(auto c : s) {if(c == 'w') cnt[0] ++;else if(c == 'i') cnt[1] ++;else cnt[2] ++;}if(cnt == all1) continue;mp[cnt].push_back(i);sum ++;}std::vector<node> op;while(sum) {int max = 0;std::array<int, 3> p1, p2;for(auto &[x1, v1] : mp) {if(v1.empty()) continue;for(auto &[x2, v2] : mp) {if(x1 == x2) continue;if(v2.empty()) continue;int c = 0;for(int i = 0; i < 3; i ++) {if(x1[i] < 1 && x2[i] > 1) c ++;else if(x2[i] < 1 && x1[i] > 1) c ++;}if(c > max) {max = c;p1 = x1, p2 = x2;}}}int t1 = mp[p1].back();int t2 = mp[p2].back();mp[p1].pop_back();mp[p2].pop_back();char c1, c2;for(int i = 0; i < 3; i ++) {if(p2[i] >= 2) c2 = ch[i], p2[i] --, p1[i] ++;else if(p1[i] >= 2) c1 = ch[i], p1[i] --, p2[i] ++;}if(p1 != all1) mp[p1].push_back(t1);else sum --;if(p2!= all1) mp[p2].push_back(t2);else sum --;op.push_back({t1, t2, c1, c2});}std::cout << op.size() << '\n';for(auto [a, b, c, d] : op) {std::cout << a << ' ' << c << ' ' << b << ' ' << d << '\n';}}return 0;
}

E. Monsters (hard version)

与C相同，不过区别是要对于每个i输出所需的最少操作一数量。

思路：我们的操作是将原数组组成一个+1递增的数列，对于每次向后加入的数，如果它比较小，那对于现有的数组来说没什么影响；但是若是加入的数比较大，那就需要考虑它的影响了。但是例如1，1，3，3，3，5来说，最后变成的数组为1，1，2，3，3，4，而其中第二个数和第四个数对于答案是没有贡献的，而去掉重复的元素后，前i个数的结果为：其中n是数组所能达到的最大的数。

引用大佬的结论和证明：

AC Code：

#include <bits/stdc++.h>typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
const int N = 2e5 + 5;
int t, n;
int a[N];struct SegmentTree {struct node {int l, r, max, add;} tr[N << 2];void pushup(int u) {tr[u].max = std::max(tr[u << 1].max, tr[u << 1 | 1].max);}void build(int u, int l, int r) {tr[u] = {l, r, -INF, 0};if(l == r) {tr[u].max = -l;return;}int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}void pushdown(int u) {if(tr[u].add) {tr[u << 1].add += tr[u].add;tr[u << 1 | 1].add += tr[u].add;tr[u << 1].max += tr[u].add;tr[u << 1 | 1].max += tr[u].add;tr[u].add = 0;}}void modify(int u, int l, int r, int c) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].max += c;tr[u].add += c;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, c);if(r > mid) modify(u << 1 | 1, l, r, c);pushup(u);}}int query(int u) {if(tr[u].l == tr[u].r) return tr[u].l;pushdown(u);if(tr[u << 1].max > 0) return query(u << 1);return query(u << 1 | 1);}} ST;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}ST.build(1, 1, n);int cnt = 0, s = 0;for(int i = 1; i <= n; i ++) {cnt ++, s += a[i];ST.modify(1, a[i], n, 1);if(ST.tr[1].max > 0) {int x = ST.query(1);ST.modify(1, x, n, -1);cnt --, s -= x;}std::cout << s - cnt * (cnt + 1) / 2 << " \n"[i == n];}}return 0;
}