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
C++
B. Special Numbers
题解
显然，考虑最后的数的n进制形式，这个n进制数必然只包含0或者1。既然是0或者1，那么自然的，第k大的数就是k的二进制形式。
比如k=4，k的二进制形式为$(100)_2$。那么这个n进制数为$(100)_n$。
代码
Java
C++
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
C++
D. The Number of Imposters
题解
我们假设其中一个人的角色，然后根据与他有关的comments用dfs推导其他人的角色即可。
需要注意的是，当我们改变对一个人的角色的假设时，相应的其他所有人的角色会直接和之前的推导结论恰好相反。因此，我们只需要dfs一次就足够了。
代码
Java
C++
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
C++
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
C++