关键词:
先把问题放在后缀数组上考虑
已知两个数组a b,求min(a[i],...,a[j])+(b[i]^b[j])的最大值
套路题
初始每个点都是一个小连通块
把a按从大到小的顺序加入,计算当前加入边作为min的贡献:
每次加入会把两个连通块联通,答案就是两边连通块各出一个数能得到的异或和最大值
我:这不是线性基吗
miaom:mdzz,只能有两个数
我:蛤,好难啊,怎么做啊
miaom:Trie啊
我:哦
没了
1 #include <bits/stdc++.h> 2 #define N 500001 3 #define MAX 18 4 using namespace std; 5 int NODE,n;char ch; 6 int a[N],b[N],c[N*MAX][2],size[N],rt[N],lef[N]; 7 pair<int,int> so[N]; 8 int X[N],Y[N],SA[N],Rk[N],Ht[N],v[N]; 9 void GetSA(int a[],int n,int m=256) 10 { 11 int *x=X,*y=Y,i,p,j; 12 memset(v,0,sizeof v); 13 for(i=1;i<=n;i++)v[x[i]=a[i]]++; 14 for(i=1;i<=m;i++)v[i]+=v[i-1]; 15 for(i=n;i>=1;i--)SA[v[x[i]]--]=i; 16 for(i=1;i<=n;i<<=1,m=p) 17 { 18 p=0; 19 memset(v,0,sizeof v); 20 for(j=n-i+1;j<=n;j++)y[++p]=j; 21 for(j=1;j<=n;j++)if(SA[j]>i)y[++p]=SA[j]-i; 22 for(j=1;j<=n;j++)v[x[y[j]]]++; 23 for(j=1;j<=m;j++)v[j]+=v[j-1]; 24 for(j=n;j>=1;j--)SA[v[x[y[j]]]--]=y[j]; 25 swap(x,y); 26 p=1;x[SA[1]]=1; 27 for(j=2;j<=n;j++) 28 if(y[SA[j-1]]==y[SA[j]]&&y[SA[j-1]+i]==y[SA[j]+i]) x[SA[j]]=p; 29 else x[SA[j]]=++p; 30 if(p>=n)break; 31 } 32 } 33 void GetHt(int a[],int n) 34 { 35 int k=0; 36 for(int i=1;i<=n;i++)Rk[SA[i]]=i; 37 for(int i=1;i<=n;i++) 38 { 39 if(k)k--; 40 int j=SA[Rk[i]-1]; 41 while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++; 42 Ht[Rk[i]]=k; 43 } 44 } 45 int build(int x) 46 { 47 int rt=++NODE,now=rt; 48 for(int i=MAX;i>=0;i--) 49 c[now][(x>>i)&1]=++NODE,now=NODE; 50 return rt; 51 } 52 int que(int x,int y,int z=0) 53 { 54 int best=z; 55 if(c[x][0]) 56 if(c[y][1]) best=que(c[x][0],c[y][1],z*2+1); 57 else best=que(c[x][0],c[y][0],z*2); 58 if(c[x][1]) 59 if(c[y][0]) best=max(best,que(c[x][1],c[y][0],z*2+1)); 60 else best=max(best,que(c[x][1],c[y][1],z*2)); 61 return best; 62 } 63 void merge(int x,int y) 64 { 65 if(c[x][0]) 66 if(c[y][0]) merge(c[x][0],c[y][0]); 67 else c[y][0]=c[x][0]; 68 if(c[x][1]) 69 if(c[y][1]) merge(c[x][1],c[y][1]); 70 else c[y][1]=c[x][1]; 71 } 72 int getfa(int x) 73 { 74 if(lef[x]==x) return x; 75 else return lef[x]=getfa(lef[x]); 76 } 77 int main() 78 { 79 scanf("%d",&n); 80 for(ch=getchar();!isalpha(ch);ch=getchar()); 81 for(int i=1;i<=n;i++,ch=getchar()) 82 a[i]=ch; 83 for(int i=1;i<=n;i++) 84 scanf("%d",&b[i]); 85 GetSA(a,n); 86 GetHt(a,n); 87 for(int i=1;i<=n;i++) 88 size[i]=1,lef[i]=i,rt[i]=build(b[SA[i]]); 89 for(int i=2;i<=n;i++) 90 so[i-1]=make_pair(n-Ht[i],i); 91 sort(so+1,so+n); 92 int ret=0; 93 for(int i=1;i<n;i++) 94 { 95 int x=so[i].second,y=x-1,z=n-so[i].first; 96 x=getfa(x);y=getfa(y); 97 if(size[x]<size[y]) swap(x,y); 98 int bes=que(rt[y],rt[x])+z; 99 if(bes>ret) 100 ret=bes; 101 merge(rt[y],rt[x]); 102 size[x]+=size[y]; 103 lef[y]=x; 104 } 105 printf("%d ",ret); 106 return 0; 107 }
bzoj4199:[noi2015]品酒大会(并查集&&后缀数组)
据说用后缀自动机+dp也能做然而并不会后缀数组的做法呢就是先建个后缀数组,求出height值,此时如果直接找,复杂度是n^2的,肯定会超时。但是height大的值是不会对小的产生影响的,所以可以按height大小,从大到小合并两个区... 查看详情
loj#109.并查集
内存限制:256MiB时间限制:2000ms标准输入输出题目类型:传统评测方式:文本比较上传者:匿名提交提交记录统计讨论1测试数据 题目描述这是一道模板题。维护一个 nnn 点的无向图,支持:加入一条连接 uuu ... 查看详情
bzoj4199[noi2015]品酒大会:后缀数组+并查集
... 对于每个整数r∈[0,n-1]: (1)问你有多少对后缀(suffix(i),suffix(j)),满足LCP(suffix(i),suffix(j))>=r (2)输出mul[r]=max(v 查看详情
bzoj4199[noi2015]品酒大会后缀数组+并查集
【BZOJ4199】[Noi2015]品酒大会题面:http://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=2144题解:听说能用SAM?SA默默水过~本题的实现还是非常简单的,先求出height数组,然后两杯酒‘r‘相似就等价于二者中间的height都>=r,于是我们将height... 查看详情
poj2513并查集,trie(字典树),欧拉路径
-ColoredSticks POJ-2513 Youaregivenabunchofwoodensticks.Eachendpointofeachstickiscoloredwithsomecolor.Isitpossibletoalignthesticksinastraightlinesuchthatthecolorsoftheendpointsthattouchareof 查看详情
poj2513欧拉回路+并查集推断是否联通+trie树
...符串相应的int值。当然这个int值也能够用于建立并查集2、接上。通过并查集推 查看详情
4199.[noi2015]品酒大会后缀数组+并查集
DescriptionSandy和Sue的热衷于收集干脆面中的卡片。然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型... 查看详情
acm算法目录
...维线段树 ?树状数组 一维树状数组 N维树状数组 ?字典树 ?后缀数组,后缀树 ?块状链表 ?哈夫曼树 ?桶,跳跃表 ?Trie树(静态建树、动态建树) ?AC自动机 ?LCA和RMQ问题 查看详情
bzoj4199:[noi2015]品酒大会后缀数组+单调栈+并查集(代码片段)
用SA求出height数组,然后发现每个height值都有一个贡献区间(因为点对之间要依次取min)用单调栈处理出区间,第一问就做完了然后用并查集维护每个点的贡献(?),从大到小枚举height,因为这样区间是不断增大的所以并查集... 查看详情
算法分类合集
...树二维线段树树状数组一维树状数组N维树状数组字典树后缀数组,后缀树块状链表哈夫曼树桶,跳跃表Trie树(静态建树、动态建树)AC自动机LCA和RMQ问题KMP算法图论基本图算法图广度优先遍历深度优先遍历拓扑排序割边割点强连通... 查看详情
hdu4641k-string,后缀自动机,并查集
http://acm.hdu.edu.cn/showproblem.php?pid=4641http://blog.csdn.net/asdfgh0308/article/details/40969047再写自动机我人就废了,码个代码爬墙。。。(明明是看代码长不想写) 查看详情
算法分类合集(转)
...树二维线段树树状数组一维树状数组N维树状数组字典树后缀数组,后缀树块状链表哈夫曼树桶,跳跃表Trie树(静态建树、动态建树)AC自动机LCA和RMQ问题KMP算法图论基本图算法图广度优先遍历深度优先遍历拓扑排序割边割点强连通... 查看详情
算法分类合集(转)
...树二维线段树树状数组一维树状数组N维树状数组字典树后缀数组,后缀树块状链表哈夫曼树桶,跳跃表Trie树(静态建树、动态建树)AC自动机LCA和RMQ问题KMP算法图论基本图算法图广度优先遍历深度优先遍历拓扑排序割边割点强连通... 查看详情
谢特——后缀数组+tire树(代码片段)
题目【题目描述】由于你成功地在$ ext1s$内算出了上一题的答案,英雄们很高兴并邀请你加入了他们的游戏。然而进入游戏之后你才发现,英雄们打的游戏和你想象的并不一样……英雄们打的游戏是这样的:首先系统会产... 查看详情
[bzoj3673][可持久化并查集byzky](rope(可持久化数组)+并查集=可持久化并查集)
...mpleInput561123122031221312SampleOutput101Solution用rope实现可持久化数组,用rope的历史记录功能实现可持久化并查集 查看详情
并查集——新手学习记录(代码片段)
...有点飘。或者这样理解:——并查集通过一个一维数组来实现,其本质是维护一个森林。(好吧,我也不是很理解),我的理解就是通过一维数组来实现,子节点与父节点之间联系,然 查看详情
并查集
并查集--basicpublicclassUnionFind1{privateint[]parent;//数组,表示并查集所有元素的集合号privateintsize;//表示并查集元素个数publicUnionFind1(intsize){//并查集初始化this.size=size;parent=newint[size];for(inti=0;i<size;i++){parent[i]= 查看详情
codeforces292dconnectedcomponents(并查集)
...求出一个前缀Li表示加入前i条边时图的连通状况以及一个后缀Ri表示加入后i条边时图的连通状况对于每个询问删除s--t条边只要将Ls-1和Rt+1合并一下就行了合并其实就是讲s-1和t+1对应的f[i]Union一下就行了为什么这就相当于把前缀i... 查看详情