Shiroha白羽的博客
·
Codeforces Round 891 (Div. 3)
💡
原文中文，约6700字，阅读约需16分钟。
📝
内容提要
这篇文章讨论了Codeforces第891轮（Div. 3）的几道题目，包括数组着色、最大四舍五入、通过最小值组装、强顶点、点的幂、求和与乘积、计数图等。每道题目提供了解决思路和方案，涉及数组操作、图论和数学计算等算法技巧。
🎯
关键要点
- A. 数组着色：将数组中的值分成两组，判断奇数个数的奇偶性来决定是否可行。
- B. 最大四舍五入：通过找到第一个大于等于5的值进行进位，计算最大值。
- C. 通过最小值组装：反推原数组，通过已排序数组的规律得到新数组。
- D. 强顶点：通过变形公式判断图中节点的可达性，找到满足条件的节点。
- E. 点的幂：计算区间命中的数量，维护左右区间的贡献。
- F. 求和与乘积：通过二元一次方程求解满足条件的不同对数。
- G. 计数图：在边权重不超过S的情况下，计算不同图的数量，确保最小生成树为给定树。
❓
延伸问答
如何判断数组着色的可行性？
通过判断原数组中奇数的个数的奇偶性来决定是否可行。
最大四舍五入的计算方法是什么？
从左往右找到第一个大于等于5的值进行进位，然后判断进位后的值是否大于等于5。
如何通过最小值组装得到原数组？
反推原数组，通过已排序数组的规律得到新数组。
强顶点问题的关键判断条件是什么？
判断条件是 a_i - b_i >= max_{j=1}^n(a_j - b_j)，满足此条件的节点可以到达所有其他节点。
如何计算点的幂？
计算区间命中的数量，维护左右区间的贡献。
求和与乘积问题的解法是什么？
通过二元一次方程求解满足条件的不同对数。
🏷️
标签
➡️
