Codeforces Round #740 Div 2 ABCDE 题解 (Java/C++)

A. Simply Strange Sort

题解

此题按照题目要求模拟即可。

代码

Java

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

C++

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

B. Charmed by the Game

题解

首先如果k在结果中,那么n-k也一定在结果中。因为将一开始的主客场交换,那么对于同样的排列,可以得到两个不同的答案。

接着,不妨考虑最小的k的构造方式:显然,我们可以贪心的分配即可。以a=7,b=4为例,我们把奇数场和偶数场分开,我们指定Alice出现在奇数场,Borys出现在偶数场时不会break,于是我们可以如下图分配:

接着,基于上图,我们可以依次交换A和B,如下图所示:

再结合n-k,就能得出所有可能。

代码

Java

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

C++

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

C. Deep Down Below

题解

显然,我们可以很容易的得出每个洞穴所需要的最低初始等级。再根据洞穴需要的最低等级进行排序,依次通过,并更新所需要的初始等级即可。

代码

Java

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

C++

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

D. Up the Strip

题解

令dp[x]表示,走到x时,有dp[x]种做法。显然dp[1]就是我们要的答案,dp[n]=1。我们依次从n到1计算dp即可。

其实不难发现$dp[x]=\sum_{i=x+1}^ndp[i]+\sum_{j=2}^{x\cdot j <=n}{\sum_{i=j\cdot x}^{j\cdot(x+1)-1}dp[i]}$。

首先考虑较为简单的$\sum_{i=x+1}^ndp[i]$部分。这一部分其实就是第一种操作的可能性。以x=5为例,显然,5后面的所有数都能通过第一种操作到达5。

接着考虑$\sum_{j=2}^{x\cdot j <=n}{\sum_{i=j\cdot x}^{j\cdot(x+1)-1}dp[i]}$,也就是第二种操作。我们考虑各个数通过除以j到达x。显然当$j\cdot x \leq y\leq j\cdot(x+1)-1$时,$\lfloor \frac{y}{j} \rfloor=x$。
以x=5,j=2为例,显然10和11,可以通过除以2到达5。再以x=3,j=3为例,9,10,11,12都可以通过除以3达到3。

于是很显然,我们维护dp的后缀和,记为f[x]。可以将原dp表达式简化为$dp[x]=f[x+1]+\sum_{j=2}^{x\cdot j <=n}(f[j\cdot x] - f[j\cdot (x+1)])$。
不难发现对于每一个x,j都有$\frac n x$种可能。因此总共需要计算$\frac{n}{1}+\frac{n}{2}+\dots+\frac{n}{n-1}+\frac{n}{n}$,因此其复杂度为$O(n\cdot log(n))$。

代码

Java

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

C++

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

E. Bottom-Tier Reversals

题解

显然,因为p只能选奇数。因此,排序前和排序后的下标的奇偶性一定不会发生改变。因此,如果如果发现奇偶性不一致,那么直接输出-1即可。

同时,不难想到,我们一定是从右往左依次排序,且当我们把一个奇数位的值恢复正确时,他前一个偶数位也一定同时恢复正确。因此我们可以依次推论出下列五种场景:

1. 如下图所示,两个数已经倒序在最开头。这种情况,我们直接令p=7进行倒转即可。

2. 如下图所示,两个数顺序的排在某个不正确的位置。那么我们令p=5,就可以得到第1种情况。

3. 如下图所示,如果两个数逆序排在某个位置。令p=7,我们就可以得到第2种情况。

4. 如下图所示,如果两个数不连续,且奇数在第一位。令p=5,我们就能得到第3种情况。

5. 如下图所示,如果两个数不连续,且奇数不在第一位。令p=3,我们就能得到第4种情况。

因此,最多需要5步。而每走完这5步,一定能恢复两位。因此一定能在$\frac 5 2 n$步内完成。

代码

Java

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

C++

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