nfls 训练赛#5

赛时过了 $3$​ 题，D 有点太史了。

A

给定一个序列 $a_i$ 和一个整数 $X$，要求构造一个长度与原序列相同的序列，对于每个位置要求 $0\le a_i\le b_i$，且序列的异或和为 $X$。求方案数。

$X\le 10^9,n\le 50$

不是很难的题，注意到如果一个可填的数为 $[0,2^k-1]$，并且 $X<2^k$，那么其他乱选之后我这个都可以调成合法。

考虑数位 dp 一位一位确定的过程，相当于是在一个 $1$ 的地方写 $0$，那么后面的位置就变成了上面的情况。

因此枚举最大的一个把 $1$ 写 $0$ 的位置即可。

复杂度 $O(n\log V)$。

B

一个 $n\times m$ 的矩形棋盘，有一些格子被 ban 掉了，其余的每个格子你可以指定放或不放硬币。

放完硬币后你可以做若干次操作，每次操作你可以指定一个方向（上下左右），使所有的硬币尝试向那个方向移动一格。如果一个硬币的目标格子被ban那么它不会移动。硬币可以被移出棋盘（然后就掉在外面回不来了）。一个格子上可以有多枚硬币。

求有多少种放硬币的方案，满足存在一种操作序列使至少有一枚硬币被移出棋盘、同时至少有一枚硬币留在棋盘上。

$n,m\le 40$

挺好的题。

注意到条件可以转化为两两之间的关系，即两个硬币是否合法。

不合法关系构成等价类，因此只需要跑出两两之间是否合法即可。

这个 check 很困难，考虑倒推，最终合法的情况一定是一个掉下去了，一个没有掉下去，枚举所有这样的情况（就是一个在边上要掉下去，另一个掉不下去），然后逆着推出所有可能的开始合法情况即可。

复杂度 $O(n^2m^2)$ 。

E

给一棵 $n$ 个结点的树，定义一个结点集合是连通的表示这棵树以这个集合为点集的导出子图是连通图。再给一个整数 $k$，将树上的结点重新编号，使得对于任意一个满足 $1\le i\le n-k+1$ 的 $i$，都满足由所有编号在 $[i,i+k-1]$ 内的结点组成的结点集合是连通的。问这样的编号方式有多少种。

$n,k\le 40$

这个 $40$ 又是误导复杂度的。

正解是分情况讨论，第一种情况是 $2k\le n$，此时开始一定是一棵子树，然后每次删一个点加一个点，最后一定也是一个子树，中间部分容易证明是一条链。

两颗子树的选法是唯一的，因此拓扑序数一下即可。

另一种情况，$2k>n$​，那么此时会有一些不动点，不动点一定是一个联通块，把树分成若干部分。

分析一下，发现每个部分全部都要放在顺序的左边或者右边，因此重心必须选。

选了重心之后就是简单 dp 了，考虑要么放中间联通块，要么子树放左边或者右边，还是一个拓扑序计数。

复杂度 $O(n^4)$，可以插值优化为 $O(n^3)$ 。