Lvat_s Blog

5
10
2016

后缀数组练习

CTSC&APIO感觉自己水平太低，完全没法做……

所以打算利用在北京的这段时间提高一下自己的OI水平

后缀数组虽然会写，但是仅限于会敲模版。。

所以我打算把罗穗骞论文里面的所有题写一遍

----------------------------------------

POJ 2774

两个串连一起搞完后缀数组然后求height最大值判断一下前后是否分别属于两个不同的串就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int n1,n2,n,rank[N],sa[N],rank2[N],wa[N],ws[N],height[N];
char s1[N],s2[N],s[2*N];

int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
    for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

bool Diff(int x){return (sa[x]<n1 && sa[x-1]>=n1)||(sa[x]>=n1 && sa[x-1]<n1);}

int Solve(){
int MxHeight=0;
for(int i=2;i<=n;i++){
	if(height[i]>MxHeight && Diff(i))MxHeight=height[i];
}
return MxHeight;
}

int main(){
freopen("2774.in","r",stdin);
freopen("2774.out","w",stdout);
scanf("%s %s",s1,s2);
n1=strlen(s1);
n2=strlen(s2);
n=n1+n2;
for(int i=0;i<n1;i++)s[i]=s1[i];
for(int i=n1;i<n;i++)s[i]=s2[i-n1];
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
printf("%d\n",Solve());
return 0;
}

----------------------------------------

POJ 1743

先差分，然后二分答案k,然后对于height分组(height[i]记录的是sa[i]和sa[i-1]的LCP)，那么因为字典序相邻的后缀在sa里的顺序是连续的，那么我们对于判定答案k是否合法的方法就是找到连续的height，它们的值都不小于k(保证重复的串长大于等于k),然后如果组内最靠前和最靠后的位置差也大于等于k，那么这个方案就是合法的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=200005,INF=2100000000;

int sa[N],rank[N],rank2[N],ws[N],s[N],wa[N],n,height[N];

int Abs(int x){return x>0?x:-x;}
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p){
    for(p=0,i=n-j;i<n;i++)y[p++]=i;
    for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
    for(i=0;i<m;i++)ws[i]=0;
    for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
    for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void Calheight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

int Solve(int k){
int i=2,Mx,Mn;
while(1){
    while(i<=n && height[i]<k)i++;
    if(i>n)break;
    Mx=sa[i-1];Mn=sa[i-1];
    while(i<=n && height[i]>=k){Mn=min(Mn,sa[i]);Mx=max(Mx,sa[i]);i++;}
    if(Mx-Mn>=k)return 1;
}
return 0;
}

int Div(){
int l=4,r=n*2,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Solve(mid)){l=mid+1;ans=mid;}
    else r=mid-1;
}
ans++;
return ans<5?0:ans;
}

int main(){
freopen("1743.in","r",stdin);
freopen("1743.out","w",stdout);
while(scanf("%d",&n),n){
    for(int i=0;i<n;i++)scanf("%d",&s[i]);
    if(n<10){puts("0");continue;}
    n--;
    for(int i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;
    s[n]=0;
    for(int i=0;i<N;i++)wa[i]=ws[i]=0;
    GetSA(s,sa,n+1,200);
    Calheight(s,sa,n);
    printf("%d\n",Div());
}
return 0;
}

----------------------------------------

Category: OI | Tags: OI

4
30
2016

[BZOJ4025] 二分图

这题我写+调了一晚上……代码能力太差

首先忘了LCT怎么维护生成树，看了半天以前的代码

然后写了1.5h。。然后过不了样例

调试

呀！原来这里写错了！改！

样例还是不对……

调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试

Splay写错了！改！

样例过了！

提交，AC了！

真心写不动题解了……Claris题解

现在才真正感受到wzf AHOI2016Day1考场写12k+代码AK的可怕……我写调了将近3h，然而这代码4k不到……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=200005,INF=2100000000;

int n,m,T,cnt,in[N],on[N];

struct Line{int v;Line *next;Line(int ux=0){v=ux;next=NULL;}}*Sline[N],*Eline[N];
void AddLineS(int u,int v){Line *x=new Line(v);x->next=Sline[u];Sline[u]=x;}
void AddLineE(int u,int v){Line *x=new Line(v);x->next=Eline[u];Eline[u]=x;}

struct Edge{
int u,v,t;
}e[N];

struct Node{
int v,rev,sum,id;
Node *ch[2],*fa,*mne;
Node(){}
Node(int vx,int vy);
void Pushdown();
void Pushup();
}*tree[2*N],*Null;

Node::Node(int val,int vy){
v=val;
id=vy;
sum=id>n;
rev=0;
ch[0]=ch[1]=fa=Null;
mne=this;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}

void Node::Pushup(){
mne=this;
sum=id>n;
if(ch[0]!=Null){if(mne->v>ch[0]->mne->v)mne=ch[0]->mne;sum+=ch[0]->sum;}
if(ch[1]!=Null){if(mne->v>ch[1]->mne->v)mne=ch[1]->mne;sum+=ch[1]->sum;}
}

bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}
Node *GetNull(){Node *p=new Node(INF,0);p->v=INF;p->id=p->sum=p->rev=0;p->ch[0]=p->ch[1]=p->fa=p->mne=p;return p;}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;swap(x->ch[0],x->ch[1]);}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *ToLct(int x){return tree[x];}

void Add(int id){
int u=e[id].u,v=e[id].v;
if(u==v){cnt++;in[id]=1;return;}
if(Find(ToLct(u))!=Find(ToLct(v))){on[id]=1;Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));}
else {
	Makeroot(ToLct(u));
	Access(ToLct(v));
	Splay(ToLct(v));
	int idx=ToLct(v)->mne->id-n;
    if(e[idx].t<e[id].t){
		if(ToLct(v)->sum&1^1){in[idx]=1;cnt++;}
		Cut(ToLct(e[idx].u),ToLct(idx+n));Cut(ToLct(e[idx].v),ToLct(idx+n));
		Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));
		on[idx]=0;on[id]=1;
    }
    else if(ToLct(v)->sum&1^1){in[id]=1;cnt++;}
}
}

void Del(int id){
if(in[id]){in[id]=0;cnt--;}else if(on[id]){Cut(ToLct(e[id].u),ToLct(id+n));Cut(ToLct(e[id].v),ToLct(id+n));}
}

int main(){
freopen("4025.in","r",stdin);
freopen("4025.out","w",stdout);
scanf("%d %d %d",&n,&m,&T);
Null=GetNull();
for(int i=1;i<=n;i++)tree[i]=new Node(INF,i);
for(int i=1;i<=m;i++){
	int x;
	scanf("%d %d %d %d",&e[i].u,&e[i].v,&x,&e[i].t);
	AddLineS(x,i);
	AddLineE(e[i].t,i);
	tree[i+n]=new Node(e[i].t,i+n);
}
for(int i=0;i<T;i++){
	for(Line *j=Sline[i];j!=NULL;j=j->next)Add(j->v);
	for(Line *j=Eline[i];j!=NULL;j=j->next)Del(j->v);
	puts(cnt?"No":"Yes");
}
return 0;
}

Category: BZOJ | Tags: OI bzoj

« 上一页 1 2 3 4 5 6 7 8 9 10 11 12 … 19 20 下一页 »

Bless all

[BZOJ3626] [LNOI2014]LCA

[BZOJ3223] Tyvj 1729 文艺平衡树

[BZOJ2739] 最远点

[BZOJ2177] 曼哈顿最小生成树

[BZOJ1415] [Noi2005]聪聪和可可

[BZOJ3000] Big Number

后缀数组练习

[BZOJ4519] [Cqoi2016]不同的最小割

[BZOJ2229] [Zjoi2011]最小割

[BZOJ4025] 二分图

音乐播放器

分类

最新评论

最新留言

存档

链接

RSS

功能

地球

计数器