本文主要是介绍Codeforces 969 div2[A~E] 个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
A - Dora's Set
原题链接
思路分析
AC代码
B - Index and Maximum Value
原题链接
思路分析
AC代码
C - Dora and C++
原题链接
思路分析
AC代码
D - Iris and Game on the Tree
原题链接
思路分析
AC代码
E - Iris and the Tree
原题链接
思路分析
AC代码
A - Dora's Set
原题链接
A - Dora's Set
思路分析
显然不能选两个偶数
比较简单的结论：
任意相邻的两个数一定互质
任意相邻的两个奇数一定互质
于是得出：
那么两个奇数 中间 夹一个偶数一定合法，并且这样得到的三元组是最多的
时间复杂度：O(N)，当然可以做到O(1)
AC代码
#include <bits/stdc++.h>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int l, r;std::cin >> l >> r;int res = 0;for (int i = l & 1 ? l : l + 1; i + 1 < r; i += 4) {++ res;}std::cout << res << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}B - Index and Maximum Value
原题链接
B - Index and Maximum Value
思路分析
我们注意到一个事情，由于每次操作都是对值域内的元素操作
那么从始至终，我们数组最大元素的下标始终不变（自己手玩一下就明白了）
时间复杂度：O(N)
AC代码
#include <bits/stdc++.h>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(n);for (int i = 0; i < n; ++ i) std::cin >> a[i];int ma = *std::max_element(a.begin(), a.end());for (int i = 0; i < m; ++ i) {char op;int l, r;std::cin >> op >> l >> r;if (l <= ma && ma <= r)ma += op == '+' ? 1 : -1;std::cout << ma << " \n"[i + 1 == m];}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}C - Dora and C++
原题链接
C - Dora and C++
思路分析
根据裴蜀定理：给定x，y存在ax + by = gcd(x, y)
那么我们可以实现对每个元素任意次 gcd(a, b) 加减操作
那么我们一定可以将原数组的元素都调整到 [0, gcd(a, b)) 内
显然我们可以得到的 range 不会超过 gcd(a, b)
我们将调整后的数组排序，枚举最小值 c[i]
为什么最小值可以取原数组的元素？
因为任意最优解我们都可以通过整个数组加减gcd来使得其最小值落在[0, gcd(a, b))内
那么枚举最小值后，最大值是哪个？
对于最小值c[i]，最大值一定是c[i - 1] + gcd
很明显，不做证明
时间复杂度：O(NlogN)
AC代码
#include <bits/stdc++.h>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n, a, b;std::cin >> n >> a >> b;int g = std::gcd(a, b);std::vector<int> c(n);for (int i = 0; i < n; ++ i) std::cin >> c[i], c[i] %= g;std::ranges::sort(c);int res = c[n - 1] - c[0];for (int i = 1; i < n; ++ i) {res = std::min(res, c[i - 1] + g - c[i]);}std::cout << res << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}D - Iris and Game on the Tree
原题链接
D - Iris and Game on the Tree
思路分析
看起来很复杂，我们不妨先考虑比较好想的情况：根节点值确定
那么我们 Iris 一定将叶子尽可能染成和树根相反的值，Dora 一定尽可能将叶子染成和树根相同的值
记叶子中原来0的数目为c0，1的数目为c1，？为none
那么当root = 0时，Iris的收益就是 (none + 1) / 2 + c1
root=1不再赘述
当根节点值不确定：
这个时候我们发现，如果Iris先手调根，那么不管调几，Dora总能让Iris的收益减少
所以Iris要晚调根，同样的，Dora也要晚调根
那么当非叶子结点存在 ？时，二者都会先去调这些结点
这些结点数目的奇偶性决定了二者谁先手调根
所以我们分为两种情况，Iris先手调根：收益就是 max(c0, c1) + none / 2
当 可以使Dora先手的时候，收益是：min(c0, c1) + (none + 1) / 2
第二种情况可以取的时候需要和第一种情况取max
时间复杂度：O(N)
AC代码
#include <bits/stdc++.h>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n;std::cin >> n;std::vector<int> d(n);for (int i = 1, u, v; i < n; ++ i) {std::cin >> u >> v;-- u, -- v;++ d[u], ++ d[v];}std::string s;std::cin >> s;int c0 = 0, c1 = 0, f = 0, none = 0;for (int i = 1; i < n; ++ i) {if (d[i] == 1) {if (s[i] == '0') ++ c0;else if(s[i] == '1') ++ c1;else ++ none;}else if (s[i] == '?') {f ^= 1;}}if (s[0] == '?') {int res = std::max(c0, c1) + none / 2;if (f)res = std::max(res, std::min(c0, c1) + (none + 1) / 2);std::cout << res << '\n';}else {if (s[0] == '1') std::cout << c0 + (none + 1) / 2 << '\n';else std::cout << c1 + (none + 1) / 2 << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}E - Iris and the Tree
原题链接
E - Iris and the Tree
思路分析
对于每个path，其收益为 w - 路径外已经确定的边权和
但是要进行特判：如果路径上边全部确定，那么其值就是路径权值和
然后可以注意到每条边在所有路径中一共出现两次
初始时，收益为n * w
最一般的情况：后面每增加一条边，除了该边出现的两条路径，所有的路径的值都会- 2f
如果考虑已经满了的路径，我们发现我们的收益就是：
已满路径的带权长度和 + 未满路径条数 * (w - 已出现路径长度和) + Σ未满路径上已出现的边权和
那么对于一条边<p[u], u>如何找到两条路径的端点？
u - 1 和 u所在子树最大dfs序，第二个我们逆着dfs序进行递推即可
由于给的是dfs序，lca(i, (i + 1) % n) = fa(i + 1)，所以我们可以很容易处理出每条路径的边的数目
时间复杂度：O(N)
AC代码
#include <bits/stdc++.h>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n;i64 w;std::cin >> n >> w;std::vector<int> p(n), d(n), res(n), submax(n);std::vector<std::vector<int>> adj(n);for (int i = 1; i < n; ++ i) {std::cin >> p[i], -- p[i];adj[p[i]].push_back(i);}for (int u = 0; u < n; ++ u)for (int v : adj[u])d[v] = d[u] + 1;for (int i = 0; i + 1 < n; ++ i) res[i] = d[i] + d[i + 1] - d[p[i + 1]] * 2;res[n - 1] = d[n - 1];std::iota(submax.begin(), submax.end(), 0);for (int i = n - 1; i; -- i)submax[p[i]] = std::max(submax[i], submax[p[i]]);std::vector<i64> len(n);i64 ans = 0, sum = 0, o = 0;int cnt = 0;for (int i = 1, v; i < n; ++ i) {i64 t;std::cin >> v >> t;-- v;int u = v - 1, sub = submax[v];sum += t;len[u] += t, len[sub] += t;o += 2 * t;if (!-- res[u]) {ans += len[u];o -= len[u];++ cnt;}if (! -- res[sub]) {ans += len[sub];o -= len[sub];++ cnt;}std::cout << ans + (n - cnt) * (w - sum) + o << " \n"[i + 1 == n];}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}这篇关于Codeforces 969 div2[A~E] 个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
