Codeforces Round #743(Div. 2) ABCD 题解 (Java/C++)

A. Countdown

题解

显然,我们会把每一个非零的数置换到个位然后减掉。因此除了个位本身,其他位只要不是0,那么就除了这个数被减掉所需的操作之外,外加一个置换操作即可。

代码

Java

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

C++

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

B. Swaps

题解

显然,我们只需要关注第一位即可。于是我们根据数组b从小到大依次尝试,每次尝试选择代价最小的a使得a<b。

同时,我们注意到,随着b的每次增长,a其实可以选择的数也只会多一个。于是我们只需维护一个所有a的最小开销,当有个新的a时,更新最小开销即可。

代码

Java

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

C++

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

C. Book

题解

显然,这是一个经典的拓扑排序问题,但是有一点点变化。算是经典应用。

因为读书是顺序读,不能倒回去。因此当我们发现某一章(记为x)的入度为0,进而根据其出边去更新其他章节(记为y)的入度时,如果发现这一章(y)在当前章(x)前面,那么这一章无论如何一定需要再读一次。
于是我们将队列分成两个:
一个是只存储可以在这次阅读中理解的章节;
一个存储虽然入度为0,但是由于上面的情景,不能在当前阅读中理解的章节。

很自然的,第一个队列都处理完后,我们再处理第二个队列即可,此时第二种队列的就变成了第一种队列。

代码

Java

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

C++

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

D. Xor of 3

题解

首先我们考虑什么时候1会变成0,不难发现只有在三个数中有2个1时,这两个1会变成0。于是不难发现如果一开始有奇数个1,那么一定无解。

接着考虑到题目要求最多n次操作,因此不难猜测到最终的解法很可能是从左至右依次构建。(从右往左构建完全同理)

我们首先考虑最左侧是0的情况。比如010xxxx。对于010xxxx,我们可以分成两种情况:
一种是0101xxx,对于这种情况,直接变成0000xxx即可。
另一种是0100xxx,我们可以先把他变成0111xxx,接着再变成0001xxx。于是我们就通过两步操作将1往右推了2格。

显然对于011xxxx,我们可以直接依次操作将其变为000xxxx。因此对于001xxxx,我们可以将其转化为010xxxx或者011xxxx中的一种。

于是到此我们已经能够将任意的0xxxxxx通过至多两次操作转化为000xxxx。(因为我们已经讨论了001xxxx,010xxxx,011xxxx。)于是就能进一步将其转化为00000xx。
同时显然的,如果最左侧是1,而最右侧是是0的话,我们只需要倒过来操作即可。

现在,剩下的场景就是最左侧和最右侧都1的情况。

立刻可以想到,101xxxx和110xxxx可以直接变成000xxxx。于是我们只剩下100xxxx和111xxxx。而100xxxx可以直接转化为111xxxx,因此我们只需要考虑111xxxx这种情况。
结合0xxxx的情况,我们不难发现,在把最左侧的1变成0的前一个状态一定是110xxxx而不可能是101xxxx。于是为了产生110xxxx,其前一个状态必然是11101xx或者11110xx。
同理11101xx中的101是无法构造出来的,因此除非原数组恰好如此,否则我们只需要考虑11110xx。而要获得11110xx和要获得110xxxx是一样的。
于是对于111xxxx除了不断向右扩展,直到遇到一个101或者110为止。如果遇到了,考虑到奇偶性,可以以此为出发点,向左向右分别按照0xxxx处理即可。

代码

Java

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

C++

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