2025/11/24
Codeforces Round 1066 (Div. 1 + Div. 2)
A. Dungeon Equilibrium
比较简单，很明显要么全部清除要么削减到 \(a_i = i\)，直接算即可
Code
#include <iostream>
#include <map>using namespace std;int T, n, ans;
map<int, int> mp;int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> T;while (T--) {cin >> n;ans = 0, mp.clear();for (int i = 1, x; i <= n; i++)cin >> x, mp[x]++;for (int i = 0; i <= n; i++)ans += mp[i] >= i ? (mp[i] - i) : mp[i];cout << ans << '\n';}return 0;
}
B. Expansion Plan 2
统一处理那么多格子的变化并不好作，发现只有一条路径是有效的，那么原问题等价于可以选择一个方向走或者斜着走，能否走到 \((x, y)\)。那么很明显 \(4、8\) 的顺序不重要。同时 \(4\) 表示可以选择一个方向走一步，\(8\) 表示两个方向都走一步。那么直接看 \(\max(x - b, 0) + \max(0, y - b)\) 是否比 \(a\) 大即可，\(a\) 表示 \(4\) 的出现数量，\(b\) 表示 \(8\) 的出现次数
Code
#include <iostream>
#include <map>using namespace std;int T, n, x, y, a, b;
string s;int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> T;while (T--) {cin >> n >> x >> y >> s, x = abs(x), y = abs(y);a = b = 0;for (auto i : s)a += i == '4', b += i == '8';x -= b, y -= b;cout << (max(x, 0) + max(y, 0) <= a ? "yes\n" : "no\n");}return 0;
}
C. Meximum Array 2
要注意到所有操作都只有统一的一个值 \(k\)。那么构造并不难
- \(i\) 只有 \(\min\) 限制。直接令 \(a_i = k\) 即可
- \(i\) 只有 \(mex\) 限制。直接从 \(0~k - 1\) 按顺序轮着放即可。如果有两个限制相交，合并起来在做
- \(i\) 两种限制都有。令 \(a_i = k + 1\)
Code
#include <iostream>using namespace std;const int kN = 101;int T, n, k, q, a[kN], tag[kN];int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> T;while (T--) {cin >> n >> k >> q;fill(tag, tag + n + 1, 0);for (int i = 1, c, l, r; i <= q; i++) {cin >> c >> l >> r;for (; l <= r; l++)tag[l] |= c;}for (int i = 1, j = 0; i <= n; i++) {if (tag[i] == 1)a[i] = k;else if (tag[i] == 2)a[i] = j, j = (j + 1) % k;elsea[i] = k + 1;}for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << '\n';}return 0;
}
D. Billion Players Game
感觉比 E 要难一点
首先需要想到选择一定是成对出现的，并且贡献非负，所以最多舍弃 \(1\) 个点不选
\(Solution1\)：
对我来说更自然的想法。直接枚举这个不选择的点，发现前缀一定是向后，后缀一定是向前。一开始假设所有点都向前，往后扫的同时算出把这个点改成向后后的答案即可。因为是两个端点选最差的，那么同时维护在两个端点的取值
Code
#include <algorithm>
#include <iostream>using namespace std;
using ll = long long;const int kN = 2e5 + 1;int T, n, L, R, a[kN];
ll l, r, ans;int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> T;while (T--) {cin >> n >> L >> R;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1), l = r = 0;for (int i = 1; i <= n; i++)l += a[i] - L, r += a[i] - R;ans = min(l, r);for (int i = 1; i <= n; i++) {l += (L - a[i]) - (a[i] - L), r += (R - a[i]) - (a[i] - R);ans = max({ans, min(l - (L - a[i]), r - (R - a[i])), min(l, r)});}cout << ans << '\n';}return 0;
}
\(Solution2\)：
巨佬 yq 的做法。显然对于在 \([l, r]\) 以外的点的选法已经固定了，考虑把这些点先算上，最终答案会形成一个一次函数。对于在 \([l, r]\) 内的点，先把 \(k\) 调成 0，再配对选即可
Code
#include <algorithm>
#include <iostream>using namespace std;
using ll = long long;const int kN = 2e5 + 1;int T, n, L, R, a[kN];
ll k, b;int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> T;while (T--) {cin >> n >> L >> R;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) {if (a[i] < L)k++, b -= a[i];else if (a[i] > R)k--, b += a[i];}int l, r;for (l = 1; l <= n && a[l] < L; l++);for (r = n; r >= 1 && a[r] > R; r--);if (k > 0) {for (; r >= l && k; r--)k--, b += a[r];} else {for (; l <= r && k; l++)k++, b -= a[l];}for (; l < r; l++, r--)b += a[r] - a[l];cout << min(k * L + b, k * R + b) << '\n';k = b = 0;}return 0;
}
E. Adjusting Drones
首先需要转化一下题意，这一步是平凡的。接下来同样有两个做法
\(Solution1\)：
jjz 发现从后往前依次把能搞的搞完不回影响原答案。直接用线段树维护每个位置的值，只需要区间覆盖和线段树上二分操作即可
\(Solution2\)：
有更加简单粗暴的做法。直接往前推，能走就走就行。最后对于每一段的答案取个 \(max\)
Code
#include <cassert>
#include <iostream>using namespace std;const int kN = 1e6 + 1;int T, n, k, ans, a[kN];int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);for (cin >> T; T--; ans = 0) {cin >> n >> k;for (int i = 1, x; i <= n; i++)cin >> x, a[x]++;for (int i = 1, s = 0; i <= 2 * n; i++, s = 0) {for (; a[i] > k; i++, s++)a[i + 1] += a[i] - 1;ans = max(ans, s);}fill(a, a + 3 * n + 1, 0);cout << ans << '\n';}return 0;
}