Codeforces Round 891 (Div. 3)
内容提要
这篇文章讨论了Codeforces第891轮（Div. 3）的几道题目，包括数组着色、最大四舍五入、通过最小值组装、强顶点、点的幂、求和与乘积、计数图等。每道题目提供了解决思路和方案，涉及数组操作、图论和数学计算等算法技巧。
延伸解读
题目覆盖与算法类型
本轮 Div.3 共包含七道题目，从 A 到 G 依次涉及数组奇偶性判断、贪心进位、构造与反推、图论可达性、区间贡献统计、二元方程求解以及最小生成树计数。整体难度梯度明显，适合不同水平的选手练习。其中 G 题被作者评价为“很不错”，需要结合并查集和组合计数，是本次比赛中最具挑战性的一题。
关键解题思路提示
A 题只需统计奇数个数；B 题从左往右找到第一个不小于 5 的数字后连续进位；C 题利用排序后最小值出现次数的规律反推原数组；D 题通过变形不等式发现只需比较 a_i - b_i 的最大值；E 题排序后维护左右区间贡献；F 题转化为二元一次方程并利用平方根判断整数解；G 题按边权排序后用并查集合并子树，并计算可添加边的组合数。
实现细节与注意事项
多题代码中使用了宏定义 int long long 来避免溢出，例如 D、E、F、G 题。F 题需要特判两个解相同的情况，用组合数计算对数；G 题模数为 998244353，并查集合并时需计算新增可连边数量，再乘以权值选择数的幂次。B 题处理字符串数字时需注意进位后可能产生前导 1。这些细节容易在比赛中出错，需仔细检查。
Q&A
如何判断数组着色的可行性？
通过判断原数组中奇数的个数的奇偶性来决定是否可行。
最大四舍五入的计算方法是什么？
从左往右找到第一个大于等于5的值进行进位，然后判断进位后的值是否大于等于5。
如何通过最小值组装得到原数组？
反推原数组，通过已排序数组的规律得到新数组。
强顶点问题的关键判断条件是什么？
判断条件是 a_i - b_i >= max_{j=1}^n(a_j - b_j)，满足此条件的节点可以到达所有其他节点。
如何计算点的幂？
计算区间命中的数量，维护左右区间的贡献。
求和与乘积问题的解法是什么？
通过二元一次方程求解满足条件的不同对数。
