Codeforces Round #891 (Div. 3) ABCDEFG 题解 (Java/C++)

A. Array Coloring

题解

只有总和是偶数才可能分成两个奇偶性相同的两拨。

代码

Java

C++

B. Maximum Rounding

题解

从右往左依次四舍五入即可。

代码

Java

C++

C. Assembly via Minimums

题解

首先，我们考虑$a$中不存在重复元素的场景。
那么显然$\min(a_i)$一定会出现$n-1$次，倒数第二小的$a_i$会出现$n-2$次。以此类推。第二大的数会出现1次。最大的数并不会出现。

接着考虑可能重复的场景。发现并没有什么区别。
因为假设存在两个相同的数，都是倒数第二小。那么就认为一个是倒数第二，另一个是倒数第三即可。

综上，统计$b$中每个数出现的次数。
然后从小到大依次遍历，假设第$b_i$小的数是第$j$小的数。那么就$count[b_i]$减去$n-j$。如果$count[b_i]$没有变成0，说明第$j+1$小的数和第$j$小的数是一样的。

代码

Java

C++

D. Strong Vertices

题解

$a_u-a_v \geq b_u-b_v$等价于$a_u-b_u \geq a_v-b_v$。
所以对于直接针对任意点$i$，计算$a_i-b_i$。所有最大的$a_i-b_i$都是答案。

代码

Java

C++

E. Power of Points

题解

首先，不难发现$\sum\limits_{p=1}^{10^9}f_p$的本质是所有区间的长度和。
因为对于每一个$p$，如果他在$[s, x_i]$，那么就会且只会给结果加1。所以区间内的每个数都恰好会被加一次。

那么就不难想到，我们可以对$x_i$进行排序。这样我们就能让$s$从小到大依次枚举。
当$s$从$x_i$变为$x_{i+1}$时。所有$i$左边的区间（包括$i$）的长度都增加了$x_{i+1}-x_i$。所有$i$右边的区间（不包括$i$）长度都减少了$x_{i+1}-x_i$。
所以$ans[i+1]=ans[i]+i\cdot(x_{i+1}-x_i)-(n-i)\cdot(x_{i+1}-x_i)$

最后在把$ans$根据下表重新排序即可。

代码

Java

C++

F. Sum and Product

题解

将$a_j=x-a_i$带入$a_i\cdot a_j=y$可得$a_i^2-x\cdot a_i+y=0$。所以$a_i=\frac {x\pm\sqrt{x^2-4\cdot y}} {2}$。
所以只需要看$a_i$有没有整数解，以及有多少个这样的$a_i$。

同时需要注意的是，$a_j$算出来可能和$a_i$相等。另外$a_i$本身可能存在两个解，但也可能只存在一个解。

代码

Java

C++

G. Counting Graphs

题解

考虑最小生成树的生成过程，我们考虑每条边从小到大依次添加到树中的过程。

当合并两个并查集的子集时，除了连接两个集合的边之外，本身还可以有$size[u]\cdot size[v] - 1$条边。这些边的长度有$s-w$种可能（其中$w$表示新添加的那条边的长度）。加上不要这条边，每条可能的边共有$\max(s-w+1, 1)$种可能。
所以，合并两个集合会产生$\max(s-w+1, 1)^{size[u]\cdot size[v] - 1}$种可能。

所以，当添加第$i$条边的时候，新的子集总有$ans[u]\cdot ans[v] \cdot \max(s-w+1, 1)^{size[u]\cdot size[v] - 1}$种可能。（其中$ans[u]$表示$u$所在的子集的可能数）

代码

Java

C++