20240926 模拟赛总结
\(10+30+30+10=80\)，有挂惨了。
比赛链接：http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9
或 http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9
A - 智乃的差分
题意：
给定一个数列 \(a_n\)（\(0\le a_i\le 10^9\)），你可以重排这个数组，问是否存在一种排序方式，使得 \(a\) 的差分数组 \(d\) 中不出现 \(x\) 这个数，若可以，求输出方案。
思路：
考虑当 \(a\) 数组升序排序时，差分数组中都是正数，那么可以解决 \(x\) 为负数的情况，所以我们考虑按照 \(x\) 的符号分类讨论。
\(x<0\) 讨论完了，下面讨论 \(x>0\) 或 \(x=0\)。
当 \(x>0\) 时，考虑降序排序数组 \(a\)，那么 \(d\) 中的 \(2\) 到 \(n\) 个元素全是负数，但是第一个数可能等于 \(x\)，考虑将后面的一个属交换到前面，我们要保证这个数不等于 \(x\) 且不等于 \(0\)，若没有这样的数就输出 no。
当 \(x=0\) 时，就是要满足重排后的数组的第一个元素不为 \(0\) 且没有相邻的相同元素，这是一个很经典的问题，我们每次找到出现次数最多的元素，若这个数与前面的数不相同，那么就使用这个数，否则使用出现次数次大的元素，将这些数放在另一个答案数组中并在原数组中删除。由于出现次数时持续变化的，所以需要用优先队列维护。
代码：
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e5 + 5;
int T, n, m, x, a[kMaxN], b[kMaxN], p, tot, f;
map<int, int> mp;
int main() {
freopen("difference.in", "r", stdin);
freopen("difference.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
for (cin >> T; T; T--) {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (x < 0) {
sort(a + 1, a + 1 + n);
cout << "yes\n";
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
} else if (x > 0) {
sort(a + 1, a + 1 + n, greater<int>());
if (x != a[1]) {
cout << "yes\n";
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
} else {
p = -1;
for (int i = 1; i <= n; i++) {
a[i] != a[1] && a[i] && (p = i);
}
if (p == -1) {
cout << "no\n";
} else {
cout << "yes\n" << a[p] << ' ';
for (int i = 1; i <= n; i++) {
i != p && (cout << a[i] << ' ');
}
cout << '\n';
}
}
} else {
mp.clear(), f = 0;
priority_queue<pair<int, int>> q;
for (int i = 1; i <= n; i++) {
mp[a[i]]++, b[i] = 0;
}
for (pair<int, int> i : mp) {
q.push({i.second, i.first});
}
for (int i = 1; i <= n; i++) {
pair<int, int> now = q.top();
q.pop();
if (now.second == b[i - 1]) {
if (q.size()) {
pair<int, int> tmp = q.top();
q.pop(), b[i] = tmp.second, q.push(now);
if (--tmp.first) {
q.push(tmp);
}
} else {
f = 1;
break;
}
} else {
b[i] = now.second;
if (--now.first) {
q.push(now);
}
}
}
if (!f) {
cout << "yes\n";
for (int i = 1; i <= n; i++) {
cout << b[i] << ' ';
}
cout << '\n';
} else {
cout << "no\n";
}
}
}
return 0;
}
B - 牛牛的旅行
题意：
给定一颗 \(n\) 个节点的树，每个点有一个点权，定义一条简单路径的权值为路径中点权的最大值减去路径的长度，求树上所有长度不为 \(0\) 的简单路径的权值和模 \(10^9+7\) 的值。
思路：
首先可以将两种操作分开，计算所有路径的长度和可以用换根 dp 求解，很板，不做讨论，下面只讲如何求解所有路径经过点权的最大值的和。
经过一条边一定会经过这条边的两个端点，所以我们可以将边的边权转化为两个端点的点权最大值，然后题目就转化为树上所有简单路径经过的最大边权之和，这就是 ABC214D 了。
讲一下这怎么做，可以先将所有边按照边权从小到大排序，然后遍历每一条边，用并查集维护所有比当前边权小的所有边连接的点的连通块，那么只需要在这条边的端点的连通块任选点的简单路径的最大值都是这条边的边权，这就做完了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e6 + 5, kM = 1e9 + 7;
int n, a[kMaxN], siz[kMaxN], fa[kMaxN], sz[kMaxN];
long long ans, f[kMaxN];
vector<int> g[kMaxN];
bitset<kMaxN> vis;
struct E {
int u, v, w;
} e[kMaxN];
void dfs(int u, int fa, int dep) {
siz[u] = 1, f[1] += dep;
for (int v : g[u]) {
if (v != fa) {
dfs(v, u, dep + 1), siz[u] += siz[v];
}
}
}
void dfs2(int u, int fa) {
for (int v : g[u]) {
if (v != fa) {
f[v] = f[u] + n - 2 * siz[v], dfs2(v, u);
}
}
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { (x = find(x)) != (y = find(y)) && (fa[y] = x, sz[x] += sz[y]); }
int main() {
freopen("tour.in", "r", stdin);
freopen("tour.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i], fa[i] = i, sz[i] = 1;
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v, e[i] = {u, v, max(a[u], a[v])}, g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0, 0), dfs2(1, 0);
sort(e + 1, e + n, [](E i, E j) { return i.w < j.w; });
for (int i = 1; i < n; i++) {
if (find(e[i].u) != find(e[i].v)) {
ans = (ans + 1LL * sz[find(e[i].u)] * sz[find(e[i].v)] % kM * e[i].w) % kM, merge(e[i].u, e[i].v);
}
}
cout << (ans * 2 % kM - accumulate(f + 1, f + 1 + n, 0LL) % kM + kM) % kM;
return 0;
}