前言(吐槽)
其实我是一直知道这玩意,但一直没学过。最近重新在看字符串算法,其中有一节讲到字典树可以处理位异或运算
知道原理但没手写过,结果隔天的练习赛就遇到了一题。。。(该来的还是会来的)
开始吐槽(其实是学习和抄板子)
板子
01-trie 是指字符集为 ${0,1}$ 的 字典树。常用来维护数组的异或极值和异或和。
01-trie 支持修改(删除 + 重新插入),和全局加一(即:让其所维护所有数值递增 1
,本质上是一种特殊的修改操作)。
这里先上个简单的板子
int tol; LL val[32*MAXN]; int ch[32*MAXN][2]; void init(){ tol=1; ch[0][0]=ch[0][1]=0; } void insert(LL x){ int u=0; for(int i=32;i>=0;i--){ int v=(x>>i)&1; if(!ch[u][v]){ ch[tol][0]=ch[tol][1]=0; val[tol]=0; ch[u][v]=tol++; } u=ch[u][v]; } val[u]=x; } LL query(LL x){ int u=0; for(int i=32;i>=0;i--){ int v=(x>>i)&1; if(ch[u][v^1]) u=ch[u][v^1]; else u=ch[u][v]; } return val[u]; }
|
观察建立树的过程,其实就和字典树差不多,上面的板子是在叶子处存值,但实际也会有各种存法(比如每个点都存),例如下面这题
(吐槽:太久没用数组建过树了,忘记怎么建了)
题(暴毙)
2021“MINIEYE杯”中国大学生算法设计超级联赛(1)-6:XOR sum
题意
给一个整数数组,你需要找到最短的区间,其按位异或和不小于. 如果有多个,找出左端点最左的
题解
异或运算里,任意x
的逆元是本身,故对于前缀和pre[i]
和pre[j]
,i
到j
的异或和可以表示为pre[i]^pre[j]
这亚子我们去求一个子串的异或和就简单灰常多啦
我们考虑字典树去维护前缀异或和,由于是要求左右端点,所以我们每往字典树中新增一个值,则查找前面的有没有适合的
那这时我们先考虑一个问题。显然一个前缀异或和可能对应好多个前缀子串,那这棵树该存些什么?
因为是边存边处理,然后要尽可能短的子串,所以在相同前缀异或和的情况下,我们存最右边的那个的下标
好了,那如何保证pre[i]^pre[j]>=k
?
显然当k的某位为1时,树只能往相异的方向走;为0时则要考虑相异方向的值和同向子树的最大。那我们在每个节点都存最右的值,即可在读到0的时候停下读标号即可
代码
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int p[4000010][2]={0},val[4000010]={0},a[100010]={0};
int main(){ int t; scanf("%d", &t); while(t--){ int n,k; scanf("%d %d", &n,&k); for(int i=1;i<=n;i++){ scanf("%d", &a[i]); a[i] ^= a[i-1]; } int l=-1,r=n,num=1; val[1]=-1; p[1][0] = p[1][1] = 0; for(int i=0;i<=n;i++){ int nowl=-1; int x=1; for(int j=29;j>=0;j--){ int abit = (a[i]>>j)&1; if((k>>j)&1) x = p[x][abit^1]; else{ if(p[x][abit^1]) nowl = max(nowl, val[p[x][abit^1]]); x = p[x][abit]; } if(!x)break; } if(x) nowl = max(nowl, val[x]); if(nowl > -1 && i-nowl < r-l) l = nowl, r = i; x=1; for(int j=29;j>=0;j--){ int abit = (a[i]>>j)&1; if(!p[x][abit]){ p[x][abit] = ++num; p[num][0] = p[num][1] = 0; } x = p[x][abit]; val[x] = i; } } if(l>-1)printf("%d %d\n", l+1,r); else printf("-1\n"); } return 0; }
|
杭电多校2的第4题貌似也是字典树,但我还没搞懂怎么弄,先鸽着。。。
2021“MINIEYE杯”中国大学生算法设计超级联赛(2)-4:I love counting