CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== C =====

我的做法：

显然这个题满足二分的性质，我们对它进行二分，

二分到一个x的时候，b[i]表示能构造的大于等于a[i]且大于等于b[i-1]的最小值，如果构造不出来即为False。

复杂度$n\log n \log n$二分乘位运算的复杂度

正解：

答案为每一个数-它后面的最小的数的位数

正确性显然

实现方法也很巧妙

一个变量记录当前最大值，一个变量记录差的最大值

每次用当前最大值减$a[i]$更新差的最大值即可。

===== D =====

如果只关注叶子的话，我们可以直接把叶子与他们LCA之间的边压缩到一块

对于这个题我们可以先选择一条以某一个叶子为根的主链,显然对于主链外，与主链上的点P，相连的点的子树，他们其中的任意叶子到P的异或值均相同。

题解中构造了如下的结构

Nonleaf 左儿子为Nonleaf 右儿子为leaf的结构 (最顶端的Nonleaf的右儿子为根)

接下来我们讨论最小值。

如果任意两个点之间的边数都是偶数的话，最小值显然为1.

如果存在两个点之间的边数为奇数，那么填一个数就不行了，这时显然填两个数也不行，但是填三个数一定可以，即沿着主链按图上的填法填即可，且1，2，3这三个数的任意一个数，都可以被任意长度的1，2，3构成。

接下来讨论最大值。

以下为正解

答案为边数-叶子数+有与叶子直连的点的个数

大概意思是同一个节点连的叶子之间的边权值肯定得相等，其他都随便填肯定能找到构造方法，似乎没有问题。

===== E =====

打表题， 甚至正解都是打表。

先打A，发现A每次是以$4^i$开头，连续4^i$个数字。

B似乎看不出什么规律，但是亦或的话是二进制，就拿二进制看看。

就发现了B与A两位两位之间的关系，如A相邻两位为00，B就为01之类的关系。

然后就能算出C了。

迷惑？？？
CVBB ACM Team

用户工具

站点工具

页面工具
