目录
写在前面
比赛地址：https://codeforces.com/contest/1976
满课，并且 48 小时之内只睡了 8h。
本来不想打的，但是手痒就上小号打了，然而唐唐唐掉大分呃呃
A
签到。
感谢 isdigit 函数。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
std::string s; std::cin >> s;
int flag = 1;
for (int i = 1; i < n; ++ i) {
if (!isdigit(s[i - 1]) && isdigit(s[i])) flag = 0;
}
for (int i = 0, lst = -1; i < n; ++ i) {
if (isdigit(s[i])) {
if (lst == -1) lst = i;
else if (s[lst] > s[i]) flag = 0;
lst = i;
}
}
for (int i = 0, lst = -1; i < n; ++ i) {
if (!isdigit(s[i])) {
if (lst == -1) lst = i;
else if (s[lst] > s[i]) flag = 0;
lst = i;
}
}
std::cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
B
模拟。
对 \(a_1\sim a_n\) 的调整的代价是固定的，即为 \(\sum_{1\le i\le n} |a_i - b_i|\)。在对它们调整的过程中需要选择一个数复制一份变为 \(a_{n + 1}\)，并最小化调整 \(a_{n + 1}\) 至 \(b_{n + 1}\) 的代价 \(|b_{n + 1} - a_{n + 1}|\)。
显然若存在 \(1\le i\le n\)，使得 \(\min(a_i, b_i) \le b_{n + 1}\le \max(a_i, b_i)\)，则 \(|b_{n + 1} - a_{n + 1}|\) 的值可以为 0；否则选择的被复制的数一定在集合 \(\{a_i\} +\{b_i\}\) 中，选择其中与 \(b_{n + 1}\) 最接近的数复制并计算代价即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], b[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
for (int i = 1; i <= n + 1; ++ i) std::cin >> b[i];
LL ans = 0, flag = 0;
for (int i = 1; i <= n; ++ i) {
ans += abs(a[i] - b[i]);
if (std::min(a[i], b[i]) <= b[n + 1] && b[n + 1] <= std::max(a[i], b[i])) flag = 1;
}
if (!flag) {
LL delta = 1e9;
for (int i = 1; i <= n; ++ i) {
delta = std::min(delta, 1ll * abs(b[n + 1] - a[i]));
delta = std::min(delta, 1ll * abs(b[n + 1] - b[i]));
}
ans += delta;
}
std::cout << ans + 1 << "\n";
}
return 0;
}
C
排序。
读错题了唐唐唐唐唐——获得了一道新题哈哈，什么时候需要就放上去。
首先假设 \(n + m + 1\) 个人全部到来，按照题意进行模拟找到其较优岗位并求得贡献之和。
然后按照到来顺序，分别枚举每个岗位中的人 \(i\)，记该岗位人数上限为 \(k\)：
- 若这个人之前已经有 \(k\) 个人入职，则这个人不来贡献减少 \(\min(a_i, b_i)\)。
- 若这个人之前不到 \(k\) 个人入职，且以该岗位为较优岗位的人少于 \(k\) 个，则这个人不来贡献减少 \(\max(a_i, b_i)\)。
- 否则这个不来一定会使得第 \(k\) 个人入职该岗位，则贡献变化量为 \(-\max(a_i, b_i) + \max(a_{k}, b_{k}) - \min(a_k, b_k)\)。
讨论即可，总时间复杂度 \(O(n+m)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2e5 + 10;
//=============================================================
int n, m;
LL sum, ans[kN];
std::vector<int> aa, bb;
int a[kN], b[kN], c[kN];
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> m;
sum = 0;
aa.clear(), bb.clear();
for (int i = 1; i <= n + m + 1; ++ i) std::cin >> a[i];
for (int i = 1; i <= n + m + 1; ++ i) {
std::cin >> b[i];
c[i] = abs(a[i] - b[i]);
sum += std::min(a[i], b[i]);
}
int cnta = 0, cntb = 0;
for (int i = 1; i <= n + m + 1; ++ i) {
if (a[i] > b[i]) {
++ cnta;
if (cnta <= n) sum += a[i] - b[i];
aa.push_back(i);
} else {
++ cntb;
if (cntb <= m) sum += b[i] - a[i];
bb.push_back(i);
}
}
for (int i = aa.size() - 1; i >= n; -- i) ans[aa[i]] = sum - b[aa[i]];
if ((int) aa.size() <= n) {
for (int i = 0; i < (int) aa.size(); ++ i) ans[aa[i]] = sum - a[aa[i]];
} else {
for (int i = n - 1; i >= 0; -- i) ans[aa[i]] = sum - a[aa[i]] + c[aa[n]];
}
for (int i = bb.size() - 1; i >= m; -- i) ans[bb[i]] = sum - a[bb[i]];
if ((int) bb.size() <= m) {
for (int i = 0; i < (int) bb.size(); ++ i) ans[bb[i]] = sum - b[bb[i]];
} else {
for (int i = m - 1; i >= 0; -- i) ans[bb[i]] = sum - b[bb[i]] + c[bb[m]];
}
for (int i = 1; i <= n + m + 1; ++ i) std::cout << ans[i] << " ";
std::cout << "\n";
}
return 0;
}
D
括号序列，枚举。
好玩题，场上一直想着怎么拆成两半拼起来了，还能这么想的 oonp。
写在最后
参考：
学到了什么：
- D：括号序列的又一种数形结合的模型转换。