Codeforces Round #764 ABCDEFG 题解 (Java/C++)

A. Plus One on the Subset

题解

显然，输出最大值减去最小值即可。

代码

Java

C++

B. Make AP

题解

依次尝试对每个数做操作即可。只要找到一种可行的方案，那么输出YES。

代码

Java

C++

C. Division by Two and Permutation

题解

我们统计0到n中的任意一个x能由哪些a[i]生成。
于是我们每次都找出0到n中可选择的i最少的x，并随便找其中的一个i将其做若干次操作得到x。
如果过程中发现某个x没有可选的i了，则输出No。

代码

Java

C++

D. Palindromes Coloring

题解

显然只要某一个字符串中有且只有一个字母出现奇数次，其他字母都是出现偶数次，那么这个字符串一定可以通过调整顺序得到一个回文串。

那么我们只需要统计出有多少对字母，比如aa，bb，cc。并将这些字母对均匀的分配给k个字符串即可。
最后剩下的，字母中最多找出k个，作为唯一的奇数个的字母加到k个字符串中即可。

代码

Java

C++

E. Masha-forgetful

一道不错的字典树和DP的题目。

F. Interacdive Problem

题解

我们二分初始的x的值。我们可以发现，对于x所有可能值得中值mid，我们给出c使得，mid+c恰好能被n整除。如果x在mid的左侧，则$\lfloor\frac{x+c}{n}\rfloor<\lfloor\frac{mid+c}{n}\rfloor$。否则$\lfloor\frac{x+c}{n}\rfloor=\lfloor\frac{mid+c}{n}\rfloor$。

唯一麻烦的地方在于，要记录下每次的c，以及计算针对当前mid的c。

代码

Java

C++

G. MinOr Tree

题解

首先，我们先找出最终结果的最高位的1。因此按二进制位数添加边，直到所有的点都在被连到一起为止。

此时我们假设的答案是一个全是1的二进制数，形如111111。（也许小于6位的所有边的OR并不是111111，但根据后面的做法，我们可以忽略这一点。）
此时最高位的1是不能变成0的，因为如果这位可以为0，意味着5位就足够了。如果我们一定要把最高位换成0，那么就需要更高位的边来补充，这样的OR的值更大。
于是我们从第二高位开始，依次尝试把每一位改成0后，是否依然能构成一棵树。也就是说，我们首先尝试101111，接着尝试1?0111，其中?要根据第一次尝试的结果来定。

这样做是因为，显然我们是希望尽可能高位为0的。因此，在讨论某一位能不能是0时，对于更低的位，一定全是1，以使得尽可能构成一棵树。

代码

Java

C++