复习板子

本以为自己要和ACM说再见了，自己也开始新生活了。 人生如梦亦似幻，朝如晨露暮如霞。 还是继续吧

ST 算法

#include<bits/stdc++.h> using namespace std; const int N=100000; int f[N][30]; int a[N]; int n; int Q; void ST_prework(){ for(int i=1;i<=n;i++) f[i][0]=a[i]; int t=log(n)/log(2)+1; for(int j=1;j<t;j++) for(int i=1;i<n-(1<<j)+1;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int ST_query(int l,int r){ int k=log(r-l+1)/log(2); return max(f[l][k],f[r-(1<<k)+1][k]); } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; while(Q--){ int l,r; cin>>l>>r; cout<<ST_query(l,r)<<endl; } }

逆序对

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=5000005; int a[N],b[N]; ll cnt; int n; void mergesort(int l,int r){ if(r-1<1) return; int mid=(l+r)>>1; mergesort(l,mid),mergesort(mid+1,r); int i=l,j=mid+1; for(int k=l;k<=r;k++) if(i<=mid&&a[i]<=a[j]||j>r) b[k]=a[i++]; else b[k]=a[i++],cnt+=mid-i+1; for(int k=1;k<=r;k++) a[k]=b[k]; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; mergesort(1,n); cout<<cnt<<endl; }

dfs序列：

void dfs(int x){ a[++m]=x; vis[x]=1; for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(vis[y]) continue; dfs(y); } a[++m]=x; }

树的深度：

void dfs(int x){ vis[x]=1; for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(vis[y]) continue; d[y]=d[x]+1; dfs(y); } }

连通块划分：

int cnt=0; void dfs(int x){ vis[x]=1,sz[x]=1; int max_part=0; for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(vis[y]) continue; dfs(y); } for(int i=1;i<=n;i++){ if(!vis[i]) { cnt++; dfs(i); } } }

树的重心

int sz[N]; int ans; int max_part; int pos; int cnt=0; void dfs(int x){ vis[x],sz[x]=1; int max_part=0; for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(vis[y]) continue; dfs(y); sz[x]+=sz[y]; max_part=max(max_part,n-sz[y]); } max_part=max(max_part,n-sz[x]); if(max_part<ans){ ans=max_part; pos=x; } }

线段树

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=10000; int a[N]; namespace Seg{ #define lc p<<1 #define rc p<<1|1 #define mid ((t[p].l+t[p].r)>>1) struct node{ int l,r; int dat,sum,add; }t[N<<2]; void pushup(int p){ t[p].sum=t[lc].sum+t[rc].sum; } void spread(int p){ if(t[p].add){ t[lc].sum+=t[p].sum*(t[lc].r-t[lc].l+1); t[rc].sum+=t[p].sum*(t[rc].r-t[rc].l+1); t[lc].add+=t[p].add; t[rc].add+=t[p].add; t[p].add=0; } } void build(int p,int l,int r){ t[p].l=l,t[p].r=r; if(l==r){ t[p].sum=a[l];return; } build(lc,l,mid),build(rc,mid+1,r); pushup(p); } void update(int p,int l,int r,int d){ if(l<=t[p].l&&t[p].r<=r){ t[p].sum+=d*(t[p].r-t[p].l+1); t[p].add+=d; return; } spread(p); if(l<=mid) update(lc,l,r,d); if(r>mid) update(rc,l,r,d); } int query(int p,int l,int r){ if(l>=t[p].l&&t[p].r<=r) return t[p].sum; spread(p); ll val=0; if(l<=mid) val+=query(lc,l,r); if(r>mid) val+=query(rc,l,r); return val; } #undef lc #undef rc #undef mid } int main(){ return 0; }

LCA

#include<bits/stdc++.h> using namespace std; #define ll long long #define gc getchar inline int read(){ int f=1,res=0;char ch=gc(); while(!isdigit(ch)) f^=ch=='-',ch=gc(); while(isdigit(ch)) res=((res<<1)+(res<<3)+(ch^48)),ch=gc(); return f?res:res; } const int N=5000000; int head[N<<1],nex[N<<1],edge[N<<1],ver[N<<1],tot; void addedge(int u,int v,int w){ ver[++tot]=v,edge[tot]=w,nex[tot]=head[u],head[u]=tot; } int f[N][30]; int dist[N]; int d[N]; int t,root; int n; int Q; void bfs(int st){ memset(d,0,sizeof(d)); memset(dist,0,sizeof(dist)); d[st]=1,dist[st]=0; queue<int >q; q.push(st); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(d[y]) continue; dist[y]=dist[x]+edge[i]; d[y]=d[x]+1; f[y][0]=x; for(int i=1;i<=t;i++){ f[y][i]=f[f[y][i-1]][i-1]; } } } } int lca(int x,int y){ if(x>y) swap(x,y); for(int i=t;i;i--) if(d[f[y][i]]>=d[x]) y=f[y][i]; if(x==y) return x; for(int i=t;i;i--) if(f[y][i]!=f[x][i]) y=f[y][i],x=f[x][i]; return f[x][0]; } int main(){ n=read(),Q=read(),root=read(); t=(int)(log(n)/log(2))+1; for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); addedge(u,v,w); addedge(v,u,w); } bfs(root); while(Q--){ int x,y; printf("%d",lca(x,y)); printf("%d",dist[x],dist[y]-2*dist[lca(x,y)]); } }

拓扑排序

#include<bits/stdc++.h> using namespace std; const int N=10000; int head[N],nex[N],ver[N],tot; int deg[N]; void addedge(int u,int v){ ver[++tot]=v,nex[tot]=head[u]; head[u]=tot; deg[v]++; } int n,m,cnt=0; int a[N]; void topusort(){ queue<int> q; for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i); while(!q.empty()){ int x=q.front();q.pop(); a[++cnt]=x; for(int i =head[x];i;i=nex[i]){ int y=ver[i]; if(--deg[y]==0) q.push(y); } } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; addedge(x,y); } topusort(); for(int i=1;i<=n;i++){ printf("%d%c",i==n?'\n':' '); } }

floyd

for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

传递闭包

for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);

dijkstra

#include<bits/stdc++.h> using namespace std; #define ll long long #define gc getchar #define pii pair<int,int> inline int read(){ int f=1,res=0;char ch=gc(); while(!isdigit(ch)) f^=ch=='-',ch=gc(); while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=gc(); return f?res:-res; } const int N=500000; int head[N<<1],nex[N<<1],edge[N<<1],ver[N<<1],tot; void addegde(int u,int v,int w){ ver[++tot]=v,edge[tot]=w,nex[tot]=head[u],head[u]=tot; } int dist[N]; int vis[N]; void dijkstra(int st){ memset(dist,0x3f3f3f3f,sizeof(dist)); memset(vis,0,sizeof(vis)); dist[st]=0; priority_queue<pii> q; q.push({-dist[st],st}); while(!q.empty()){ pii pt=q.top();q.pop(); int x=pt.second; if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=nex[i]){ int y=ver[i]; if(dist[y]>dist[x]+edge[i]){ dist[y]=dist[x]+edge[i]; q.push({-dist[y],y}); } } } } int main(){ return 0; }

高精度：

#include<bits/stdc++.h> using namespace std; struct Bigint{ const static int M=10000; int num[M],len; Bigint(){clean();} void clean(){memset(num,0,sizeof(num));len=1;} void read(){ char str[M];scanf("%s",str); len=strlen(str); for(int i=1;i<=len;i++) num[i]=str[len-i]-'0'; } void write(){ for(int i=len;i>=1;i--) printf("%d",num[i]); printf("\n"); } void toBig(int x){ clean(); while(x){ num[len++]=x%10;x/=10; } if(len!=1) len--; } bool operator < (const Bigint &cmp) const { if(len!=cmp.len) return len<cmp.len; for(int i=len;i>=1;i--) if(num[i]!=cmp.num[i]) return num[i]<cmp.num[i]; return false; } bool operator > (const Bigint &cmp) const {return cmp < *this;} bool operator <=(const Bigint &cmp) const {return !(cmp<*this);} bool operator >=(const Bigint &cmp) const {return !(cmp>*this);} bool operator != (const Bigint &cmp) const {return cmp<*this||*this <cmp;} bool operator == (const Bigint &cmp) const {return !(cmp<*this||*this <cmp);} Bigint operator +(const Bigint &A) const { Bigint s; s.len=max(len,A.len); for(int i=1;i<=s.len;i++){ s.num[i]+=num[i]+A.num[i]; if(s.num[i]>=10){ s.num[i]-=10; s.num[i+1]++; } } while(s.num[s.len+1]) s.len++; return s; } Bigint operator - (const Bigint &A) const { Bigint s; s.len=max(len,A.len); for(int i=1;i<=len;i++){ s.num[i]+=num[i]-A.num[i]; if(s.num[i]<0){ s.num[i]+=10; s.num[i+1]--; } } while(!s.num[s.len]&&s.len>1) s.len--; return s; } Bigint operator * (const Bigint &A) const { Bigint s; if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0)) return s; s.len=len+A.len; for(int i=1;i<=len;i++) for(int j=1;j<=A.len;j++){ s.num[i+j-1]+=num[i]*A.num[j]; s.num[i+j]+=s.num[i+j-1]/10; s.num[i+j-1]%10; } while(s.num[s.len+1]) s.len++; return s; } Bigint operator / (const Bigint &A) const{ Bigint s; if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0)) return s; Bigint tmp,tmp2; s.len=0; for(int i=len;i>=1;i--){ tmp2.toBig(10); tmp=tmp*tmp2; tmp2.toBig(num[i]); tmp=tmp+tmp2; int flag=-1; for(int j=1;j<=10;j++){ tmp2.toBig(j); if(tmp2*A>tmp) { flag=j-1;break; } } s.num[++s.len]=flag; tmp2.toBig(flag); tmp=tmp-tmp2*A; } for(int i=1;i<=len/2;i++) swap(s.num[i],s.num[len-i+1]); while(!s.num[s.len]&&s.len>1) s.len--; return s; } Bigint operator % (const Bigint &A) const { Bigint s; Bigint p=*this/A; s=*this-p*A; return s; } }; int main(){ return 0; }