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

A. Plus One on the Subset

题解

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

代码

Java

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

C++

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

B. Make AP

题解

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

代码

Java

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

C++

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

C. Division by Two and Permutation

题解

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

代码

Java

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

C++

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

D. Palindromes Coloring

题解

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

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

代码

Java

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

C++

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

E. Masha-forgetful

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

Codeforces Round #764 Masha-forgetful 题解 (Java/C++)
题解字典树+DP。首先,任何大于3的数都能表示为若干个2和若干个3的和。因此我们我们每一个区间的长度要么是2要么是3。
点击上面链接查看详细题解

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

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

C++

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

G. MinOr Tree

题解

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

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

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

代码

Java

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

C++

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