Codeforces Round 881 (Div. 3)
A - Sasha and Array Coloring (CF1843 A)
题目大意
给定一个数组，给每个元素涂色。求最大的代价。
代价为每个颜色的代价和。
每个颜色的代价为涂了该颜色的元素的极差。
解题思路
因为是极差，每个元素要么对答案有正的贡献，要么有负的贡献，要么无贡献。且正负贡献的个数要相同。
因为要最大值，自然就是想有正贡献的是最大的那些数，负贡献的是最小的那些数。
因此答案就是最大的那一半的和\(-\)最小的那一半的和。奇数的话中间多出来的一个无贡献。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a)
cin >> i;
sort(a.begin(), a.end());
int ans = -accumulate(a.begin(), a.begin() + n / 2, 0) + accumulate(a.end() - n / 2, a.end(), 0);
cout << ans << '\n';
}
return 0;
}
B - Long Long (CF1843 B)
题目大意
给定一个数组，可以进行一个操作。要求最小化操作数，使得数组元素的和最大。
操作为：选定一个区间，对区间里的每个元素取其相反数。
解题思路
很显然，和最大一定是将所有的负数变为正数。
然后考虑如何求最小操作数。
对于一连串的负数，我们肯定选择这个区间，这样操作一次就好了。
对于\(----+---\)，如果我们一次选定这个区间，后续还需要一次操作将里面的 +变回来，其操作次数跟只操作其中的负区间的次数是一样的，都是两次。不会更优。
因此就对每个负区间进行操作，答案就是这里面负区间的个数了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a)
cin >> i;
LL ans = 0;
for(auto &i : a)
ans += abs(i);
int cnt = 0;
bool neg = (a[0] < 0);
for(auto &i : a){
if (i > 0 && neg){
cnt ++;
neg = false;
}else if (i < 0)
neg = true;
}
cnt += neg;
cout << ans << ' ' << cnt << '\n';
}
return 0;
}
C - Sum in Binary Tree (CF1843 C)
题目大意
给定一棵完全二叉树，点权为其标号。问从\(n\)号点开始，不断往父亲节点走，其点权和是多少。
解题思路
父亲节点的标号为\(\frac{n}{2}\)，因此直接模拟即可，走 \(\log\)次就走到根了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
LL n;
cin >> n;
LL ans = 0;
while(n){
ans += n;
n >>= 1;
}
cout << ans << '\n';
}
return 0;
}
D - Apple Tree (CF1843 D)
题目大意
给定一棵有根树。树上有两个苹果。每一时刻，每个苹果可以往其中一个儿子节点移动。最终移动到叶子处。
设两个苹果最终所处的叶子节点为\(a,b\)，问 \((a,b)\)的情况数。
解题思路
如果一个苹果在\(x\)节点，那么它能移动的叶子处就是以 \(x\)为根的叶子节点，如果有 \(a\)个叶子，那么该苹果的可移动到的叶子数就是 \(a\)。
现在有两个苹果，假设它们最终可移动到的叶子节点数分别为\(a,b\)，那最终的情况数就是 \(a \times b\)。
因此事先预处理\(son[x]\)表示以\(x\)为根的叶子数量，\(O(1)\)回答即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<vector<int>> edge(n);
for(int i = 1; i < n; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
}
vector<int> son(n, 0);
function<void(int, int)> dfs = [&](int u, int fa){
bool leaf = true;
for(auto &v : edge[u]){
if (v == fa)
continue;
leaf = false;
dfs(v, u);
son[u] += son[v];
}
son[u] += leaf;
};
dfs(0, 0);
int q;
cin >> q;
while(q--){
int u, v;
cin >> u >> v;
-- u, -- v;
cout << 1ll * son[u] * son[v] << '\n';
}
}
return 0;
}
E - Tracking Segments (CF1843 E)
题目大意
给定一个有\(n\)个\(0\)的数组\(a\)，以及 \(m\)个区间。
一个区间如果是好区间，则其间 \(1\)的个数严格大于 \(0\)的个数。
现依次进行 \(q\)次操作，每次操作将 \(a_x = 1\)。
问最早进行了多少次操作后，出现好区间。
解题思路
我们可以依次枚举\(q\)，得到操作后的数组，接下来就是判断每个区间是不是 好区间，即判断\(1\)的个数和 \(0\)的个数的大小关系。朴素判断是\(O(nm)\)，但我们可以事先对 \(1\)的个数求一遍数组\(a\)的前缀和 ，这样每个区间的判断都可以在\(O(1)\) 得出结果，判断的复杂度降为\(O(n + m)\)。
由于我们是枚举\(q\)的，此时时间复杂度为 \(O(q(n + m))\)，但可以发现 \(q\)与是否存在 好区间是一个单调的函数，即如果\(q=4\)存在 好区间，那么\(q > 4\)也一定存在好区间，因此我们可以二分这个 q，得到其临界点。
最终时间复杂度降为\(O((n + m)\log q)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<array<int, 2>> seg(m);
for(auto &i : seg){
cin >> i[0] >> i[1];
-- i[0], -- i[1];
}
int q;
cin >> q;
vector<int> pos(q);
for(auto &i : pos){
cin >> i;
-- i;
}
auto check = [&](int x){
vector<int> cnt(n, 0);
for(int i = 0; i < x; ++ i)
cnt[pos[i]] = 1;
partial_sum(cnt.begin(), cnt.end(), cnt.begin());
for(auto &[l, r] : seg){
int one = cnt[r];
if (l > 0)
one -= cnt[l - 1];
int zero = r - l + 1 - one;
if (one > zero)
return true;
}
return false;
};
int l = 0, r = q;
while(l + 1 < r){
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
if (!check(r))
r = -1;
cout << r << '\n';
}
return 0;
}
F1 - Omsk Metro (simple version) (CF1843 F1)
题目大意
给定一棵点权为\(1\) 或\(-1\)的树，点数为\(n\)。
给定\(q\)个询问\(u, v, k\)，依次回答从\(u \to v\)这条路径中，是否存在一个子区间，其和为 \(k\)。
该题\(u = 1\)
解题思路
子区间和可以转换成两个前缀和作差，那么在一般的问题里，我们可以枚举每个前缀和，若其值为\(x\)，那就看之前的前缀和是否有值为 \(x - k\)的。
很显然本题里，复杂度是\(O(nq)\)，无法通过。但本题有个奇特点为点权仅为\(1\)或 \(-1\)，这其间或许有什么性质。
容易发现，假设一个区间的最大字段和为 \(max\)，最小字段和为 \(min\)，那么 \([min, max]\)区间的数都可以取到，即都存在对应的子区间。因为点权仅为\(1\)或 \(-1\)，一个子区间左右扩张，其值只会加一或者减一，不会跳跃，而初始值为 \(0\)。
因此问题就转换成维护一个区间的子区间的最大值和最小值即可。这是一个简单的\(dp\)，即设 \(dp[i]\)表示以 \(i\)结尾的最大后缀和，然后再维护一个全局的最大值。最小值同理。
由于本题中 \(u = 1\)，因此可以直接从 \(1\)开始 \(dfs\)，维护这个 \(dp\)即可。撤销\(dp\)相当于回溯。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<vector<int>> edge(n + 1);
vector<int> val(n + 1);
vector<vector<int>> target(n + 1);
vector<int> q;
val[0] = 1;
int cur = 1;
for(int i = 0; i < n; ++ i){
string op;
cin >> op;
if (op[0] == '+'){
int v, x;
cin >> v >> x;
-- v;
edge[v].push_back(cur);
edge[cur].push_back(v);
val[cur] = x;
++ cur;
}else{
int u, v, k;
cin >> u >> v >> k;
-- u, -- v;
assert(u == 0);
target[v].push_back(int(q.size()));
q.push_back(k);
}
}
vector<int> ans(q.size());
function<void(int, int, int, int, int, int)> dfs = [&](int u, int fa, int maxx, int minn, int gmaxx, int gminn){
for(auto &t : target[u]){
ans[t] = (q[t] <= gmaxx && q[t] >= gminn);
}
for(auto &v : edge[u]){
if (v == fa)
continue;
int nmaxx = max({maxx + val[v], val[v], 0});
int nminn = min({minn + val[v], val[v], 0});
int ngmaxx = max(gmaxx, nmaxx);
int ngminn = min(gminn, nminn);
dfs(v, u, nmaxx, nminn, ngmaxx, ngminn);
}
};
dfs(0, 0, 1, 0, 1, 0);
for(auto &i : ans)
if (i)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
return 0;
}
F2 - Omsk Metro (hard version) (CF1843 F2)
题目大意
给定一棵点权为\(1\) 或\(-1\)的树，点数为\(n\)。
给定\(q\)个询问\(u, v, k\)，依次回答从\(u \to v\)这条路径中，是否存在一个子区间，其和为 \(k\)。
解题思路
本题\(u \neq 1\)。
在上一题中，我们将问题转换成维护一个区间的子区间的最大值和最小值。
注意到这个信息是可合并的。以最大值为例。
假设我们有一个左区间和一个右区间，现在我们要将其合并成一个大区间，并求其子区间的最大值。
那么该最大值只有三种情况：
- 左区间的最大值
- 右区间的最大值
- 左区间的最大后缀和+右区间的最大前缀和
因此我们只需要额外增加最大前缀和和最大后缀和这两个信息，我们就可以将两个区间合并，得到新区间的最大值。
而为了维护最大前缀和和最大后缀和，还需要区间和这个信息，因为新区间的最大前缀和有两种情况：
- 左区间的
最大前缀和 - 左区间的
区间和+右区间的最大前缀和
最大后缀和同理，因此我们只要维护一个区间的
- 最大值、最小值
- 最大前缀和、最小前缀和
- 最大后缀和、最小后缀和
- 区间和
这些信息，我们就可以将两个区间合并，得到一个大区间的信息。
可合并有什么用呢？
每次询问其实就是询问一个区间的最大子区间和和最小子区间和，因为这些区间的数量级是\(O(n^2)\)，我们不可能一一计算，而是通过只计算某些区间，这样其他区间都可以通过这些区间，以较少的代价合并得到。
回想下 \(st\)表，它可以 \(O(1)\)回答出任意一个区间的最值，但它预处理的复杂度只有 \(O(n\log n)\)，也就是说它可以通过计算 \(n\log n\)个区间的最值，然后以\(O(1)\)的代价通过 这些计算好的区间，合并出任意区间的最值（注意最值这个信息也是可合并的）。而它用到的方法就是倍增。
同样，既然我们要维护的信息是可合并的，我们可以运用倍增的思想，即树上倍增，对于每个点，维护以这个点往父亲方向，一共\(2^j\)个点所组成的序列的信息，然后对于每个询问所对应的路径，通过 倍增的方式可以拆成\(\log\)个区间进行合并 。
假设询问\(u \to v\)，因为在树上，我们可以在它们的\(lca\)点拆开，这样\(u \to lca\), \(v \to lca\)就是一条链，通过倍增合并得到其信息（跟倍增求lca是一样的），最后再将\(u \to lca\)和\(v \to lca\)合并（注意\(v \to lca\)信息的前后缀要反转过来）即得到\(u \to v\)的信息。
这样每次询问的复杂度就是\(O(\log n)\)了。
当然因为是可合并的，树链剖分将一个路径剖分成若干条轻链和重链合并也不是不行
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct info{
int max, premax, sufmax;
int min, premin, sufmin;
int sum;
};
info operator+(const info& a, const info& b){
info c;
c.max = max({a.max, b.max, a.sufmax + b.premax});
c.premax = max(a.premax, a.sum + b.premax);
c.sufmax = max(b.sufmax, b.sum + a.sufmax);
c.min = min({a.min, b.min, a.sufmin + b.premin});
c.premin = min(a.premin, a.sum + b.premin);
c.sufmin = min(b.sufmin, b.sum + a.sufmin);
c.sum = a.sum + b.sum;
return c;
}
info reverse(const info& a){
info c = a;
swap(c.premax, c.sufmax);
swap(c.premin, c.sufmin);
return c;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> val(n + 1);
val[0] = 1;
int cur = 1;
vector<array<int, 3>> q;
vector<vector<int>> fa(32, vector<int>(n + 1));
vector<int> deep(n + 1);
for(int i = 0; i < n; ++ i){
string op;
cin >> op;
if (op[0] == '+'){
int v, x;
cin >> v >> x;
-- v;
val[cur] = x;
fa[0][cur] = v;
deep[cur] = deep[v] + 1;
++ cur;
}else{
int u, v, k;
cin >> u >> v >> k;
-- u, -- v;
q.push_back({u, v, k});
}
}
vector<vector<info>> up(32, vector<info>(n));
for(int i = 0; i < n; ++ i){
if (val[i] == 1){
up[0][i] = info{1,1,1,0,0,0,1};
}else{
up[0][i] = info{0,0,0,-1,-1,-1,-1};
}
}
for(int i = 1; i < 32; ++ i){
for(int j = 0; j < n; ++ j){
fa[i][j] = fa[i - 1][fa[i - 1][j]];
if (fa[i - 1][j] != fa[i][j])
up[i][j] = up[i - 1][j] + up[i - 1][fa[i - 1][j]];
}
}
auto find = [&](int u, int v){
if (deep[u] < deep[v])
swap(u, v);
int dis = deep[u] - deep[v];
info l{}, r{};
for(int i = 0; i < 32; ++ i){
if (dis & 1){
l = l + up[i][u];
u = fa[i][u];
}
dis >>= 1;
}
if (u == v){
return l + reverse(up[0][u]);
}
for(int i = 31; i >= 0; -- i){
if (fa[i][u] != fa[i][v]){
l = l + up[i][u];
r = r + up[i][v];
u = fa[i][u];
v = fa[i][v];
}
}
int lca = fa[0][u];
l = l + up[0][u];
r = r + up[0][v];
return l + up[0][lca] + reverse(r);
};
auto solve = [&](int u, int v, int k){
auto res = find(u, v);
return res.min <= k && k <= res.max;
};
for(auto &[u, v, k] : q)
if (solve(u, v, k))
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
return 0;
}