Codeforces Round #739 ABCDEF 题解 (Java/C++)

A. Dislike of Threes

题解

从1开始依次检查每个数即可。

代码

Java

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

C++

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

B. Who's Opposite?

题解

总人数等于$2\cdot |a-b|$,也就是ab之差就是一半的人数。如果abc中任意一个数大于总人数,则输出-1。否则,根据c的情况,加减$|a-b|$即可。

代码

Java

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

C++

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

C. Infinity Table

题解

我们按下图方式分段。不难发现,每一段的起始值只差每次都增加2。

2-1=1, 5-2=3, 10-5=5

代码

Java

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

C++

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

D. Make a Power of Two

题解

枚举$2^0$到$2^63$即可。对于每个$2^k$,我们从高位往低位依次匹配,计算出所需要的操作次数即可。最后我们就从64个答案中选一个最小的。

代码

Java

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

C++

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

E. Polycarp and String Transformation

题解

因为每次我们都会从s中删除一个字母。因此我们从后往前遍历t,按照字母首次出现的先后顺序,就可以得到删除字母的顺序。
我们得到了删除的顺序之后,我们就能通过每个字母出现的总数,构建出s。
最后根据我们构建的s,验证一次即可。

我们以样例为例:
如下图所示,我们从右往左检查每个字母首次出现顺序,于是我们得到了删除顺序:lcoayrp。

接着我们尝试构建s。显然,因为l是第一个被删掉的,所以所有的l都应该在s中。接着对于字母c,因为是第二个被删掉的,所以s中的c在t中会出现两次。而对于字母p,s中p的个数为t中p的个数除以7。于是我们就能得到s中每个字母出现的次数。
最后,我们根据s中每个字母的出现次数,再结合t,我们就能得出s。再验证一次即可。

代码

Java

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

C++

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

F. Nearest Beautiful Number (Easy/Hard)

题解

首先,$C_{10}^5=252$。因此我们选择直接暴力枚举这k个数字。然后根据选择好的数字来构造尽可能小,且大于n的数字。

至于构造过程,我们需要注意以下几点。
1. 如果之前某一位已经大于原数字,那么后面的所有数字都是选尽可能小的。
2. 如果原数字比这k个数字都大,那么就往前找最近的一位,并把这一位的数字变大。
3. 如果不存在第2点的这一位,那么说明这个排列不成立。

代码

Java

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

C++

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