ACM数据结构部分模版.docx
《ACM数据结构部分模版.docx》由会员分享，可在线阅读，更多相关《ACM数据结构部分模版.docx（40页珍藏版）》请在冰点文库上搜索。
ACM数据结构部分模版
数据结构：
增加栈
#pragmacomment（linker,"/STACK:
1024000000,1024000000"）
二维树状数组
#include
#include
#include
#definemaxn130
usingnamespacestd;
intxt[maxn][maxn][maxn];
intadd,z,n;
intlow（intx）
{
returnx&（-x）;
}
//二维树状数组，第三维枚举
voidup（intx,inty）
{
inti,j;
for（i=x;i<=maxn;i+=low（i））
for（j=y;j<=maxn;j+=low（j））
{
xt[z][i][j]+=add;
if（xt[z][i][j]<0）xt[z][i][j]=0;
}
}
intsum（intx,inty）
{
inti,ans=0;
for（i=x;i>0;i-=low（i））
for（intj=y;j>0;j-=low（j））
{
ans+=xt[z][i][j];
}
returnans;
}
intmain（）
{
intx,y,a;
intx1,y1,z1,z2;
intx2,y2,ans;
while（cin>>n）
{
memset（xt,0,sizeof（xt））;
while（scanf（"%d",&a）&&a!
=3）
{
ans=0;
if（a==1）
{
scanf（"%d%d%d%d",&x,&y,&z,&add）;
x+=2;y+=2;z+=2;
up（x,y）;
}
elseif（a==2）
{
scanf（"%d%d%d",&x1,&y1,&z1）;
scanf（"%d%d%d",&x2,&y2,&z2）;
//树状数组必须大于0，而且是整数
x1+=2;x2+=2;y1+=2;y2+=2;z1+=2;z2+=2;
for（z=z1;z<=z2;z++）
{//求矩阵（x1,y1）（x2,y2）（对角）的和公式
//sum（x2,y2）-sum（x1-1,y2）-sum（x2,y1-1）+sum（x1-1,y1-1）
ans+=（sum（x2,y2）-sum（x1-1,y2）-sum（x2,y1-1）+sum（x1-1,y1-1））;
}
printf（"%d\n",ans）;
}
}
线段树成段更新
voiddown（into,intL,intR）
{
if（add[o]!
=0）
{
sum[o]+=add[o]*（R-L+1）;
}
}
voidupdate（intL,intR,into）
{
if（L>=ql&&qr>=R）
{
add[o]+=v;
sum[o]+=v*（R-L+1）;
return;
}
intmid=（L+R）>>1;
if（ql<=mid）update（L,mid,o<<1）;
if（qr>mid）update（mid+1,R,o<<1|1）;
sum[o]=sum[o<<1]+sum[o<<1|1];
down（o,L,R）;
}
voidfind（intL,intR,into,LL_add）
{
if（L>=ql&&qr>=R）
{
v+=sum[o];
v+=_add*（R-L+1）;
return;
}
intmid=（L+R）>>1;
if（ql<=mid）find（L,mid,o<<1,_add+add[o]）;
if（qr>mid）find（mid+1,R,o<<1|1,_add+add[o]）;
}
voidpush（into）
{
intlc=o*2;intrc=o*2+1;
if（set[o]>=0）//往下更新
{
set[lc]=set[rc]=set[o];
set[o]=-1;//记得标记
}
}
voidupdate（into,intL,intR）
{
intlc=o*2,rc=o*2+1;
if（x1<=L&&x2>=R）
{
set[o]=v;
}
else
{
push（o）;//把之前没有更新的一起带下去更新
intmid=（L+R）/2;
if（x1<=mid）update（lc,L,mid）;
if（x2>mid）update（rc,mid+1,R）;
}
}
//求居间不同数个数
voidfind（into,intL,intR）
{
if（set[o]!
=-1）
{
if（set[o]>0&&!
vi[set[o]]）
{
vi[set[o]]=1;
mun++;
}//如果当前有标记则不再往下找
return;
}
if（L==R）return;
intmid=（L+R）>>1;
find（o*2,L,mid）;
find（o*2+1,mid+1,R）;
}
KMP：
voidget（）
{
inti,j=-1;
f[0]=-1;
for（i=1;iwhile（j>=0&&p[j+1]!
=p[i]）j=f[j];
if（p[j+1]==p[i]）j++;
f[i]=j;
}
}
voidfind（）
{
inti,j=-1;
get（）;
for（i=0;iwhile（j>=0&&p[j+1]!
=T[i]）j=f[j];
if（p[j+1]==T[i]）j++;
if（j==m-1）{
mun++;
j=-1;
}
}
}
intmain（）
{
while（scanf（"%s",T）!
=EOF）{
if（T[0]=='#'&&strlen（T）==1）break;
n=strlen（T）;
scanf（"%s",p）;
m=strlen（p）;
mun=0;
find（）;
cout<}
}
差分约束
//用SPFA解差分方程，用最短路径求差分方程的最大解；用最长路径求差分方程的最小解.
//d[t+1]-d[s]>=c,也就是dist[t+1]>=dist[s]+c,
//这是求最长路的形式,所以要求最长路//看形势
voidspfa（intMax,intMin）
{
inti,j,now;
intu,w;
memset（vi,0,sizeof（vi））;
queueq;
for（i=Min;i<=Max;i++）
d[i]=-INF;//因为求最长路
d[Min]=0;
q.push（Min）;
vi[1]=Min;
while（!
q.empty（））
{
now=q.front（）;
q.pop（）;
for（i=0;i{
piia=qe[now][i];
u=a.first;
w=a.second;
if（d[u]{
d[u]=w+d[now];
if（!
vi[u]）
{
q.push（u）;
vi[u]=1;
}
}
}
vi[now]=0;
}
}
intmain（）
{
inti,j,n,m;
intu,v,w,len,Max=MAX,Min;
while（scanf（"%d",&n）!
=EOF）
{
for（i=0;i<=Max;i++）
qe[i].clear（）;
Max=0;Min=INF;
for（i=1;i<=n;i++）
{
scanf（"%d%d%d",&u,&v,&w）;
qe[u].push_back（pii（v+1,w））;
if（v+1>Max）
Max=v+1;
if（u}
for（i=Min;i{
qe[i+1].push_back（pii（i,-1））;
qe[i].push_back（pii（i+1,0））;
}
spfa（Max,Min）;
cout<printf（"%d\n",d[Max]-d[Min]）;
}
}
LCA离线算法
typedefpairpii;
vectormap[M],query[M];
intfa[M],dis[M],ans[M];
boolvi[M];
intn,m;
voidin（）
{
inta,b,c,i;
charqq;
cin>>m;
for（i=0;iscanf（"%d%d%d%c",&a,&b,&c,&qq）;
map[a].push_back（pii（b,c））;
map[b].push_back（pii（a,c））;
}
cin>>m;
for（i=0;iscanf（"%d%d",&a,&b）;
query[a].push_back（pii（b,i））;//这就是离线
query[b].push_back（pii（a,i））;
}
memset（vi,0,sizeof（vi））;
}
intfind（intx）{
if（fa[x]!
=x）
fa[x]=find（fa[x]）;
returnfa[x];
}
voiddfs（intu,intlen）{
fa[u]=u;//往下找防止找到最后父亲
dis[u]=len;
vi[u]=1;
inti,j;
for（i=0;iintv=map[u][i].first;
intw=map[u][i].second;
if（!
vi[v]）{
dfs（v,len+w）;
fa[v]=u;//延后处理
}
}
for（i=0;iintv=query[u][i].first;
intw=query[u][i].second;
if（vi[v]）{
ans[w]=dis[u]+dis[v]-2*dis[fa[find（v）]];//公式
}
}
}
intmain（）
{
while（cin>>n）{
in（）;
dfs（1,0）;
for（inti=0;iprintf（"%d\n",ans[i]）;
}
}
AC自动机
structtrie
{
intch[maxn][4],cnt,end[maxn],root,fail[maxn];
intnewnode（）
{
memset（ch[cnt],-1,sizeof（ch[cnt]））;
end[cnt]=0;fail[cnt++]=-1;
returncnt-1;
}
voidinit（）
{
cnt=0;
root=newnode（）;
}
voidinsert（charss[]）
{
intc,u=root,n=strlen（ss）;
for（inti=0;i{
c=id（ss[i]）;
if（ch[u][c]==-1）ch[u][c]=newnode（）;
u=ch[u][c];
}
end[u]=1;
}
queueQ;
voidgetfail（）
{
inti,u=root;
fail[root]=root;
for（i=0;i<4;i++）
if（ch[root][i]==-1）ch[root][i]=root;
else
{
fail[ch[root][i]]=root;
Q.push（ch[root][i]）;
}
while（!
Q.empty（））
{
intpos=Q.front（）;Q.pop（）;
if（end[fail[pos]]==1）
end[pos]=1;
for（i=0;i<4;i++）
if（ch[pos][i]==-1）
ch[pos][i]=ch[fail[pos]][i];
else
{
fail[ch[pos][i]]=ch[fail[pos]][i];
Q.push（ch[pos][i]）;
}
}
}
intquery（chars[]）
{
intn=strlen（s）,pos=root,ans=0,tmp;
for（inti=0;i{
tmp=ch[pos][s[i]-'a'];
pos=tmp;
while（tmp!
=root）
{
ans+=end[tmp];
end[tmp]=0;
tmp=fail[tmp];
}
}
returnans;
}
nodeget（）
{
nodeans;
n=cnt;
ans.Clear（）;
for（inti=0;ifor（intj=0;j<4;j++）if（end[ch[i][j]]==0）
ans.mat[i][ch[i][j]]++;
returnans;
}
intsolve（charss[]）
{
inttmp,u,i,j,pos;
intn=strlen（ss）;
for（i=0;i<=n;i++）
for（j=0;jdp[i][j]=INF;
dp[0][root]=0;
for（i=0;ifor（j=0;j{
for（u=0;u<4;u++）
{
pos=ch[j][u];
if（end[pos]==1）continue;
if（u==id（ss[i]））tmp=dp[i][j];
elsetmp=dp[i][j]+1;
dp[i+1][pos]=min（dp[i+1][pos],tmp）;
}
}
pos=INF;
for（i=0;ipos=min（pos,dp[n][i]）;
if（pos==INF）return-1;
returnpos;
}
}AC;
intmain（）
{
inti,m,nn;
LLans;
charss[12];
//freopen（"in.txt","r",stdin）;
while（scanf（"%d%d",&m,&nn）!
=EOF）
{
AC.init（）;
while（m--）
{
scanf（"%s",ss）;
AC.insert（ss）;
}
AC.getfail（）;
nodea=AC.get（）;
init（）;
a=pow（a,nn）;
ans=0;
for（i=0;ians=（ans+a.mat[0][i]）%mod;
cout<}
return0;
}
2-SAT
booldfs（intx）
{
if（mark[x^1]）return0;
if（mark[x]）return1;
mark[x]=1;
s[mun++]=x;
for（inti=0;iif（!
dfs（qe[x][i]））return0;
return1;
}
boolsolve（）
{
inti,j;
for（i=0;iif（!
mark[i]&&!
mark[i+1]）
{
mun=0;
if（!
dfs（i））
{
while（mun>0）mark[s[--mun]]=0;
if（!
dfs（i+1））return0;
}
}
return1;
}
voidGet_map（intx,inta,inty,intb）
{
x=（x<<1）+a;y=（y<<1）+a;
qe[x^1].push_back（y）;
qe[y^1].push_back（x）;
}
boolfind（intmid）
{
inti,j,a,b;
for（i=1;i<=m;i++）for（a=0;a<2;a++）
for（j=i+1;j<=m;j++）for（b=0;b<2;b++）
if（abs（map[i][a]-map[j][b]）{
Get_map（i,a,j,b）;
}
if（solve（））return0;
return1;
}
intmain（）
{
inti,Min;
ints,e,Max,mid;
intL,R;
while（scanf（"%d",&m）!
=EOF）
{
Max=0;Min=INF;
for（i=1;i<=m;i++）
{
scanf（"%d%d",&s,&e）;
map[i][0]=s;
map[i][1]=e;
Max=max（Max,e）;
Min=min（Min,s）;
}
R=（Max-Min+1）/m;L=0;
while（L<=R）
{
mid=（R+L）>>1;
if（find（mid））R=mid-1;
elseL=mid+1;
}
printf（"%d\n",mid）;
for（i=0;i<=Max;i++）
qe[i].clear（）;
}
}
后缀数组
#include
#include
#include
usingnamespacestd;
#definemaxn1010010
ints[maxn],t[maxn],t2[maxn];
intc[maxn],sa[maxn];
voidbuild_sa（intn,intm）
{
inti,*x=t,*y=t2,p,j;
升级会员 