3
3
2016
0

Diary of March 3rd

好消息 好消息 我的博客重开辣 _(:зゝ∠)_
因为今天阳阳的模拟赛靠三道暴力进了前15 心情舒畅
再加上晚上码字典树的时候忘记怎么打了  找不到代码回来看博客
突然发现写博客还是挺好的 复习比较方便
停了一个半月……还是再写起来吧

先把大串反一下  然后所有单词建一棵Trie
开个 F 数组记录一下要到达原串每个位置最后一个应该取哪个单词
不能到达的话就为0
然后从后往前输出就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#include<map>
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=10005,M=100005;
int n,m,cnt=0,nn=0;
char ch[N];
string s,word[M];
struct Trie{
	Trie *to[26];
	int idx;
	Trie(){Rep(i,0,25) to[i]=NULL;idx=0;}
}*root;
int f[N];
void Build(char *s){
	int len=strlen(s);
	Trie *now=root;
	Rep(i,0,len-1){
		int g=s[i]-'a';
		if (now->to[g]==NULL) now->to[g]=new Trie;
		now=now->to[g];
	}
	now->idx=cnt;
}
void GetAns(int pos){
	while (pos){
		printf("%s ",word[f[pos]].c_str());
		pos-=word[f[pos]].size();
	}
}
int main(){
	n=IN();root=new Trie;
	scanf("%s",ch);s=string(ch);
	reverse(s.begin(),s.end());
	m=IN();
	Rep(i,1,m){
		scanf("%s",ch);
		word[++cnt]=string(ch);
		int len=word[cnt].size();
		Rep(j,0,len-1) ch[j]=tolower(word[cnt][j]);
		ch[len]=0;
		Build(ch);
	}
	f[0]=1;
	Rep(i,0,s.size()-1){
		if (!f[i]) continue;
		Trie *now=root;
		Rep(j,i,s.size()-1){
			int g=s[j]-'a';
			if (now->to[g]!=NULL) now=now->to[g];else break;
			if (now->idx) f[j+1]=now->idx;
		}
	}
	GetAns(s.size());
}
#吾已将此身献给LCT#
这题是LCT维护一个最小生成树
我的做法是把边当成一个点,然后和它两端的结点相连
然后把删边改为倒序的加边
把删边改为给每条边打一个标记 这个可以用二分实现
首先把没删掉的边都加进去 然后再处理操作
每次加边的时候如果这条边两端结点不在同一个连通块就直接连上
否则询问这条边两端结点路径上的最大值
如果这个最大值比这条边权值大的话就cut再link
然后每次询问链上最大值就可以了
第一次用LCT维护连通性26S....第二次排了一下序再用并查集维护14S             23333
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005,M=1000005,Q=100005;
int n,m,q;
struct Edge{
	int u,v,w,idx;
	bool del;
}e[M];
bool cmp1(const Edge &a,const Edge &b){return a.u==b.u?a.v<b.v:a.u<b.u;}
bool cmp2(const Edge &a,const Edge &b){return a.w<b.w;}
struct Task{
	int op,x,y;
}md[Q];
struct SplayTree *null;
struct SplayTree{
	SplayTree *Fa,*Ls,*Rs,*Mx;
	int Val;
	bool Rev;
	bool Top(){return Fa==null || (Fa->Ls!=this&&Fa->Rs!=this);}
	void PushDown(){
		if (this==null) return;
		if (Rev){Rev=0;Ls->Rev^=1;Rs->Rev^=1;swap(Ls,Rs);}
	}
	void Update(){
		if (this==null) return;
		if (this-null>n) Mx=this;else Mx=null;
		if (Ls->Mx->Val>Mx->Val) Mx=Ls->Mx;
		if (Rs->Mx->Val>Mx->Val) Mx=Rs->Mx;
	}
	void Zig(){
		if (this==null) return;
		SplayTree *y=Fa,*z=y->Fa;
		if (z->Ls==y) z->Ls=this;else if (z->Rs==y) z->Rs=this;Fa=z;
		y->Ls=Rs;if (Rs!=null) Rs->Fa=y;
		Rs=y;y->Fa=this;y->Update();
	}
	void Zag(){
		if (this==null) return;
		SplayTree *y=Fa,*z=y->Fa;
		if (z->Ls==y) z->Ls=this;else if (z->Rs==y) z->Rs=this;Fa=z;
		y->Rs=Ls;if (Ls!=null) Ls->Fa=y;
		Ls=y;y->Fa=this;y->Update();
	}
}a[N+M],*S[N+M],*now;
int Top=0;
void Splay(SplayTree *x){
	now=x;while (!now->Top()) S[++Top]=now,now=now->Fa;
	now->PushDown();while (Top) S[Top--]->PushDown();
	while (!x->Top()){
		SplayTree *y=x->Fa,*z=y->Fa;
		if (!y->Top())
			if (z->Ls==y) if (y->Ls==x) y->Zig(),x->Zig();else x->Zag(),x->Zig();
				else if (y->Rs==x) y->Zag(),x->Zag();else x->Zig(),x->Zag();
		else if (y->Ls==x) x->Zig();else x->Zag(); 
	}
	x->Update();
}
SplayTree *Access(SplayTree *x){
	SplayTree *y=null;
	while (x!=null){
		Splay(x);
		x->Rs=y;x->Update();
		y=x;x=x->Fa;
	}
	return y;
}
void ChangeRoot(SplayTree *x){
	Access(x)->Rev^=1;
	Splay(x);
}
SplayTree *GetRoot(SplayTree *x){
	Access(x);Splay(x);
	x->PushDown();
	while (x->Ls!=null) x=x->Ls,x->PushDown();
	return x;
}
SplayTree *QueryMax(SplayTree *x,SplayTree *y){
	ChangeRoot(x);
	Access(y),Splay(y);
	return y->Mx;
}
void Link(SplayTree *x,SplayTree *y){
	ChangeRoot(x);x->Fa=y;
}
void Cut(SplayTree *x,SplayTree *y){
	ChangeRoot(y);
	Access(x),Splay(x);
	x->Ls->Fa=null;
	x->Ls=null;
}
void Delete(int u,int v){
	int l=1,r=m;
	while (l<r){
		int mid=l+r>>1;
		if (e[mid].u<u ||(e[mid].u==u&&e[mid].v<v)) l=mid+1;
			else r=mid;
	}
	while (l<=m&&e[l].u==u&&e[l].v==v) e[l].del=1,l++;
}
void Recover(int u,int v){
	int l=1,r=m;
	while (l<r){
		int mid=l+r>>1;
		if (e[mid].u<u ||(e[mid].u==u&&e[mid].v<v)) l=mid+1;
			else r=mid;
	}
	while (l<=m&&e[l].u==u&&e[l].v==v){
		int u=e[l].u,v=e[l].v,w=e[l].w;
		SplayTree *t=QueryMax(a+u,a+v);
		if (t->Val>w){
			Cut(t,a+e[t-null-n].v);
			Cut(t,a+e[t-null-n].u);
		}
		else{l++;continue;}
		a[n+l].Val=w,a[n+l].Mx=a+n+l,a[n+l].Rev=0;
		Link(a+u,a+n+l),Link(a+v,a+n+l);
		l++;
	}
}
int cnt,Ans[Q],fa[N],SZ[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	n=IN(),m=IN(),q=IN();
	Rep(i,1,m){
		e[i].u=IN(),e[i].v=IN(),e[i].w=IN(),e[i].del=0;
		if (e[i].u>e[i].v) swap(e[i].u,e[i].v);
	}
	sort(e+1,e+m+1,cmp1);
	Rep(i,1,m) e[i].idx=i;
	Rep(i,1,q){
		md[i].op=IN(),md[i].x=IN(),md[i].y=IN();
		if (md[i].op==2){
			if (md[i].x>md[i].y) swap(md[i].x,md[i].y);
			Delete(md[i].x,md[i].y);
		}
	}
	null=a;
	Rep(i,0,n+m) a[i]=(SplayTree){null,null,null,null,-oo,0};
	sort(e+1,e+m+1,cmp2);
	Rep(i,1,n) fa[i]=i,SZ[i]=1;
	int now=0;
	Rep(i,1,m){
		if (e[i].del) continue;
		int u=e[i].u,v=e[i].v,w=e[i].w,id=e[i].idx;
		int fu=find(u),fv=find(v);
		if (fu!=fv){
			a[n+id].Val=w,a[n+id].Mx=a+n+id,a[n+id].Rev=0;
			Link(a+u,a+n+id),Link(a+v,a+n+id);
			if (SZ[fv]<SZ[fu]) fa[fv]=fu,SZ[fv]+=SZ[fu];else fa[fu]=fv,SZ[fu]+=SZ[fv];
			now++;if (now==n-1) break;
		}
	}
	sort(e+1,e+m+1,cmp1);
	Drp(i,q,1){
		int x=md[i].x,y=md[i].y;
		if (md[i].op==1) Ans[++cnt]=QueryMax(a+x,a+y)->Val;
		else Recover(x,y);
	}
	Drp(i,cnt,1) Out(Ans[i]),putchar('\n');
}

 

Category: Diary | Tags: Trie LCT | Read Count: 177

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com