Codeforces Round #735 ABCD 题解 (Java/C++)

A. Cherry

题解

显然，我们希望区间内的最大值和最小值都尽可能大，这样乘积才能尽可能大。
显然$$max(a_{l},a_{l+1})\cdot min(a_{l},a_{l+1}) \geq max(a_{l},a_{l+1},a_{l+2})\cdot min(a_{l},a_{l+1},a_{l+2})$$和$$max(a_{l+1},a_{l+2})\cdot min(a_{l+1},a_{l+2}) \geq max(a_{l},a_{l+1},a_{l+2})\cdot min(a_{l},a_{l+1},a_{l+2})$$中至少有一个成立。

因为$max(a_{l},a_{l+1})=max(a_{l},a_{l+1},a_{l+2})$和$max(a_{l+1},a_{l+2})=max(a_{l},a_{l+1},a_{l+2})$中至少有一个成立。
而$min(a_{l},a_{l+1}) \geq min(a_{l},a_{l+1},a_{l+2})$和$min(a_{l+1},a_{l+}) \geq min(a_{l},a_{l+1},a_{l+2})$始终成立。

所以，只需要枚举所有长度为2的区间即可。

代码

Java

C++

B. Cobb

题解

只需枚举最后200位的任意组合即可。

考虑最后两位的组合，其结果为：$n\cdot (n-1)-k\cdot (a_n|a_{n-1})$。易得$a_n|a_{n-1}<n$。因此最后两位的组合的结果的最小值为：$n\cdot (n-1)-100n=n^2-101n$。（$a_n|a_{n-1}<n$并不严谨）

考虑最后一位和第n-100位组合，其结果为：$n\cdot (n-100)-k\cdot (a_n|a_{n-100})$。不考虑$a_n$的值，$a_n|a_{n-100}$可能的最小值为0。因此，这种组合的最大值为：$n\cdot (n-100)=n^2-100n$。

我们发现，$[n,n-1]$的最小值已经差不多大于$[n,n-100]$的最大值了。因此枚举最后200位就非常可靠了。

代码

Java

C++

C. Mikasa

题解

首先，如果一个数没有出现（假设这个数是x），一定有$x\oplus n > m$。而我们的任务就是求出这个最小的x。

令$x\oplus n = y$，我们只需要按位枚举第一个大于m的二进制位即可。

以n=69，m=696为例。

我们枚举第一个使Y大于696的位置（红色部分）。在这个位置后面的值可以随意（？部分），只要保证x在这一位是0即可（绿色部分）。于是我们可以找出结果是640。

唯一一个可能的例外是$m=(111...11)_2$。我们只需要最后再考虑$x=m\oplus (m+1)$的情况即可。

代码

Java

C++

D. Diane

题解

考虑字符串"aaaaa"，考量所有子串，a出现了5次，aa出现了4次，aaa出现了3次，aaaa出现了2次，aaaaa出现了1次。因此不满足条件的只有aa和aaaa。
再考虑字符串"aaaa"，a出现了4次，aa出现了3次，aaa出现了2次，aaaa出现了1次。
于是我们可以想到，把这两个加起来的话，a就出现了9次，aa出现了7次，aaa出现了5次，aaaa出现了3次，aaaaa出现了1次。

因此我们的想法是，把x个a和x+1个a都加进最终的字符串里。因此我们构造形如aaabaaaa的字符串。如果n是奇数，则构造形如aaabcaaaa的字符串。

代码

Java

C++