BZOJ2844 albus 就是要第一个出场

题意

给定 $n(n \le 10000)$个数 $a_1, a_2, \ldots, a_n$ 以及一个数 $Q$。将 $a_1, a_2, \ldots, a_n$ 的所有子集(可以为空)的异或值从小到大排序得到序列 $B$,请问 $Q$ 在 $B$ 中第一次出现的下标是多少?保证 $Q$ 在 $B$ 中出现。

题解

这题也是我学习线性基时在Sengxian的博客上看到的例题。

由于Sengxian讲的已经非常好了,我就将重点部分贴上他的话吧。

这题要求某个数第一次出现的下标,也就相当于求它在线性基$\mathfrak{B}$中可以被张成的所有元素的排名,但是实际上应该求的是它在向量空间$V$中可以被张成的所有元素的排名。
继续阅读

BZOJ2115 最大异或和路径

题面

给定一个 $n(n\le 50000)$ 个点 $m(m\le 10000)$ 条边的无向图,每条边上有一个权值。

请你求一条从 $1$ 到 $n$ 的路径,使得路径上的边的异或和最大。

题解

这题思想还是不错的。

可以将一条路径拆分成一条$1$到$n$的一条路径边权的异或和与一些环的异或和的异或和。

因为如果从$1$开始走到一个环的起点,将其遍历一遍之后再走回$1$就相当于获得了这个环的异或和的值。

于是我们先$dfs$一遍,然后以环的异或和为向量空间,求出线性基$\mathfrak{B}$,然后取初始答案为$dfs$后$1$到$n$的路径异或和,然后在$\mathfrak{B}$上从高位到低位贪心的取,如果当前位置异或上答案能够使答案变大就取,否则不取。
继续阅读