Codeforces Round 1023 (Div. 2) (A-D)

每周至少五篇博客：(1/5)

A. LRC and VIP

题意

您有一个大小 $n$ 的数组 $a$ - $a_1,a_2,\dots a_n$ 。

您需要将 $n$ 元素分为 $2$ 序列 $B$ 和 $C$ ，以满足以下条件：

• 每个元素恰好属于一个序列。
• 两个序列 $B$ 和 $C$ 至少包含一个元素。
• $\gcd$ $(B_1,B_2,\dots ,B_{|B|})\ne \gcd (C_1,C_2,\dots ,C_{|C|})$ ${}^{\text{∗}}$

${}^{\text{∗}}$ $\gcd (x,y)$ 表示[https://en.wikipedia.org/wiki/wiki/greatest_common_divisor） $x$ 和98774178}。

思路

找最大值，把最大值放在一组，其余的放在另一组，如果所有元素值相同，那么无解

代码

void solve() {int n;std::cin >> n;std::vector<PII> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i].first;a[i].second = i;}std::sort(a.begin(), a.end());if (a.front().first == a.back().first) {std::cout << "NO\n";return ;}std::cout << "YES\n";int max = a.back().first;std::sort(a.begin(), a.end(), [](PII p1, PII p2) {return p1.second < p2.second;});for (auto [x, i] : a) {if (x == max) std::cout << "2 ";else std::cout << "1 ";}std::cout << '\n';
}

B. Apples in Boxes

题意

汤姆和杰里在地下室发现了一些苹果。他们决定玩游戏以获取一些苹果。

有 $n$ 盒子， $i$ \ - th框具有 $a_i$ 苹果。汤姆和杰里轮流捡起苹果。汤姆首先。依次，他们必须做以下操作：

• 选择一个带有正数的苹果的盒子 $i$ （ $1\le i\le n$ ），即 $a_i>0$ ，然后从此框中选择 $1$ 苹果。请注意，这减少了 $1$ 的 $a_i$ 。
• 如果没有有效的盒子，当前玩家会输。
• 如果在移动后， $\max (a_1,a_2,\dots a_n)-\min (a_1,a_2,\dots ,a_n)>k$ 持有，那么当前的玩家（最后一步）也会输。

如果两个玩家都在最佳比赛中打球，请预测游戏的获胜者。

思路

如果极差大于 $k+1$ ，那么tom一定会输，或者极差等于 $k+1$， 但是有多个最大值。否则二人会将所有苹果拿光，此时看奇偶性即可

代码

void solve() {int n, k;std::cin >> n >> k;std::vector<i64> a(n);for (int i = 0; i < n; i++) std::cin >> a[i];std::sort(a.begin(), a.end());if (a[n - 1] - a[0] > k + 1) {std::cout << "Jerry\n";return;} else if (a[n - 1] - a[0] == k + 1) {if (a[n - 1] == a[n - 2]) {std::cout << "Jerry\n";return;}}i64 sum = std::accumulate(a.begin(), a.end(), 0ll);if (sum & 1) {std::cout << "Tom\n";} else {std::cout << "Jerry\n";}
}

C. Maximum Subarray Sum

题意

给您一个长度 $n$ 的数组 $a_1,a_2,\dots ,a_n$ 和一个正整数 $k$ ，但是丢失了数组的某些部分 $a$ 。您的任务是填充丢失的部分，以使 $a$ 的最大子阵列总和 ${}^{\text{∗}}$ 完全是 $k$ ，或报告不存在解决方案。

形式上，给您一个二进制字符串 $s$ 和一个部分填充的数组 $a$ ，其中：

• 如果您记住 $a_i$ 的值，则指示这一点，并给出 $a_i$ 的真实值。
• 如果您不记得 $a_i$ 的值， $s_i=0$ 表示这是 $a_i=0$ 。

您记住的所有值满足 $|a_i|\le 10^6$ 。但是，您可以使用最多 $10^{18}$ 的值来填充您不记得的值。可以证明，如果存在解决方案，也存在满足 $|a_i|\le 10^{18}$ 的解决方案。

${}^{\text{∗}}$ 长度 $a$ 的最大子阵列总和 $n$ ，即 $a_1,a_2,\dots a_n$ ，定义为{367999959}其中 ${\max }_{1\le i\le j\le n}S(i,j)$ 其中 $S(i,j)=a_i+a_{i+1}+\dots +a_j$ 。

思路

一个经典的dp——求子数组最大和

定义 $d{p}_i$ 是以 $i$ 为结尾的子数组的最大和

转移考虑选不选第 $i$ 个的元素 $d{p}_i=\max (d{p}_{i-1}+a_i,0)$

回到本题

考虑什么时候无解，就是当在我们填数之前，已经有一个最大的子数组和满足 $>k$ ，此时我们无论怎么操作都无法影响，所以无解

换句话说，如果有解的话，必然满足所有最大子数组和都 $\le k$

另外因为这里涉及到原数组中第 $i$ 个元素是否需要填充的问题，所以在处理子数组最大和时，我们应该根据每个需要填数的位置来将原数组分段，再对每段去跑dp

接下来我们只需要选择任意一个填数的位置，算上这个位置两侧的最大子数组和，这里我们需要维护两个dp，分别表示以 $i$ 为结尾和以 $i$ 为起始的最大子数组和，设填数的位置是 $p$ ，那么加上两侧的最大子数组和是 $d{p}_{p-1}+dp{2}_{p+1}$ ，要让这个和加上我们填的数 $=k$ ，所以这个位置填 $k-d{p}_{p-1}-dp{2}_{p+1}$ ，对于其余位置，填 $-10^{18}$ 即可

代码

void solve() {i64 n, k;std::cin >> n >> k;std::string s;std::cin >> s;s = "?" + s;std::vector<i64> a(n + 10), dp(n + 10), ndp(n + 20);i64 max = -LINF;bool ex = false;for (int i = 1; i <= n; i++) {bool f = (s[i] == '1');std::cin >> a[i];if (f) {dp[i] = std::max(0ll, dp[i - 1] + a[i]);} else {dp[i] = 0;}max = std::max(max, dp[i]);if (!f) ex = true;}for (int i = n; i >= 1; i --) {bool f = s[i] == '1';if (f) {ndp[i] = std::max(0ll, ndp[i + 1] + a[i]);} else {ndp[i] = 0;}max = std::max(max, ndp[i]);}if ((max != k && !ex) || max > k) {std::cout << "NO\n";return ;}std::cout << "YES\n";for (int i = 1; i <= n; i ++) if (s[i] == '0') {a[i] = k - dp[i - 1] - ndp[i + 1];s[i] = '1';break;}for (int i = 1; i <= n; i ++) if (s[i] == '0') a[i] = -LINF;for (int i = 1; i <= n; i ++) std::cout << a[i] << " ";std::cout << '\n';
}

D. Apple Tree Traversing

题意

有一个带有{888877302}节点的苹果树，最初在每个节点处有一个苹果。您有一张纸，最初没有写任何东西。

只要剩下至少一个苹果，就可以在苹果树上穿越苹果树：

• 选择Apple路径 $(u,v)$ 。当且仅当对路径上的每个节点{894444091}上的每个节点时，路径 $(u,v)$ 被称为Apple路径，上面有一个Apple。
• 令 $d$ 为路径上的苹果数量，按照本顺序在纸上写下三个数字 $(d,u,v)$ 。
• 然后删除路径上的所有苹果 $(u,v)$ 。

在这里，路径 $(u,v)$ 是指从 $u$ 到 $v$ 的唯一最短步行中的顶点。

让纸上的数字序列为 $a$ 。您的任务是找到词典上最大的序列 $a$ 。

思路

考虑简化问题——只需要求出第一个三元组即可

那么答案是 $d$ 是树的直径， $u,v$ 是满足距离为 $d$ 的同时且编号最大的两个点

这个三元组是确定的答案，不存在第二种符合条件的三元组

接下来将 $u-v$ 这条路径的所有边在树上去掉，会发现有多出来了若干棵树，而对于其中每棵树的答案实际上和上面一样都是固定的，并且求法一样

所以可以想到要用分治去做

关于求直径也是很经典的问题了，先任意选一个点进行dfs，把其他点到这个点的距离求出来，然后选择距离最远的点 $u$ ，再用这个点 $u$ dfs一次求距离，得到的距离 $u$ 最远的点 $v$ ，这两个点 $u,v$ 的路径就是直径

在这里要多一次遍历，将 $u,v$ 换成编号最大的点

关于删除路径，只需要用一个数组 $exis{t}_u$ 表示 $u$ 是否还存在于树即可，然后求 $u,v$ 的LCA $w$，接下来遍历 $u-w,v-w$ 两条路径，将每个点都 $exis{t}_i=false$ 即可，至于求LCA我这里是直接用了前两天写的博客的板子[算法学习]——通过RMQ与dfs序实现O(1)求LCA（含封装板子），实际上想了想好像暴力就够了

关于遍历，我们要用一个数组去存当前分治处理的这棵子树有哪些节点，直接 $1-n$ 遍历的话会TLE

这个题思路挺好想，但是代码比较难实现，细节可以看代码

关于时间复杂度是 $O(能过)$ ，不太懂证明，听群友说均摊下来是 $n\sqrt{n}$

代码

#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;typedef std::pair<long long, long long> PII;
const int mod = 998244353;
const int N = 2e6 + 1000;
const int INF = 0x3f3f3f3f;
const long long LINF = 1e18;
const double eps = 1e-12;
const double pi = std::acos(-1);
std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<u64> dist_rand(mod / 2, mod - 1);struct LCA {int n, LOG;std::vector<int> l, r, id, dep, parent, lg;std::vector<std::vector<int>> st;const std::vector<std::vector<int>>& adj;int tot = 0;// 构造函数：传入节点数 n（假设节点编号 1..n）、邻接表 adj、根节点 rootLCA(int _n, const std::vector<std::vector<int>>& _adj, int root): n(_n), adj(_adj){LOG = 32 - __builtin_clz(n);  // ⌊log2(n)⌋ 的上界l.assign(n+1, 0);r.assign(n+1, 0);id.assign(n+1, 0);dep.assign(n+1, 0);parent.assign(n+1, 0);lg.assign(n+2, 0);// 预处理对数for (int i = 2; i <= n; i++)lg[i] = lg[i>>1] + 1;// 1) 建立 dfs 序，记录 l[u], r[u], id[]dfs(root, 0);// 2) 构建 ST 表用于 RMQst.assign(LOG+1, std::vector<int>(n+2));// 第一层直接存序列上的节点编号for (int i = 1; i <= n; i++)st[0][i] = id[i];// 其余层for (int j = 1; j <= LOG; j++) {for (int i = 1; i + (1<<j) - 1 <= n; i++) {int x = st[j-1][i];int y = st[j-1][i + (1<<(j-1))];// 取深度更小（即在树上更靠近根）的那个st[j][i] = (dep[x] < dep[y] ? x : y);}}}// 返回节点 u 在序列中的位置 l[u], 以及构造 parent, depvoid dfs(int u, int p) {parent[u] = p;dep[u] = dep[p] + 1;l[u] = ++tot;id[tot] = u;for (int v : adj[u]) {if (v == p) continue;dfs(v, u);}r[u] = tot;}// O(1) 查询 LCAint lca(int u, int v) const {// 如果 u 是 v 的祖先，直接返回 u；反之同理if (l[u] <= l[v] && r[u] >= r[v]) return u;if (l[v] <= l[u] && r[v] >= r[u]) return v;// 保证 l[u] < l[v]if (l[u] > l[v]) std::swap(u, v);// 在序列 [l[u]..l[v]] 上做 RMQ，找到深度最小的节点 xint L = l[u], R = l[v];int k = lg[R-L+1];int x1 = st[k][L], x2 = st[k][R - (1<<k) + 1];int x  = (dep[x1] < dep[x2] ? x1 : x2);// 这个 x 一定是 u 到 v 路径上，且最靠近根的那个孩子节点，// 它的 parent 就是 LCAreturn parent[x];}
};void solve() {int n;std::cin >> n;std::vector go(n + 1, std::vector<int>());for (int i = 1; i < n; i ++) {int u, v;std::cin >> u >> v;go[u].emplace_back(v);go[v].emplace_back(u);}LCA lca(n, go, 1);int tot = 0;std::vector<int> e(n + 1, 1), f(n + 1), col(n + 1);auto dfs2 = [&](auto &&dfs2, int u, int fa) -> void {f[u] = fa;for (auto v : go[u]) {if (v == fa) continue;dfs2(dfs2, v, u);}};dfs2(dfs2, 1, 1);auto dfs = [&](auto &&dfs, int u, int fa, auto &d, int &sz) -> void {d[u] = d[fa] + 1;sz ++;col[u] = tot;for (auto v : go[u]) {if (v == fa || e[v] == 0) continue;dfs(dfs, v, u, d, sz);}};std::vector<int> s;auto dfs3 = [&](auto &&dfs3, int u, int fa) -> void {s.emplace_back(u);for (auto v : go[u]) {if (v == fa || e[v] == 0) continue;dfs3(dfs3, v, u);}};std::vector<std::array<int, 3>> ans;std::vector<int> d1(n + 1), d2(n + 1);auto solve = [&](auto &&solve, int root) -> void {d1[root] = 0;int sz = 0;tot ++;s.clear();dfs3(dfs3, root, root);dfs(dfs, root, root, d1, sz);if (sz == 1) {ans.push_back({1, root, root});e[root] = 0;return ;}for (int i = 1; i <= n; i ++) if (col[i] == tot) s.emplace_back(i);int max = 0, p = 0, q = -1;for (int i : s) if (d1[i] >= max) {max = d1[i];p = i;}d2[p] = 0;dfs(dfs, p, p, d2, sz);max = 0, p = 0;for (int i : s) if (d2[i] >= max) {max = d2[i];p = i;}d1[p] = 0;dfs(dfs, p, p, d1, sz);for (int i : s) if (d1[i] >= max && p != i) q = i;if (p < q) std::swap(p, q);ans.push_back({max, p, q});int w = lca.lca(q, p);while (p != w) e[p] = 0, p = f[p];while (q != w) e[q] = 0, q = f[q];e[w] = false;for (int i : s) if (e[i]) {solve(solve, i);}};solve(solve, 1);std::sort(ans.begin(), ans.end(), std::greater<>());for (auto [d, u, v] : ans) std::cout << d << ' ' << u << ' ' << v << ' ';std::cout << '\n';
}signed main() {std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int tmp = 1;std::cin >> tmp;while (tmp--)solve();return 0;
}