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

A. Consecutive Sum Riddle

题解

显然$\frac {(l+r)\cdot (r-l+1)} 2 = n$,于是有$(l+r)\cdot (r-l+1) = 2\cdot n$。

我们尝试假设r-l+1=2,于是我们发现上面的等式可以化简为$(l + l + 1) \cdot 2 = 2 \cdot n$,也就是$2\cdot l+1=n$。
此时只要n是一个奇数时,l有解。

于是现在只剩下n是一个偶数的情况。此时,我们尝试假设r-l+1=4。于是可以将原等式化简为:$(2\cdot l + 3) \cdot 4 = 2 \cdot n$。于是$(2\cdot l + 3) = \frac n 2$。
此时只要$\frac n 2$是一个奇数时,l有解。

于是我们就只剩下n能被4整除的情况。同理,我们再让r-l+1翻倍。如此往复,直到$2l+?$等于一个奇数。

代码

Java

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

C++

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

B. Special Numbers

题解

显然,考虑最后的数的n进制形式,这个n进制数必然只包含0或者1。既然是0或者1,那么自然的,第k大的数就是k的二进制形式。

比如k=4,k的二进制形式为$(100)_2$。那么这个n进制数为$(100)_n$。

代码

Java

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

C++

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

C. Make Them Equal

题解

首先可以立刻想到操作次数一定不会超过2。因为n和n-1一定能够把所有字符换成c。

接着我们从后往前找,找到最右边的i使得s[i]=c。如果$i*2-1\geq n$,那么通过这个i,能够把除了s[i]以外的所有字符换成c,而恰好s[i]=c,所以只需要一次操作。
而如果如果$i*2-1< n$,如果我们对i做一次操作,那么s[2i]一定不等于c(否则根据i的定义,i其实应该是2i)。因此一定需要第二次操作。那不如直接用n和n-1,这样更简单一些。

代码

Java

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

C++

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

D. The Number of Imposters

题解

我们假设其中一个人的角色,然后根据与他有关的comments用dfs推导其他人的角色即可。

需要注意的是,当我们改变对一个人的角色的假设时,相应的其他所有人的角色会直接和之前的推导结论恰好相反。因此,我们只需要dfs一次就足够了。

代码

Java

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

C++

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

E. Rubik's Cube Coloring (easy/hard version)

题解

我们将颜色分为3类,白色黄色为第0类,绿色和蓝色为第1类,红色和橙色为第2类。

我们首先考虑easy version。我们自下而上的考虑当前节点涂某类颜色有多少可能,如下图所示:

首先我们考虑最下层的节点,显然每一类其实都有2种选择。
接着我们考虑第二层,以第0类为例,显然如果第二层的某个节点要选择0类的颜色,那么这个节点的左右儿子都不能是第0类的颜色;同时注意到第0类颜色有两种涂法。于是就有(left[1]+left[2])*(right[1]+right[2])*2=(2+2)*(2+2)*2=32种涂法。
类似的,我们就可以自下而上的构建到树根处。

而注意到,如果没有预涂,我们发现每一层的各个节点之间是完全一样的。同时节点内,每种类型也是一样的。于是我们可以直接用一个一维数组就能计算出来。

对于hard version,由于最多有2000个节点有预涂上颜色。我们把这些节点以及其所有父节点都单独构建出来。因为深度最多是60,所以最多有2000*60=120000个节点被单独构建。
同样的,我们可以自下而上的构建。和easy version的区别是,hard version中我们需要基于easy version的结果,再次对单独构建的节点自下而上构建一次即可。

代码

Java

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

C++

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

F. Ideal Farm

题解

首先,如果k大于s,那么一定是no。因为无论如何,都不会存在lucky的情况。接着如果k等于s,那么一定是yes。因为无论如何,都可以选择所有围栏来实现lucky。

因此我们只需要考虑s大于k的情况。显然,我们只需要找出什么情况下可以构造出不lucky的分配方式就可以了。

不难想到这种构造$$\underbrace{1, 1, 1, \dots}_{k-1},\ k+1,\ \underbrace{1,1,1,\dots}_{k-1},\ k+1,\ \dots$$也就是首先每个栅栏都分配1个动物,然后每隔k-1个栅栏多分配k个。

如果s不足以支撑上面这种构造,那么就需要从上面的某个k+1减少值。(因为栅栏不能为空,所以不能从1上减。)
因此我们只需要考虑这种构造需要多少动物即可,所以$s-n<\lfloor \frac{n}{k}\rfloor k$时,无法构造出unlukcy,输出Yes。

代码

Java

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

C++

Submission #131390410 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论