目录
写在前面
比赛地址：https://codeforces.com/contest/1921
写完 C 题去泡了个面边吃边看 D，吃着吃着不对劲味儿怎么这么冲一看过期两个月了我草
以及 div3 都 AK 不了了呃呃博弈论把我鲨了
还剩最后一门近代史，周四才考，开摆！
感觉除了离散可能有点拉其他都还好，C++概率论大物怎么考那么傻逼啊妈的
A
四个点排个序即得左下角和右上角的点，即可直接求面积。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
std::pair <int, int> p[5];
for (int i = 1; i <= 4; ++ i) p[i] = std::make_pair(read(), read());
std::sort(p + 1, p + 4 + 1);
printf("%d\n", (p[4].first - p[1].first) * (p[4].second - p[1].second));
}
return 0;
}
B
分别求两个数列中该位置为 1 且另一数列中该位置为 0 的位置的数量，取最大值即为答案。
正确性显然，最优方案显然是将该数列中满足上述条件的位置与另一数列中满足上述条件的位置交换，然后再删或补使得 1 的数量相等，总操作数即为上述所求。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n;
std::string a, b;
int cnt[2];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
std::cin >> a;
std::cin >> b;
cnt[0] = cnt[1] = 0;
for (int i = 0; i < n; ++ i) {
if (a[i] == b[i]) continue;
cnt[b[i] == '1'] ++;
}
printf("%d\n", std::max(cnt[0], cnt[1]));
}
return 0;
}
C
模拟。
考虑每个时间间隔是一直开机或者关机，取电量消耗的最小值即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, a, b;
LL f;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), f = read(), a = read(), b = read();
int last = 0, flag = 1;
for (int i = 1; i <= n; ++ i) {
int m = read(), t = m - last;
f -= std::min(1ll * a * t, 1ll * b);
if (f <= 0) flag = 0;
last = m;
}
printf("%s\n", flag ? "YES" : "NO");
}
return 0;
}
D
仅关心对应位置值的差，显然可以对两个数列任意重排。
先考虑 \(n=m\) 的情况，则等价于重排数列以最大化对应位置的残差和，即最da化残差平方的和。由经典题 [NOIP2013 提高组] 火柴排队，则令 A 升序排序 B 降序排序即可。
然后考虑 \(n \le m\) 的情况。基于上述排序后两数列的形态贪心地考虑，应使得 A 中的较小值对应 B 中的较大值，A 中的较大值对应 B 中的最小值，即 A 升序排序 B 降序排序后，A 的一段前缀对应 B 的等长的后缀，除去这段前缀的 A 的后缀对应 B 的等长的前缀。于是先预处理 A 所有长度的前/后缀与 B 等长的后/前缀对应时的贡献和，再枚举上述前缀和后缀的分界线统计答案取最大值即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, a[kN], b[kN];
LL sum1[kN], sum2[kN], ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T -- ) {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= m; ++ i) b[i] = read();
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + m + 1);
sum1[0] = sum2[n + 1] = ans = 0;
for (int i = 1, j = m; i <= n; ++ i, -- j) sum1[i] = sum1[i - 1] + 1ll * abs(b[j] - a[i]);
for (int i = n, j = 1; i >= 1; -- i, ++ j) sum2[i] = sum2[i + 1] + 1ll * abs(b[j] - a[i]);
for (int i = 0; i <= n; ++ i) ans = std::max(ans, sum1[i] + sum2[i + 1]);
printf("%lld\n", ans);
}
return 0;
}
E
我没脑子妈的
F
对于一次询问 \(s, d, k\)，显然有 \(d\times k \le n\)，一眼根号分治。
\(k\le \sqrt{n}\) 时直接暴力；\(k\ge \sqrt{n}\) 时肯定有 \(d\le \sqrt{n}\)，于是考虑预处理 \(\operatorname{sum}(i, j)\) 表示询问 \(s = i(1\le i\le n), d = j(1\le j\le \sqrt{n}), k = \infin\) 时的答案，\(\operatorname{suf}(i, j)\) 表示询问 \(s = i, d = j, k = \infin\) 访问到的所有位置的和，则任意 \(d\le \sqrt{n}\) 的询问 \(s, d, k\) 答案即为：
\[\operatorname{sum}(s,d) - \operatorname{sum}(s + d\times k,d) - k \times \operatorname{suf}(s + d\times k,d) \]预处理时空复杂度均为 \(O(n\sqrt{n})\) 级别，总时间复杂度 \(O(n\sqrt{n} + m\sqrt{n})\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kSqrtN = 320;
//=============================================================
int n, q, sqrtn, a[kN];
LL pre[kN + kSqrtN], suf[kN + kSqrtN][kSqrtN], sum[kN + kSqrtN][kSqrtN];
int s, d, k;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read(), q = read();
sqrtn = sqrt(n) + 1;
for (int i = 1; i <= n; ++ i) a[i] = read();
pre[0] = 0;
for (int i = 1; i <= n; ++ i) pre[i] = pre[i - 1] + a[i];
for (int i = 1; i <= sqrtn; ++ i) {
for (int j = n + 1; j <= n + sqrtn + 1; ++ j) sum[j][i] = suf[j][i] = 0;
for (int j = n; j >= 1; -- j) {
sum[j][i] = sum[j + i][i] + suf[j + i][i] + a[j];
suf[j][i] = suf[j + i][i] + a[j];
}
}
}
LL Query() {
LL ret = 0;
if (k < sqrtn) {
for (int i = 1, j = s; i <= k; ++ i, j += d) {
ret += 1ll * i * a[j];
}
return ret;
}
int t = s + d * k;
if (t > n) {
return sum[s][d];
} else {
return sum[s][d] - sum[t][d] - 1ll * k * suf[t][d];
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
while (q --) {
s = read(), d = read(), k = read();
printf("%lld ", Query());
}
printf("\n");
}
return 0;
}
G
我有一个傻逼码农暴力做法，可惜这里空太小，写不下。
还没调出来，背会儿近代史再写妈的。
写在最后
学到了什么：
- D：最小化两个数列对应位置残差和令第 \(k\) 大对应第 \(k\) 大；最大化则反之。
- F：\(d\times k\le n\) 可根号分治。