Codeforces Round #633 (Div. 2)

比赛ABC，赛后DE。排名4025。

我是傻逼。

A - Filling Diamonds

Code

题意：

给定一个钻石状图形，让你用小四边形（n=1）进行填充。问有多少种不重复的填充方案。

解法：

根据思考可得，只要确定了直立小四边形的位置，其它小四边形的位置就已经确定了。所以对于任意图形，有且仅有n个直立小四边形的位置。

B - Sorted Adjacent Differences

Code

题意：

给定一个整数数组a[n]，数组中的数可能有重复。让你对这个数组进行排序，使得：|a1−a2|≤|a2−a3|≤…≤|a_n−1−a_n|。保证一定有解。

解法：

易知数组里面最多有一组重复的数。否则不能保证一定有解。

如果数组里面有重复的数（记为v），且重复k次。那么a[1..k] = v。然后我们在a[1..k]的左边找到一个数a[k+1]，然后在a[1..k+1]的右边找到a[k + 2]。此时一定有| a[k+1] - a[k] | <= | a[k + 2] - a[k + 1] |。之后依次向两边扩展。

对于没有重复的数的数组，我们可以找到它的中位数，然后依次向两边扩展。

C - Powered Addition

Code

我真的是傻逼

题意：

有一个整数数组a[n]，每一秒可以执行一次如下操作：选择任意个（或0个）元素，a[i] += 2^(x - 1)。x为当前时间（秒），从1开始。

问最少多少秒之后，可以让数组a[n]变为不递减（nondecreasing）的。

解法：

如果我们在每一秒都向数组的最后一个数a[n]进行修改，也不会破坏“不递减”的性质。之后再向前一个数a[n-1]加尽可能大的数以维持性质。

所以我们用二分法，假设所需要的时间为T。然后更新数组，看是否能满足不递减的性质。

注意最大的加数为(1 << T) - 1。

D - Edge Weight Assignment

Code

题意：

给定一棵有n个节点的树。现在让你给这棵树的每一条边赋值x（x > 1)，使得任意两个叶子节点之间的简单路径的xor和为0。

求最少/最多使用多少个数可以满足以上条件。

解法：

[官方解法]

先考虑最小值。我们从最简单的n=3的情况开始。对于n=3，一定是以下的情况。

此时树上叶子节点的路径只有一条，并且xor值为0。

如果我们要把两个n=3的树合在一起，会有如下两种情况。

左边的子树从叶子到根的路径xor为1，右边的根到叶子的路径xor为0。因为边的权值不能为0。所以我们只能填入2和3。
左边和右边完全对称，填入1即可。

我们继续推导，可以（猜测）得出一般情况下，所需要权值种类最小值为3。而在所有叶子节点的深度相同的（特殊）情况下，最小值为1。

再考虑最大值。

在这种情况下，每个不同子树从根到叶子的路径xor值都不相同。

所以只需要保证当前子树根节点直接连接的叶子节点权值保持一致即可。

思路扩展：可以将本题转化为，所有节点有一个权值，并且邻居节点之间的值一定不同。

E - Perfect Triples

Code

题意：

有一个无限长的序列s。其构建规则如下：

找到3个正整数a, b, c。使得a ^ b ^ c == 0，且a, b, c当前都不在s当中。
如果有多组情况，选择字典序最小的(a, b, c)
s += [a, b, c]。并重复以下操作

问序列第n个值是多少。

解法：

OEIS大法失效，直接打表看结果。其特性如下：

每4^k个三元组为一大组，每组的第一个数字为4^k...(4^k) * 2 - 1
因为要保证字典序最小。每个三元组的最高位排列都是(01, 10, 11)。
后面的比特位都是('00', '00', '00'), ('01', '10', '11'), ('10', '11', '01'), ('11', '01', '10')这样的排列。每4次为一个循环。

找到规律直接搞就行了。

官方题解给了数学归纳法的证明。并且说OEIS是可行的（？）。

Wizmann / ACM-ICPC