menu zcmimi's blog
nya~
zcmimi
oier & archlinuxer

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

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

加边删边可以用按秩合并的并查集解决

zc
2020-06-04 19:43

[WC2011]最大XOR和路径 ```cpp

include<bits/stdc++.h>

int rd(

zc
2020-06-04 12:21

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

可以考虑换个思路:

对于每一对点的每一位,有多少种方案

zc
2020-06-04 07:29

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

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

线性基内的元素都是由外界元素异或出来的,那么对于线性基内每个元

zc
2020-06-03 13:53

线性基搬到了树上

线性基是支持合并的

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

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

在倍增找出询问两点的lca,然后以rmq的方式合并

zc
2020-06-03 12:34

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

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

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

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

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

直接随意找一条1到n的路径,然后

zc
2020-06-02 13:14

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

include<bits/stdc++.h>

typedef long long ll; const

zc
2020-06-01 19:50
zcmimi
2020-06-01 13:28

可以考虑把字符串倒序

这样添加一个字母相当于增加了一个后缀,相对原来更好处理

可以发现在插入新的字符串时,height改变的只有`height[pre],height[p],height[nxt]

zc
2020-05-29 17:09

40%的log n做法挺容易的,就是一直往右儿子走,走到叶子就往左走,一直重复即可

100%的做法:

首先可以把f(l)\bigoplus\dots\bigoplus f(r)变成

$[

zc
2020-05-29 17:09
1 / 63
Search
search