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

A. Array Coloring

题解

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

代码

Java

Submission #225888154 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #225888154 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Maximum Rounding

题解

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

代码

Java

Submission #225892772 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226330656 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #225899533 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226331048 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #225900889 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226331191 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #225904182 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226332773 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #226449851 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226334011 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #226330031 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #226334555 - Codeforces
Codeforces. Programming competitions and contests, programming community