Codeforces Round #759 ABCD 题解 (Java/C++)

A. Life of a Flower

题解

按照题意模拟即可。

代码

Java

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

C++

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

B. Array Eversion

题解

显然,当最大值位于数组的最右端时,数组不再发生变化。
而每次操作后,最右侧的值会变为从右往左第一个比当前最右端的值大的数。

因此我们只需要找出经过多少次操作后,最右端的值变为数组的最大值即可。

代码

Java

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

C++

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

C. Minimize Distance

题解

显然,除了最后一次送货之外,每次送货完成后都会需要返回原点。因此最后一次送货应当尽可能远一点。
同时,远处的送货应当尽可能带满货物。

因此我们从远到近,一次往返带货,最后我们再减去最后一次带货返回的路程即可。

代码

Java

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

C++

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

D. Yet Another Sorting Problem

题解

首先如果有重复的数字,那么我们可以通过两个相同的数字加上一个不同的数字实现两个数字的互换位置。因此,如果有相同的数字,则一定是YES。

而对于没有重复数字的情况。我们可以观察到,每次操作之后,数组的逆序对数目只会变化2。比如[1,2,3,4,5],我们对2,3,4执行操作后,变成了[1,4,2,3,5],逆序对数目由0变成了2。
因此我们只需要用线段树维护出逆序对的数目即可,如果数目是偶数,则YES,否则NO。

代码

Java

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

C++

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