Tag: 线性基

3 篇文章

BZOJ2115 [Wc2011] Xor
题面 样例输入 第一行包含两个整数$N$和 $M$, 表示该无向图中点的数目与边的数目。 接下来$M$ 行描述 $M$ 条边,每行三个整数$S_i$,$T_i$ ,$D_i$,表示 $S_i$ 与$T_i$之间存在 一条权值为 $D_i$的无向边。 图中可能有重边或自环。 样例输出 仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行…
BZOJ4568 [Scoi2016]幸运数字
题面 $A$ 国共有 $n$ 座城市,这些城市由 $n-1$ 条道路相连,使得任意两座城市可以互达,且路径唯一。每座城市都有一个幸运数字,以纪念碑的形式矗立在这座城市的正中心,作为城市的象征。一些旅行者希望游览 $A$ 国。旅行者计划乘飞机降落在 $x$ 号城市,沿着 $x$ 号城市到 $y$ 号城市之间那条唯一的路径游览,最终从$ y$ 城市起飞…
线性基小结
学习线性基 我们在处理异或问题的时候可能会遇到某些恶心的问题,比如: 1.给定一个集合,可以让任意多个数异或,求最大/小异或和 2. 给定一个集合,可以让任意多个数异或,求第k小异或和 3. 给定一个集合,可以让任意多个数异或,求x能否被异或出来 这些问题我们可以使用线性基来解决。 何为线性基 线性基是一个集合,它的大小是log2原集合的值域,它的…