A. Single Push
题意
给你两个等长度数组 $a$，$b$，问你是否可以选择或不选数组 $a$ 的一段连续子段，子段每个元素都加上 $k$，使得两数组均相等？
大概思路
题意不难，难的是如何快速写实现。
我们直接对两个数组作差，然后消掉前后缀的连续 $0$，最后再判断剩下的部分是否含 $0$ 即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n), b = a;
for (auto &i : a) std::cin >> i;
for (auto &i : b) std::cin >> i;
for (int i = 0; i < n; i++) {
a[i] -= b[i];
a[i] = -a[i];
if (a[i] < 0) {
std::cout << "NO\n";
return;
}
}
int i = 0;
for (; i < n; i++) {
if (a[i] != 0) break;
}
int j = n - 1;
for (; j >= 0; j--) {
if (a[j] != 0) break;
}
std::set<int> s;
for (int k = i; k <= j; k ++) {
s.insert(a[k]);
}
std::cout << (s.size() <= 1 ? "YES\n" : "NO\n");
}
B. Silly Mistake
题意
给你一个数组，问你是否可以将其分成若干个子数组（不得改变相对位置），使得每个子数组满足如下规则：
- 每种元素只能出现一次
- 绝对值相等的一对元素，正数必须出现在负数前面
- 子数组元素和为 $0$
大概思路
直接模拟即可，考虑贪心，当前已经选取到的子数组元素和为 $0$ 时，立马切割，一定是最优的。如果操作到不能再进行操作时，输出 $-1$ 即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
i64 sum = 0;
for (auto &i : a) (std::cin >> i), sum += i;
if (sum != 0 || a.back() > 0) {
std::cout << -1 << "\n";
return;
}
std::vector<int> ans;
int cnt_ = 1;
int in = 1;
std::set<int> cnt;
cnt.insert(a[0]);
for (int i = 1; i < n; i++) {
cnt_++;
if (a[i] > 0) {//收到正数（入）
if (!cnt.count(a[i])) {//没出现过，加入
cnt.insert(a[i]);
in++;
} else {
std::cout << -1 << "\n";
return;
}
} else {//收到负数（出）
if (!cnt.count(-a[i])) {//没出现过
std::cout << -1 << "\n";
return;
} else {//出现过
in--;
}
}
if (in == 0) {
ans.push_back(cnt_);
cnt_ = 0;
cnt.clear();
}
}
std::cout << ans.size() << "\n";
for (auto &u : ans) std::cout << u << " ";
std::cout << "\n";
}
C. Sweets Eating
题意
津杉给轻音乐俱乐部带来了 $n$ 颗美味的糖果。它们的编号从 $1$ 到 $n$ ，其中 $i$ /th的糖果的糖浓度用整数 $a_i$ 来描述。
Yui 喜欢吃甜食，但出于健康考虑，她每天最多只能吃 $m$ 种甜食。
天数编号从 $1$ 开始（依次为 $1, 2, 3, \ldots$ ）。在第 $d$ 天食用 $i$ 种甜食会导致 $(d \cdot a_i)$ 的糖分惩罚，因为随着时间的推移，甜食的糖分会越来越高。一种甜食最多只能吃一次。
糖分惩罚的总和将是每种甜食的糖分惩罚的 总和。
假设小伊选择了 $k$ 种甜食，并按照任意顺序吃完。她能得到的 最少 总糖罚分是多少？
由于小依是一个犹豫不决的女孩，她希望您能回答 $1$ 和 $n$ 之间 $k$ 的每一个值。
大概思路
稍加分析可知，先对原数组排序，然后选前 $k$ 小的元素，从大到小吃，最后的和一定是最小的（排序不等式：反序和 $\le$ 乱序和 $\le$ 正序和）
那么我们要考虑怎么优化这个统计过程，直接暴力统计是 $O(n^2)$ 的，肯定会超时。
考虑当前处理是第 $k + 1$ 个答案，那么 $k$ 的答案肯定是已经处理好的，我们手玩一下样例，看看能不能从前一个答案递推过来。
容易发现，当处理第 $k + 1$ 个答案时，只有 $k + 1，k + 1 - m， k + 1 - 2m，\dots$ 处的贡献发生了变化。那么我们只需要预处理出一个序号公差不为 $1$ 的前缀和，然后每次更新答案的时候，加上 $pre[i]$ 即可。
这个预处理是 $O(n)$ 的，不会超时。
参考代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<i64> a(n);
for (auto &i : a) std::cin >> i;
std::sort(a.begin(), a.end());
std::vector<i64> pre(n);
for (int i = 0; i < m; i++) {
pre[i] = a[i];
for (int j = i + m; j < n; j += m) {
pre[j] += a[j] + pre[j - m];
}
}
i64 ans = 0;
for (int i = 0; i < n; i++) {
ans += pre[i];
std::cout << ans << " ";
}
std::cout << "\n";
}
D. Harmonious Graph
题意
给你一个有 $n$ 个节点的无向图，让你连上最少的边数，使得“若任意两个节点 $l，r(l < r)$之间可达，那么 $l，k（l < k < r）$ 之间也是可达的”成立。
大概思路
其实题意可以转化为，给你若干个联通块，问你最少合并几次，可以让每个联通块内部的元素均是连续的（即，如果一个联通块有 $1$ 和 $3$，那么这个联通块一定含有 $2$）。
考虑从小到大遍历每个元素，同时维护一个“截至到第 $i$ 个元素，访问过的联通块的内部元素最大值” $MAX$。若当前访问到的元素 $i$ 与 $MAX$ 不在一个并查集里，且 $i < MAX$ 那么必须连边。
遍历一遍，统计连边次数即可。
参考代码
const int N=200005;
int F[N], mx[N];//维护并查集元素最大最小值
int find(int x) {
if(F[x]!=x) {
int t=F[x];//暂存其亲戚
F[x]=find(F[x]);
mx[x] = std::max(mx[x], mx[t]);
}
return F[x];
}
void join(int x,int y){
int Fx=find(x),Fy=find(y);
if(Fx!=Fy){
F[Fx]=Fy;
mx[Fy] = std::max(mx[Fy], mx[Fx]);
}
}
void solve() {
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++) F[i] = mx[i] = i;
while (m--) {
int x, y;
std::cin >> x >> y;
join(x, y);
}
int mxx = mx[1];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (find(mxx) != find(i) && i < mxx) {
ans++;
join(mxx, i);
}
mxx = std::max(mxx, mx[i]);
}
std::cout << ans;
}