zcmimi's blog

arrow_back线性基共7篇文章

avatar
zc
2020-06-04 19:43:00
查看原题

点击跳转

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决,遇到环就插入线性基

由于并查集无法删除元素,删边可以用线段树分治处理(转化为每条边在一个时间段存在)

avatar
zc
2020-06-04 12:21:00
查看原题

点击跳转

[WC2011]最大XOR和路径

avatar
zc
2020-06-04 07:29:00
查看原题

点击跳转

做这题之前可以看看[WC201]最大XOR和路径

可以考虑换个思路:

对于每一对点的每一位,有多少种方案能使该位的xor和为1

dfs求出1到各点x的任意一条简单路径xord_x,那么求xy的简单路径长度就是d_x ~ xor ~ d_y

dfs的过程中也可以顺便求出所有环的xor和,这些可以用来增广简单路径,我们将这些环的xor和插入到线性基中

若线性基中有cnt个非零位,则一共会产生2^{cnt}个不同的xor

到了这一步,通过枚举两个点来统计路径的复杂度仍然是O(n^2 \cdot 60)的,我们要采用更高效的方法

直接讨论d_x对答案的贡献

先统计出第k位为0的数的个数,我们将其记为x,再统计出第k位为1的数的个数,记为y,总共有point个点

  1. d_x的第k位为1,线性基中有第k位为1的数: 此时我们有两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总体对于答案的贡献为:2^k\cdot 2^{cnt-1}\cdot (point-1),减1就是为了把自己给去掉。
  2. d_i的第k位为1,线性基中没有第k位为1的数: 这个时候另一个点只能取第k位为0的,, 所以总贡献为: 2^k\cdot 2^{cnt}\cdot x

  3. d_i的第k位为0,线性基中有第k位为1的数: 一样的,, 两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总贡献为: 2^k\cdot2^{cnt-1}\cdot(point-1)
  4. d_i的第k位为0,线性基中没有第k位为1的数: 另一个点只能取第k位为1的,总贡献: 2^k\cdot 2^{cnt}\cdot y

avatar
zc
2020-06-03 13:53:00
查看原题

点击跳转

线性基中每个元素的异或方案唯一,也就是说,线性基中不同的异或组合异或出的数都是不一样的。

那么我们把字符串转成二进制,然后插入线性基

线性基内的元素都是由外界元素异或出来的,那么对于线性基内每个元素,我们都有选/不选两种情况,

假设线性基内有cnt个元素,答案就是2^{cnt}

avatar
zc
2020-06-03 12:34:00
查看原题

点击跳转

线性基搬到了树上

线性基是支持合并的

这题就是倍增暴力合并线性基

虽然O(\log^3_2n)的复杂度已经可以通过了,但是还有更优的方法

在倍增找出询问两点的lca,然后以rmq的方式合并+查询线性基,可以将复杂度降到O(\log^2_2n)

avatar
zc
2020-06-02 13:14:00
查看原题

点击跳转

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后求这条路径长度在线性基上最大能异或成多少即可

假设1到n有一条更好的路径,那么会和刚才钦定的路径形成一个环,相当于异或时已经考虑过了

avatar
zc
2020-06-01 19:50:00
查看原题

点击跳转

先按魔法值排序,然后按顺序插入,如果不能被当前集合异或出来,那么插入并加上其贡献

1/1
Search
search