Codeforces Round 891 (Div. 3) 题解

发布时间 2023-08-09 09:14:15作者: cantorsort2919

A. Array Coloring

因为:

偶数+偶数=偶数

奇数+奇数=偶数

奇数+偶数=奇数

所以设 \(s1\) 为奇数之和,\(s2\) 为偶数之和

\(s2\) 必定是偶数

如果奇数的个数为偶数,则 \(s1\) 为偶数;否则是奇数

而在 \(s1\) 为奇数时,即使拿一个奇数加到 \(s2\) 里,那么也是不合法的

所以直接判断奇数的个数是否为奇数即可

B. Maximum Rounding

取最高的可以“五入”的位进行四舍五入即可

C. Assembly via Minimums

\(a\) 的最小值,必定至少在 \(b\) 中出现 \(n-1\) 次,接着以此类推即可

D. Strong Vertices

\(a_u-a_v\ge b_u-b_v\) 移项,得 \(a_u-b_u\ge a_v-b_v\)

所以我们统计一个 \(c_i=a_i-b_i\),那么最后只需要看有多少个 \(c_i\) 满足它大于等于所有数即可

这个值显然为 \(c\)中的最大值,因此我们需要做的就是统计 \(c\) 中最大值的数量

这里可以直接排序,为了方便第二问,同时要存储位置

E. Power of Points

显然题目所要求的就是各段长度之和

那么我们将各点排序,先求出最小的点的答案,易得当点 \(p_i\) 转移到 \(p_{i+1}\) 时,实际上是与 \(p_{i+1}\) 左边的每个点都增加了这一段的长度、右边都减少了,因此可递推得出答案

F. Sum and Product

根据题意我们有:\(b=a_i+a_j,c=a_i\times a_j\)

可以发现 \(a_i\)\(a_j\) 是一元二次方程 \(x^2-bx+c=0\) 的根

那么就可以根据求根公式 \(x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\) 来求出 \(a_i\)\(a_j\) 的值,再将它们的数量相乘即为答案

\(b^2-4ac\le 0\) 的情况要特判

G. Counting Graphs

(待补)