Codeforces Round #728 (Div. 2) ABC 题解 (Java/C++)

A. Pretty Permutations

题解

显然,只需要相邻两位相互交换位置即可。对于n等于奇数的情况,只需最后三位相互交换即可。

代码

Java

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

C++

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

B. Pleasant Pairs

题解

对原数组a排序。于是,对于任意一个j,我们可以按a值从小到大枚举。一旦发现其乘积大于2n就不再往后枚举。这样时间复杂度大约是$\frac{n}{a_1}+\frac{n}{a_2}+\frac{n}{a_3}+...\frac{n}{a_n}$。

代码

Java

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

C++

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

C. Great Graphs

题解

显然,为了正值尽可能小,我们尽可能的复用之前的路径。于是正值的路大概如下图:

接着,我们为了负值尽可能大,于是我们顺着正值的路依次构建即可:

代码

Java

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

C++

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