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

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

C++

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

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

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

C++

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

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

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

C++

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

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

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

C++

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