XXI Open Cup named after E.V. Pankratiev. Grand Prix of Belarus
A. Belarusian State University
需要深入理解FWT的本质。
FWT的分治中，是拆开某一位去分治的。
对于每一位的处理，实际上就是相当于处理一种运算关系。
而我们的目标是处理 $2^4=16$ 种二元0/1运算，我们会的只有 $or,and,xor$ 三种。
而我们可以将这个运算转换成取反，固定某个变量的值，以及上面三种常规操作的若干种，从而解决某一位的问题。
分类讨论 $16$ 种情况即可。。
时间复杂度 $O(2^nn)$。
B. Beautiful Sequence Unraveling
C. Brave Seekers of Unicorns
DP，设 $f_i$ 表示序列最后一位为 $i$ 的总方案数。设 $s_i$ 为其前缀和，最终答案为 $s_n$。考虑用所有的方案数减去不合法的，也就是：
$f_i=s_{i-1}-\sum_{k<k\oplus i<i}f_k$。
而对于所有的 $k<k\oplus i<i$，$k$ 的规律是 $k$ 的最高位比 $i$ 小，且该最高位中 $i$ 这一位为 $1$。
然后就是 $O(\log n)$ 个区间和了。
时间复杂度 $O(n\log n)$。
D. Bank Security Unification
设 $f_i$ 表示考虑前 $i$ 个，其中第 $i$ 个必选的最大值，有 $f_i=\max {f_j+a_j& a_i}$。
优化，我们只需要对于每一位考虑前边的出现过这一位为 $1$ 的最大下标即可。
- 证明： 设 $a_i&a_j$ 的最大位为 $k$，对于任一更小的 $j’$，且满足 $a_i& a_{j’}$ 最大位为第 $k$ 位，那么显然有 $a_{j’}& a_{i}<2^{k+1}\le a_{j’}& a_j+a_j& a_i$。说明 $i,j’$ 中间多选一个 $j$ 会比较优。
时间复杂度 $O(n\log C)$。
E. Brief Statements Union
拆位后，变成 $01$ 序列。$and=1$ 的限制相当于表示 $[l_i,r_i]$ 全是 $1$；$and=0$ 的限制表示 $[l_i,r_i]$ 不全为 $1$。
假设 $and=1$ 的都选，差分后，求出有多少个 $and=0$ 的区间全是 $1$。
如果是 $0$ 个，随便删哪个线段均可；
如果是 $1$ 个，可以删掉这个 $and=0$ 的区间；
如果 $>1$ 个，则不能删掉 $and=0$ 的区间；
下面考虑删掉任意一个 $and=1$ 的区间后合法的情况。那么删掉这个区间后合法当且仅当删掉后能满足所有 $and=0$ 的区间的限制。
还是利用每个点被 $and=1$ 的线段覆盖次数的数组，找到所有的只被一条线段覆盖过的点就可以了。
时间复杂度 $O(n\log C)$。
F. Border Similarity Undertaking
分治，然后预处理出左右两边的最远距离，以及能遇到的一些最大值。暴力枚举，时间复杂度 $O(nm\log nm)$。
G. Biological Software Utilities
不妨设有 $2n$ 个点，如何求有完美匹配的树的个数？
首先枚举 $2n$ 个点的不同的匹配情况，答案是 $\prod_{i=1}^n(2i-1)$。
然后对于每种匹配间进行连边，每次连边有 $4$ 种情况，且需要连成一个 $n$ 个点的树，答案是 $4^{n-1}\times n^{n-2}$。
时间复杂度 $O(n)$。
H. Bytelandia States Union
对于一条路径 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$，它的权值总和为 $x_n^2y_n^2-x_1^2y_1^2+\sum_{i=1}^{n-1}(x_i^2+y_i^2)$。
那么，相当于算 $\sum_{i=1}^n(x_i^2+y_i^2)$ 的最小值。
考虑每次移动，$(x^2+y^2)$ 的变化是 $\pm 2x/2y+1$ 的。
先不妨设 $x_1\le x_n$。
如果 $y_1\geq y_n$，那么显然先一直往下走，然后再往右走最优。
如果 $y_1\le y_n$，那么就从 $(x_1,y_1)$ 一直移动 $x$ 或 $y$ 中的较小值，直到他们相等，$(x_n,y_n)$ 也是如此。经过这样的操作以后，就变成从 $(x_1,x_1)$ 移动到 $(x_n,x_n)$ 了，这个很容易算出最小值。
分类讨论，$O(1)$ 计算，时间复杂度 $O(n)$。
I. Binary Supersonic Utahraptors
欺诈题，无论怎么操作，答案不会改变。
J. Burnished Security Updates
判断是否是若干连通二分图。
M. Brilliant Sequence of Umbrellas
我们若构造 $1,1\times 2,2\times 3,3\times 4\cdots$，唯一不满足的是有可能出现隔着两个不互质，比如 $2\times 3,3\times 4$。为了解决这个问题，我们暴力规定隔着两个是互质的。
于是有：$1,2,3,5,7,8,9,11,13,\cdots$，第 $i$ 个数大概是 $\frac{3}{2}i$，这样就可以了。
时间复杂度 $O(n)$。
N. Best Solution Unknown
找到区间的最大值。然后向左右两边递归，记录当前需要到达的最低分即可。
使用单调栈建立笛卡尔树，时间复杂度 $O(n)$。