模板庫

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

讀入優化

char ch;
void read(int &n)
{
n=0;
ch=G();
while((ch<'0' || ch>'9') && ch!='-')ch=G();
ll w=1;
if(ch=='-')w=-1,ch=G();
while('0'<=ch && ch<='9')n=(n<<3) (n<<1) ch-'0',ch=G();
n*=w;
}

輸出優化

void write(int x)
{
if(x>9) write(x/10);
P(x%10 '0');
}

最短路(spfa)

    memset(dis,127,sizeof(dis));
memset(bz,1,sizeof(bz));
bz[n]=dis[n]=0;
d[1]=n;
int head=0,tail=1;
while(head<tail)
{
x=d[  head];
for(int i=last[x];i;i=next[i])
if(dis[a[i]]>dis[x] v[i] || (dis[a[i]]==dis[x] v[i] && b[f[a[i]]]>b[x]))
{
dis[a[i]]=dis[x] v[i];
f[a[i]]=x;
if(bz[a[i]])
{
bz[a[i]]=0;
d[  tail]=a[i];
}
}
bz[x]=1;
}

高精度

void add(arr a,arr b)
{
memset(t,0,sizeof(t));
int m=max(a[0],b[0]);
for(int i=1;i<=m;i  )
{
t[i] =a[i] b[i];
t[i 1] =t[i]/mo;
t[i]=t[i]%mo;
}
if(t[m 1]>0)t[0]=m 1;else t[0]=m;
}
void dd(arr a,arr b)
{
memset(tt,0,sizeof(tt));
for(int i=1;i<=a[0];i  )
{
tt[i] =a[i]-b[i];
while(tt[i]<0)
{
tt[i] =mo;
tt[i 1]--;
}
}
tt[0]=a[0];
while(!tt[tt[0]])tt[0]--;
}

線段樹

void work(int x)
{
if(t[x].l>=opl && t[x].r<=opr)
{
if(opx==1)t[x].x=min(t[x].x,ops);
if(opx==2)ops=min(ops,t[x].x);
return;
}
if(t[x].l==t[x].r)return;
int m=(t[x].l t[x].r)/2;
if(opl<=m)work(x x);
if(m<opr)work(x x 1);
t[x].x=min(t[x x].x,t[x x 1].x);
}

並查集

int get(int x){return x==f[x]?x:f[x]=get(f[x]);}

雜湊


inline void ins()
{
int x=y%mo;
while(f[x]!=0 && f[x]!=y)x=(x 1)%mo;
f[x]=y;g[x]  ;
}
inline int find()
{
int x=y%mo;
while(f[x]!=0 && f[x]!=y)x=(x 1)%mo;
return g[x];
}

tarjan

void tarjan(int x)
{
ti  ;
dfn[x]=low[x]=ti;
bz[x]=0;
ta  ;
z[ta]=x;
for(int i=lst[x];i;i=nxt[i])
{
if(dfn[to[i]]==0)
{
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
}
else if(!bz[to[i]])low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
for(cnt  ;z[ta]!=x && ta;ta--)F[g[z[ta]]=cnt] =V[z[ta]],bz[z[ta]]=1;
F[g[z[ta]]=cnt] =V[z[ta]],bz[z[ta]]=1;
ta--;
}
}

tarjan(人工棧)


void tarjan(int x)
{
d[r=1]=x;
while(r)
{
x=d[r];
if(dfn[x]==0)
{
z[  top]=x;
bz[x]=w[x]=0;
dfn[x]=low[x]=  now;
}
if(b[x])
{
int i=b[x];
if(p[i]==0)
{
low[x]=min(low[x],low[to[i]]);
} else
if(bz[to[i]])
{
if(p[i])
{
d[  r]=to[i];
p[i]=0;
continue;
}
}else if(!w[to[i]])
low[x]=min(low[x],dfn[to[i]]);
b[x]=nxt[i];
}
else
{   
if(low[x]==dfn[x])
{
cnt  ;
z[top 1]=-1;
while(z[top 1]!=x)
{
f[z[top]]=cnt;
v[cnt]  ;
w[z[top]]=1;
top--;
}
ans=max(ans,v[cnt]);
}
r--;
}
}
}

倍增LCA

int lca(int x,int y)
{
if(deep[x]>deep[y])swap(x,y);
for(int j=19;j>=0;j--)
if(deep[x]<=deep[f[y][j]])y=f[y][j];
if(x==y)return x;
for(int j=19;j>=0;j--)
if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
return f[x][0];
}

樹狀陣列

int low(int x)
{
return x & (-x);
}
int find(int x,int y)
{
int s=0;
for(int i=x;i;i=i-low(i))
s =z[y][i];
return s;
}
void change(int x,int y,int s)
{
for(int i=x;i<=n;i=i low(i))
z[y][i] =s;
}

優先佇列(堆)

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int x;
};
priority_queue <node> q;
//定義一個型別為node的優先佇列(使用堆的佇列) 
bool operator <(node a,node b){
return a.x>b.x;
}
//因為優先佇列預設為從大到小( 用"<"比較),我們若要從小到大,就要重新定義"<"為相反操作 
int main(){
int n;
cin>>n;
if (q.empty()) cout<<"The heap is empty!"<<endl;//判斷佇列是否為空 
for (int i=1;i<=n;  i){
node t;
cin>>t.x;
q.push(t);//將t加入佇列 
}
for (int i=1;i<=n;  i){
node t;
t=q.top();//取出隊首 
q.pop();//將隊首彈出 
cout<<t.x<<' ';
}
cout<<endl;
}

trie

int ins(char* s,int len)
{
int x=1;
for(int p=1;p<=len;p  )
{
if(tr[x].son[s[p]-'a']==0)
{
deep[  tot]=deep[x] 1;
tr[x].son[s[p]-'a']=tot;
f[tot][0]=x;
for(int j=1;j<20;j  )
f[tot][j]=f[f[tot][j-1]][j-1];
}
x=tr[x].son[s[p]-'a'];
}
return x;
}

kmp

void make(int* t,int len)
{
memset(nxt,0,sizeof(nxt));
int j=0;
for(int i=2;i<=len;i  )
{
while(j>0 && t[j 1]!=t[i])j=nxt[j];
if(t[i]==t[j 1])j  ;
nxt[i]=j;
}
}
int kmp(int l)
{
int j=0,sum=0;
for(int i=1;i<n;i  )
{
while(j>0 && a[i]!=b[j 1])j=nxt[j];
if(a[i]==b[j 1])j  ;
if(j==l)
{
sum  ;
j=nxt[l];
}
}
return sum;
}

最小生成樹(克魯斯卡爾)

 for(int i=1;t<n-1;i  )
{
f1=get(a[i].x);
f2=get(a[i].y);
if(f1!=f2)
{
ins(a[i].x,a[i].y,a[i].z);
ins(a[i].y,a[i].x,a[i].z);
fa[f2]=f1;
ans =a[i].z;
t  ;
bz[i]=0;
}
}

二分圖匹配(匈牙利演算法)

bool find(int x)
{
for(int i=b[x];i;i=next[i])
{
if(bz[t[i]])continue;
bz[t[i]]=1;
if(g[t[i]]==0 || find(g[t[i]]))
{
g[t[i]]=x;
return 1;
}
}
return 0;
}

最長迴文串


void manacher(char s[], int length, int rad[]) {
for (int i=1,j=0,k; i < length; i =k) {
while (s[i-j-1] == s[i j 1])   j;
rad[i] = j;
for (k = 1; k <= rad[i] && rad[i-k] != rad[i]-k;   k) 
{ 
rad[i k] = min(rad[i-k], rad[i]-k);
}
j = max(j-k, 0);
}
}

網路流


int nxt[N*2],to[N*2],v[N*2],last[N],cur[N],tot;
int q[N],h[N],S,T,ans;
int a[M][M],n,m,t;
bool bfs()
{
int head=0,tail=1;
for(int i=0;i<=T;i  )h[i]=-1;
q[0]=S;h[S]=0;
while(head!=tail)
{
int now=q[head];head  ;
for(int i=last[now];i;i=nxt[i])
if(v[i] && h[to[i]]==-1)
{
h[to[i]]=h[now] 1;
q[tail  ]=to[i];
}
}
return h[T]!=-1;
}
int dfs(int x,int f)
{
if(x==T)return f;
int w,used=0;
for(int i=cur[x];i;i=nxt[i])
if(h[to[i]]==h[x] 1)
{
w=f-used;
w=dfs(to[i],min(w,v[i]));
v[i]-=w;v[i^1] =w;
if(v[i])cur[x]=i;
used =w;
if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic()
{
while(bfs())
{
for(int i=0;i<=T;i  )
cur[i]=last[i];
ans =dfs(S,inf);
}
}

相關文章

程式語言 最新文章