A.Moving Chips (思维)
题意：
给一个长度为 n n n的数组 a a a， a i = 1 a_i=1 ai=1或者 a i = 0 a_i=0 ai=0，现在可以选择一个 1 1 1，然后将其与左侧最近的 0 0 0交换。询问使得所有的 1 1 1连在一起，中间没有 0 0 0至少需要多少次操作。
分析：
可以发现答案为从第一个 1 1 1到最后一个 1 1 1的子串中 0 0 0的数量。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int a[N];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int l = INF, r = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 1)
l = min(i, l), r = max(i, r);
}
int ans = 0;
for (int i = l; i <= r; i++) {
if (a[i] == 0)
ans++;
}
cout << ans << endl;
}
return 0;
}
B.Monsters Attack! (前缀和)
题意：
有 n n n个怪物在一个数轴上，每个怪物位于 x i x_i xi处，有生命值 h i h_i hi，玩家处于数轴 0 0 0位置处，每一秒都会进行以下操作：
- 玩家选择一些怪物，并为他们分配总计 k k k点伤害。
- 怪物生命值小于等于 0 0 0认定死亡
- 所有生命值大于 0 0 0的怪物都向玩家所在位置前进一个单位。如果存在怪物到达 0 0 0，玩家失败。
分析：
对于第 i i i个怪物，需要在 x i x_i xi秒前造成至少 k k k点伤害， n u m [ i ] num[i] num[i]表示 1 − i 1-i 1−i秒需要造成的伤害，如果伤害大于 k k k，就表明失败。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int t;
cin >> t;
while (t--) {
LL n, k;
cin >> n >> k;
LL a[n + 1], x[n + 1];
vector<LL> num(n + 1, 0);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
num[abs(x[i])] += a[i];
for (int i = 1; i <= n; i++)
num[i] += num[i - 1];
int flag = 0;
for (int i = 1; i <= n; i++) {
if (num[i] > i * k) {
flag = 1;
break;
}
}
if (flag)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
return 0;
}
C. Find B (思维)
题意：
一个长度为 m m m的数组 a a a被认为是好的，当且仅当满足下列条件：
- 存在数组 b b b， b i > 0 , a i ≠ b i b_i>0,a_i \neq b_i bi>0,ai=bi， ∑ i = 1 m a i = ∑ i = 1 m b i \sum\limits_{i=1}^{m} a_i=\sum\limits_{i=1}^{m} b_i i=1∑mai=i=1∑mbi
给出一个数组 c c c和区间 l , r l,r l,r，询问子数组 c l ∼ c r c_l \sim c_r cl∼cr是不是好的。
分析：
长度为 1 1 1的区间显然无解。对于长度不为 1 1 1的区间，如果所有的元素都大于 1 1 1，那么可以将所有数大于 1 1 1的部分加到其中一个数字上，一定有解。如果区间内存在若干个 1 1 1，那么需要判断区间内大于 1 1 1的部分能否将区间内的每个 1 1 1都至少加上 1 1 1。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector<LL> sum(n + 1), cnt1(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
sum[i] = sum[i - 1] + x;
cnt1[i] = cnt1[i - 1] + (x == 1);
}
while (q--) {
int l, r;
cin >> l >> r;
if (l == r) {
cout << "NO" << endl;
continue;
}
LL tmp = sum[r] - sum[l - 1] - (r - l + 1);
if (tmp >= cnt1[r] - cnt1[l - 1]) {
cout << "YES" << endl;
} else
cout << "NO" << endl;
}
}
return 0;
}
D.Slimes (二分)
题意：
有 n n n个史莱姆排成一排，第 i i i个史莱姆的大小为 a i a_i ai，每一秒都会进行如下操作：
- 选择两个大小不同的并且相邻的史莱姆，较大的史莱姆将吞噬较小的史莱姆，且大小变为两者之和。
询问对于每一个史莱姆，最少需要几秒才能被吞噬，如果不可能被吞噬，输出 − 1 -1 −1。
分析：
对于一个史莱姆，可以从左右两个方向来选择一段区间合并出一个大史莱姆将其吞噬，首先需要保证区间内数字和大于 a i a_i ai，可以通过二分出满足条件的左右端点。其次需要判断区间内的数字是否不完全相同，只要不完全相同都可以通过吞噬得到一个更大的史莱姆，可以通过维护一个数字往前/往后第一个与其不同的数字的位置来进行判断。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n + 5);
vector<LL> sum(n + 5);
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
vector<int> pre(n + 5), suf(n + 5);
for (int i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
pre[i] = pre[i - 1];
} else {
pre[i] = i - 1;
}
}
suf[n] = n + 1;
for (int i = n - 1; i >= 1; i--) {
if (a[i] == a[i + 1]) {
suf[i] = suf[i + 1];
} else {
suf[i] = i + 1;
}
}
for (int i = 1; i <= n; i++) {
int ans = INF;
if (sum[i - 1] > a[i]) {
int l = 0, r = i - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (sum[i - 1] - sum[mid - 1] > a[i])
l = mid;
else
r = mid - 1;
}
if (r == i - 1) {
ans = min(ans, 1);
} else if (pre[i - 1] != 0) {
ans = min(ans, max(i - r, i - pre[i - 1]));
}
}
if (sum[n] - sum[i] > a[i]) {
int l = i + 1, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (sum[mid] - sum[i] > a[i])
r = mid;
else
l = mid + 1;
}
if (r == i + 1) {
ans = min(ans, 1);
} else if (suf[i + 1] != n + 1) {
ans = min(ans, max(r - i, suf[i + 1] - i));
}
}
if (ans == INF)
ans = -1;
cout << ans << " ";
}
cout << endl;
}
return 0;
}
E.Count Paths (启发式合并)
题意：
给出一棵 n n n个节点的树，每个节点有着颜色 c i c_i ci，询问满足以下条件的路径的数量：
- 至少经过两个节点
- 起始节点和终止节点颜色相同，并且和路径上的节点的颜色不相同
分析：
有两种满足要求的路径：
- 一个点是另一个点的祖先
- 两个节点没有祖先关系
遍历每一个节点，使用 m a p map map记录子树内没有被祖先覆盖过的每种颜色的点的数量，再利用启发式合并来进行统计，满足上述要求的两种路径都可以在启发式合并的过程中求出来。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<LL> c(n + 5);
vector<vector<LL>> g(n + 5);
for (int i = 0; i < n; i++)
cin >> c[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector<map<LL, LL>> dp(n + 5);
LL ans = 0;
auto dfs = [&](auto self, int u, int p) -> void {
for (auto v: g[u]) {
if (v == p)
continue;
self(self, v, u);
}
for (auto v: g[u]) {
if (v == p)
continue;
if (dp[v].size() > dp[u].size()) {
swap(dp[u], dp[v]);
}
}
for (auto v: g[u]) {
if (v == p)
continue;
for (auto [x, y]: dp[v]) {
if (x != c[u])
ans += y * dp[u][x];
dp[u][x] += y;
}
}
ans += dp[u][c[u]];
dp[u][c[u]] = 1;
};
dfs(dfs, 0, -1);
cout << ans << endl;
}
return 0;
}
赛后交流
在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。
群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。
![LeetCode 刷题 [C++] 第236题.二叉树的最近公共祖先](https://img-blog.csdnimg.cn/direct/17587ee6080a41c1843524b11bebff7b.png)
