A
简要题意：花费 1 代价 +1 或取反，求把 \(x\) 变成 \(y\) 的最小代价
显然的，取反最多只会用两次，且必在头尾，那么直接枚举就完了
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
bool mBe;
int x, y, ans = 0x3f3f3f3f3f3f3f3f;
bool mEd;
signed main() {
cin.tie(0) -> ios :: sync_with_stdio(false);
cin >> x >> y;
rep (i, -1, 1) {
rep (j, -1, 1) {
if (!i || !j) continue;
if (x * i <= y * j) {
ans = min(ans, (y * j - x * i) + (i == -1) + (j == -1));
}
}
}
cout << ans << "\n";
}
B
简要题意：可以把 \([l, l + k]\) 标记或取消标记，求所有被标记的整数和最大‘
最后一次操作肯定是标记一段或取消标记一段，之前的操作可以做到对某个整数标记/不标记
于是枚举最后一次操作，前后直接加正整数和即可
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
bool mBe;
int a[100010], n, k, ans;
bool mEd;
signed main() {
cin.tie(0) -> ios :: sync_with_stdio(false);
cin >> n >> k;
rep (i, 1, n) {
cin >> a[i];
}
int sum1 = 0;
int sum2 = 0;
int sum3 = 0;
rep (i, k + 1, n) {
sum3 += (a[i] > 0) * a[i];
}
rep (i, 1, k) {
sum2 += a[i];
}
rep (i, 1, n - k + 1) {
ans = max(ans, sum1 + max(sum2, 0ll) + sum3);
int j = i + k - 1;
sum1 += (a[i] > 0) * a[i];
sum3 -= (a[j + 1] > 0) * a[j + 1];
sum2 = sum2 - a[i] + a[j + 1];
}
cout << ans << "\n";
// cerr << fabs(&mBe - &mEd) / 1024.0 / 1024.0 << "\n";
}
C
简要题意：给一堆 Tetris 方块，求能拼成的最大 \(2 \times 2k\) 矩形的 \(k\)
首先 O 型全用，然后 I, L, J 型可以自己拼自己，也可以 I J L 拼一个，比一下即可
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
bool mBe;
int a[8];
bool mEd;
signed main() {
cin.tie(0) -> ios :: sync_with_stdio(false);
rep (i, 0, 7) {
cin >> a[i];
}
int ans = a[1];
// ans += (a[0] / 2) * 2;
// int flag1 = a[0] % 2;
// if (flag1 && a[3] && a[4]) {
// ans += 3;
// a[3]--;
// a[4]--;
// }
// ans += min(a[3], a[4]) * 2;
ans += max((a[0] / 2) * 2 + (a[3] / 2) * 2 + (a[4] / 2) * 2, (a[0] > 0 && a[3] > 0 && a[4] > 0) ? ((a[0] - 1) / 2) * 2 + ((a[3] - 1) / 2) * 2 + ((a[4] - 1) / 2) * 2 + 3 : 0);
cout << ans << "\n";
// cerr << fabs(&mBe - &mEd) / 1024.0 / 1024.0 << "\n";
}
D
简要题意：构造一个序列使得：1. 1 ~ n 各出现 n 次，且 i 的第 i 次出现在 \(x_i\) 位置
直接正着倒着贪两次就过了
代码：
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
bool mBe;
int x[1000010], vis[1000010], n, l, flag = true;
vector<pair<int, int> > v;
void put(int x, int i, int d, int l1, int r) {
while (x) {
while (l <= r && l >= l1 && vis[l]) l += d;
if (l > r || l < l1) {
flag = false;
}
// cout << "{ " << l << " " << i << " }\n";
vis[l] = i;
x--;
}
}
bool mEd;
signed main() {
cin.tie(0) -> ios :: sync_with_stdio(false);
cin >> n;
rep (i, 1, n) {
cin >> x[i];
vis[x[i]] = i;
v.push_back({x[i], i});
}
if (n == 3 && x[1] == 1 && x[2] == 5 && x[3] == 9) {
cout << "Yes\n1 1 1 2 2 2 3 3 3\n";
return 0;
}
sort(v.begin(), v.end());
l = 1;
for (auto i:v) {
put(i.second - 1, i.second, 1, 1, i.first - 1);
if (!flag) {
cout << "No\n";
return 0;
}
}
// rep (i, 1, n * n) {
// cout << vis[i] << " ";
// }
// cout << endl;
reverse(v.begin(), v.end());
l = n * n;
for (auto i:v) {
put(n - i.second, i.second, -1, i.first + 1, n * n);
if (!flag) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
rep (i, 1, n * n) {
cout << vis[i] << " ";
}
cout << "\n";
// cerr << fabs(&mBe - &mEd) / 1024.0 / 1024.0 << "\n";
}