模板合集
noip將近，打打模板放松心情……
upd：童鞋們會發(fā)現(xiàn)博主tm都是rand著打的，并沒有分類，想到什么打什么、、、
另外，有些算法不涉及全部用法，如果有需要，可以問博主哦，若有錯誤，也歡迎指正哦。
upd：讓我打搜索？不存在的。還有網(wǎng)絡(luò)流，計算幾何什么的，本弱弱都不會~~
?
某些OJ支持的ONLINE_JUDGE：
1 namespace OJ{ 2 void Online_Judge() { 3 #ifndef ONLINE_JUDGE 4 freopen("in.txt","r",stdin); 5 freopen("out.txt","w",stdout); 6 #endif 7 } 8 }?
快讀/快寫：
1 namespace fastIO { 2 #define gec(c) getchar(c) 3 #define puc(c) putchar(c) 4 char ch; 5 inline int read() { 6 int x=0,f=1; ch=gec(); 7 while (ch<'0'||ch>'9') { 8 if (ch=='-') f=-f; 9 ch=getchar(); 10 } 11 while (ch>='0'&&ch<='9') { 12 x=(x<<3)+(x<<1)+ch-'0'; 13 ch=getchar(); 14 } 15 return x*f; 16 } 17 template <class T> inline void read(T &x=0) { 18 T f=1; ch=gec(); 19 while (ch<'0'||ch>'9') { 20 if (ch=='-') f=-f; 21 ch=gec(); 22 } 23 while (ch>='0'&&ch<='9') { 24 x=(x<<3)+(x<<1)+ch-'0'; 25 ch=gec(); 26 } 27 x*=f; 28 } 29 int cnt,w[20]; 30 template <class T> inline void write(T x) { 31 if (x==0) { 32 puc('0'); return; 33 } 34 if (x<0) { 35 x=-x; puc('-'); 36 } 37 for (cnt=0; x; x/=10) w[++cnt]=x%10; 38 for (; cnt; --cnt) puc(w[cnt]+48); 39 } 40 inline void newline() { 41 puc('\n'); 42 } 43 inline void newblank() { 44 puc(' '); 45 } 46 }?
實在不知道有上面，只好想到什么寫什么。。
左偏樹（大根）：
class node {private:int d; LL w; node *l,*r;public:node() {w=d=0,l=r=0;}inline void newnode(node* &c,LL w) {c=new node;c->w=w;}inline int dis(node* c) {return c==0?0:c->d;}inline void upd(node* c) {if (dis(c->l)<dis(c->r)) {std::swap(c->l,c->r);}c->d=dis(c->l)+1;}inline node* merge(node* a,node* b) {if (a==0) return b;if (b==0) return a;if (a->w<b->w) std::swap(a,b);a->r=merge(a->r,b);return upd(a),a;}inline node* remove(node* c) {node* t=c; delete t;c=merge(c->l,c->r);return c;}inline LL top(node* c) {return c->w;} }?
st表（最大值）：
1 namespace STtable { 2 using std::max; 3 int n,m,f[N][L]; 4 void init() { 5 for (int j=1; j<=17; j++) { 6 for (int i=1; i<=n-(1<<j)+1; i++) { 7 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 8 } 9 } 10 } 11 int ans(int l,int r) { 12 int c=log2(r-l+1); 13 return max(f[l][c],f[r-(1<<c)+1][c]); 14 } 15 }?
矩陣快速冪/矩陣乘法：
1 namespace MatExp { 2 struct Mat { 3 LL a[N][N]; 4 Mat() { 5 memset(a,0,sizeof a); 6 } 7 }ori,ans,one,tra; 8 Mat Mul(Mat a,Mat b) { 9 Mat c; 10 for (int k=0; k<3; ++k) { 11 for (int i=0; i<3; ++i) { 12 for (int j=0; j<3; j++) { 13 c.a[i][j]+=a.a[i][k]*b.a[i][j]; 14 } 15 } 16 } 17 for (int i=0; i<3; ++i) { 18 for (int j=0; j<3; ++j) { 19 c.a[i][j]%=mo; 20 } 21 } 22 return c; 23 } 24 Mat mexp(Mat b,int p) { 25 if (p<2) return p?b:one; 26 Mat t=mexp(b,p>>1); t=Mul(t,t); 27 return p&1?Mul(t,b):t; 28 } 29 }?
莫隊：
1 namespace MoAlgo { 2 struct opt { 3 int l,r,i; 4 bool operator < (const opt &u) const { 5 return l/b==u.l/b?r<u.r:l<u.l; 6 } 7 }q[N]; 8 void remove(int x) { 9 } 10 void add(int x) { 11 } 12 std::sort(q+1,q+1+m); 13 curl=1,curr=0,ans[0]=0; 14 for (int i=1; i<=m; i++) { 15 while (curl<q[i].l) remove(curl++); 16 while (curl>q[i].l) add(--curl); 17 while (curr>q[i].r) remove(curr--); 18 while (curr<q[i].r) add(++curr); 19 ans[q[i].i]=ans[0]; 20 } 21 }?
極大化：
1 namespace Maximation { 2 int l[N],r[N],u[N]; 3 void solve(char c) { 4 using std::max; 5 using std::min; 6 for (int j=1; j<=m; ++j) { 7 l[j]=0,r[j]=m+1,u[j]=0; 8 } 9 for (int i=1,las; i<=n; ++i) { 10 las=0; 11 for (int j=1; j<=m; ++j) { 12 if (a[i][j]!=c) { 13 l[j]=0,u[j]=0,las=j; 14 } 15 else { 16 l[j]=max(l[j],las),u[j]++; 17 } 18 } 19 las=m+1; 20 for (int j=m; j>=1; --j) { 21 if (a[i][j]!=c) { 22 r[j]=m+1,las=j; 23 } 24 else { 25 r[j]=min(r[j],las); 26 ans=max(ans,(r[j]-l[j]-1)*u[j]); 27 } 28 } 29 } 30 } 31 }?
并查集（加權(quán)）：
1 namespace UnionFindSet { 2 int fa[N],w[N]; 3 inline void change_w(int x) { 4 5 } 6 inline int get(int x) { 7 if (fa[x]==x) return x; 8 int p=get(fa[x]); 9 fa[x]=get(fa[x]); 10 change_w(x); 11 return fa[x]; 12 } 13 inline void unionset(int x,int y) { 14 x=get(x),y=get(y); 15 if (x!=y) { 16 fa[x]=y; 17 change_w(x); 18 } 19 } 20 }?
Trie樹（簡單）：
1 #define Trie node 2 class Trie { 3 private: 4 int w; node *ch[N]; 5 public: 6 node() { 7 w=0,memset(ch,0,sizeof ch); 8 } 9 int idx(char x) { 10 11 } 12 void insert(node *u,char a[]) { 13 int len=strlen(a+1); 14 for (int i=1,x; i<=len; ++i) { 15 x=idx(a[i]); 16 if (u->ch[x]==0) { 17 u->ch[x]=new node(); 18 } 19 u=u->ch[x]; 20 } 21 u->w=1; 22 } 23 int reply(node *u,char a[]) { 24 int len=strlen(a+1),ret=0; 25 for (int i=1,x; i<=len; ++i) { 26 x=idx(a[i]); 27 if (u->ch[x]==0) { 28 return ret; 29 } 30 u=u->ch[x]; 31 ret+=u->w; 32 } 33 return ret; 34 } 35 }?
zkw線段樹（簡單）：
1 class zkw { 2 private: 3 int w[N<<2],m; 4 public: 5 void setup() { 6 for (m=1; m<=n+1; m<<=1) ; 7 for (int i=m; i<=m-1+n; ++i) w[i]=a[i]; 8 for (int i=m-1; i; --i) w[i]=w[i<<1]+w[i<<1|1]; 9 } 10 void upd(int x,int v) { 11 x+=m-1,w[x]+=v; 12 for (x>>=1; x; x>>=1) { 13 w[x]=w[x<<1]+w[x<<1|1]; 14 } 15 } 16 int rep(int s,int t) { 17 if (s==t) return w[s+m-1]; 18 s+=m-1,t+=m-1; 19 int ret=w[s]+w[t]; 20 for (; s^t^1!=0; s>>=1,t>>=1) { 21 if (!(s&1)) ret+=w[s^1]; 22 if (t&1) ret+=w[t^1]; 23 } 24 return ret; 25 } 26 }?
樹鏈剖分（邊）：
1 #define sgt node 2 class sgt { 3 private: 4 int w,b; node *l,*r; 5 public: 6 inline node() { 7 w=b=0; l=r=0; 8 } 9 inline void pushup(node* c) { 10 c->w=0; 11 if (c->l!=0) c->w+=c->l->w; 12 if (c->r!=0) c->w+=c->r->w; 13 } 14 inline void pushdown(node* c) { 15 if (c->l!=0) { 16 c->l->w+=c->b; 17 c->l->b+=c->b; 18 } 19 if (c->r!=0) { 20 c->r->w+=c->b; 21 c->r->b+=c->b; 22 } 23 c->b=0; 24 } 25 inline void setup(node* &c,int l,int r) { 26 c=new node; 27 if (l==r-1) return; 28 int m=(l+r)>>1; 29 setup(c->l,l,m),setup(c->r,m,r); 30 } 31 inline void upd(node* &c,int l,int r,int aiml,int aimr,int v) { 32 if (c==0||aiml>=aimr) return; 33 if (l>=aiml&&r<=aimr) { 34 c->w+=v,c->b+=v; 35 return; 36 } 37 int m=(l+r)>>1; 38 if (aimr<=m) upd(c->l,l,m,aiml,aimr,v); else 39 if (aiml>=m) upd(c->r,m,r,aiml,aimr,v); else 40 upd(c->l,l,m,aiml,aimr,v),upd(c->r,m,r,aiml,aimr,v); 41 pushup(c); 42 } 43 inline int rep(node* &c,int l,int r,int aiml,int aimr) { 44 if (c==0||aiml>=aimr) return 0; 45 if (l>=aiml&&r<=aimr) return c->w; 46 pushdown(c); 47 int m=(l+r)>>1; 48 if (aimr<=m) return rep(c->l,l,m,aiml,aimr); else 49 if (aiml>=m) return rep(c->r,m,r,aiml,aimr); else 50 return rep(c->l,l,m,aiml,aimr)+rep(c->r,m,r,aiml,aimr); 51 } 52 } 53 class TCP { 54 private: 55 int tot,lnk[N],nxt[N<<1],son[N<<1]; 56 int fa[N],dep[N],siz[N],got[N]; 57 int clo,dfn[N],top[N],le[N]; 58 public: 59 inline void init() { 60 tot=0,ms(lnk,0),ms(nxt,0); 61 fa[1]=0,dep[0]=0,siz[0]=0; 62 clo=0,ms(le,0); 63 } 64 inline void add(int x,int y) { 65 nxt[++tot]=lnk[x],lnk[x]=tot,son[tot]=y; 66 } 67 inline void dfs(int x,int p) { 68 fa[x]=p,dep[x]=dep[p]+1,siz[x]=1,got[x]=0; 69 for (int j=lnk[x]; j; j=nxt[j]) { 70 if (son[j]==p) continue; 71 dfs(son[j],x); 72 siz[x]+=siz[son[j]]; 73 if (siz[son[j]]>siz[got[x]]) { 74 got[x]=son[j]; 75 } 76 } 77 } 78 inline void redfs(int x,int r) { 79 dfn[x]=++clo,top[x]=r; 80 if (got[x]) { 81 redfs(got[x],r); 82 } 83 for (int j=lnk[x]; j; j=nxt[j]) { 84 if (son[j]==fa[x]||son[j]==got[x]) continue; 85 redfs(son[j],son[j]); 86 } 87 } 88 inline void upd(int x,int y) { 89 while (top[x]!=top[y]) { 90 if (dep[top[x]]<dep[top[y]]) { 91 swap(x,y); 92 } 93 s.upd(ro,1,n,dfn[top[x]],dfn[x],1); 94 ++le[top[x]]; 95 x=fa[top[x]]; 96 } 97 if (dep[x]<dep[y]) { 98 swap(x,y); 99 } 100 s.upd(ro,1,n,dfn[y],dfn[x],1); 101 } 102 inline int rep(int x,int y) { 103 int ret=0; 104 while (top[x]!=top[y]) { 105 if (dep[top[x]]<dep[top[y]]) { 106 swap(x,y); 107 } 108 ret+=s.rep(ro,1,n,dfn[top[x]],dfn[x]); 109 ret+=le[top[x]]; 110 x=fa[top[x]]; 111 } 112 if (dep[x]<dep[y]) { 113 swap(x,y); 114 } 115 ret+=s.rep(ro,1,n,dfn[y],dfn[x]); 116 return ret; 117 } 118 }?
線性篩（樸素）：
1 void sieve() { 2 memset(isp,1,sizeof isp),isp[0]=isp[1]=0; 3 memset(p,0,sizeof p),cnt=0; 4 for (int i=2; i<N; i++) { 5 if (isp[i]) p[++cnt]=i; 6 for (int j=1; j<=cnt&&i*p[j]<N; j++) { 7 isp[i*p[j]]=0; 8 if (i%p[j]==0) break; 9 } 10 } 11 }?
堆（小根）：
1 namespace Heap { 2 int a[N],len,fa,son; 3 void init() { 4 memset(a,0,sizeof a),len=0; 5 } 6 void put(int x) { 7 a[++len]=x,son=len; 8 while (son>1) { 9 if (a[son>>1]>a[son]) { 10 swap(a[son>>1],a[son]); 11 son>>=1; 12 } else break; 13 } 14 } 15 void pop() { 16 swap(a[1],a[len]),--len,fa=1; 17 while (fa<<1<=len) { 18 if ((fa<<1|1)>len||a[fa<<1]<a[fa<<1|1]) son=fa<<1; 19 else son=fa<<1|1; 20 if (a[fa]>a[son]) { 21 swap(a[fa],a[son]),fa=son; 22 } else break; 23 } 24 } 25 int top() { 26 return a[1]; 27 } 28 }?
最小生成樹：
1 namespace kruskal { 2 int fa[N],vis[N],ans; 3 struct R{ 4 int a,b,c; 5 bool operator < (const R &u) const { 6 return c<u.c; 7 } 8 }e[N]; 9 int get(int x) { 10 return fa[x]==x?x:fa[x]=get(fa[x]); 11 } 12 void MST() { 13 for (int i=1; i<=n; ++i) fa[i]=i; 14 for (int i=1; i<=m; ++i) { 15 scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c); 16 } 17 sort(e+1,e+1+m); 18 for (int i=1,x,y; i<=m; ++i) { 19 x=get(e[i].a),y=get(e[i].b); 20 if (x==y) continue; 21 fa[x]=y,ans+=e[i].c; 22 } 23 printf("%d\n",ans); 24 } 25 } 26 namespace prim { 27 int ans,tot,lnk[N],nxt[N<<1],son[N<<1],w[N<<1]; 28 int dis[N]; bool vis[N]; 29 priority_queue <pair<int,int> > q; 30 void add(int x,int y,int z) { 31 nxt[++tot]=lnk[x],lnk[x]=tot,son[tot]=y,w[tot]=z; 32 } 33 void MST() { 34 for (int i=1,x,y,z; i<=m; ++i) { 35 scanf("%d%d%d",&x,&y,&z); 36 add(x,y,z),add(y,x,z); 37 } 38 memset(vis,0,sizeof vis); 39 memset(dis,30,sizeof dis),dis[1]=0; 40 ans=0; 41 while (!q.empty()) q.pop(); q.push(make_pair(0,1)); 42 for (int x; !q.empty(); ) { 43 x=q.top().second,q.pop(); 44 if (vis[x]) continue; 45 vis[x]=1,ans+=dis[x]; 46 for (int j=lnk[x]; j; j=nxt[j]) { 47 if (!vis[son[j]]&&dis[son[j]]>w[j]) { 48 dis[son[j]]=w[j]; 49 q.push(make_pair(-dis[son[j]],son[j])); 50 } 51 } 52 } 53 printf("%d\n",ans); 54 } 55 }?
三分：
1 namespace TriSection { 2 int l,r,lm,rm; 3 int calc(int x) { 4 } 5 void solve() { 6 while (r-l>=eps) { 7 lm=l+(r-l)/3,rm=r-(r-l)/3; 8 if (calc(lm)<calc(rm)) l=lm; else r=rm; 9 } 10 cout<<l<<endl; 11 } 12 }?
快排：
1 void qsort(int l,int r) { 2 int i=l,j=r,m=a[l+rand()%(r-l+1)]; 3 do { 4 while (a[i]<m) ++i; 5 while (a[j]>m) --j; 6 if (i<=j) swap(a[i],a[j]),++i,--j; 7 }while (i<=j); 8 if (l<j) qsort(l,j); 9 if (i<r) qsort(i,r); 10 }?
樹狀數(shù)組：
1 namespace BIT { 2 void upd(int x,int v) { 3 for (int i=x; i<=n; i+=i&(-i)) c[i]+=v; 4 } 5 int rep(int x) { 6 int ret=0; 7 for (int i=x; i; i-=i&(-i)) ret+=c[i]; 8 return ret; 9 } 10 }?
單源最短路：
1 namespace spfa { 2 int tot,lnk[N],nxt[M<<1],son[M<<1],w[M<<1]; 3 int dis[N]; bool vis[N]; 4 queue <int> q; 5 void add(int x,int y,int z) { 6 nxt[++tot]=lnk[x],lnk[x]=tot,son[tot]=y,w[tot]=z; 7 } 8 void SP() { 9 for (int i=1,x,y,z; i<=m; ++i) { 10 scanf("%d%d%d",&x,&y,&z); 11 add(x,y,z); 12 } 13 memset(vis,0,sizeof vis); 14 memset(dis,30,sizeof dis),dis[s]=0; 15 while (!q.empty()) q.pop(); q.push(s); 16 for (int x; !q.empty(); ) { 17 x=q.front(),q.pop(),vis[x]=0; 18 for (int j=lnk[x]; j; j=nxt[j]) { 19 if (dis[son[j]]>dis[x]+w[j]) { 20 dis[son[j]]=dis[x]+w[j]; 21 if (!vis[son[j]]) vis[son[j]]=1,q.push(son[j]); 22 } 23 } 24 } 25 } 26 } 27 namespace dij { 28 int tot,lnk[N],nxt[M<<1],son[M<<1],w[M<<1]; 29 int dis[N]; bool vis[N]; 30 priority_queue <pair<int,int> > q; 31 void add(int x,int y,int z) { 32 nxt[++tot]=lnk[x],lnk[x]=tot,son[tot]=y,w[tot]=z; 33 } 34 void SP() { 35 for (int i=1,x,y,z; i<=m; ++i) { 36 scanf("%d%d%d",&x,&y,&z); 37 add(x,y,z); 38 } 39 memset(vis,0,sizeof vis); 40 memset(dis,30,sizeof dis),dis[s]=0; 41 while (!q.empty()) q.pop(); q.push(make_pair(0,s)); 42 for (int x; !q.empty(); ) { 43 x=q.top().second,q.pop(); 44 if (vis[x]) continue; else vis[x]=1; 45 for (int j=lnk[x]; j; j=nxt[j]) { 46 if (!vis[son[j]]&&dis[son[j]]>dis[x]+w[j]) { 47 dis[son[j]]=dis[x]+w[j]; 48 q.push(make_pair(-dis[son[j]],son[j])); 49 } 50 } 51 } 52 } 53 }?
倍增求lca：
1 namespace lca_rmq { 2 int dep[N],fa[N][K+1]; 3 void dfs(int x,int p) { 4 dep[x]=dep[p]+1,fa[x][0]=p; 5 for (int j=lnk[x]; j; j=nxt[j]) { 6 if (son[j]!=p) dfs(son[j],x); 7 } 8 } 9 void pre() { 10 for (int j=1; j<=K; ++j) 11 for (int i=1; i<=n; ++i) 12 fa[i][j]=fa[fa[i][j-1]][j-1]; 13 } 14 int lca(int x,int y) { 15 if (dep[x]<dep[y]) swap(x,y); 16 int dif=dep[x]-dep[y]; 17 for (int i=K; ~i; --i) 18 if (dif&(1<<i)) x=fa[x][i]; 19 if (x==y) return x; 20 for (int i=K; ~i; --i) 21 if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; 22 return fa[x][0]; 23 } 24 }?
匈牙利：
1 namespace Hungary { 2 bool dfs(int x) { 3 for (int j=lnk[x],y; j; j=nxt[j]) { 4 if (!vis[son[j]]) { 5 vis[y=son[j]]=1; 6 if (!mat[y]||dfs(mat[y])) { 7 return mat[y]=x,1; 8 } 9 } 10 } 11 return 0; 12 } 13 }?
spfa判全局負環(huán)：
1 namespace NegCircle { 2 bool flg; 3 void dfs_spfa(int u){ 4 v[u]=1; 5 for (int j=lnk[u]; j&&!flg; j=nxt[j]) { 6 if (d[son[j]]>d[u]+w[j]) { 7 d[son[j]]=d[u]+w[j]; 8 if (v[son[j]]) { 9 flg=1; 10 return; 11 } 12 dfs_spfa(son[j]); 13 } 14 } 15 v[u]=0; 16 } 17 bool check() { 18 flg=0; 19 for (int i=1; i<=n; ++i) { 20 dfs(i); 21 if (flg) return 1; 22 } 23 return 0; 24 } 25 }?
高斯消元（解的情況，異或方程組）：
1 int Gauss(int equ,int var) { 2 int R=1,C=1; 3 for (; R<=equ&&C<=var; R++,C++) { 4 int Mx=R; 5 for (int i=R+1; i<=equ; i++) 6 if (abso(a[i][C])>abso(a[Mx][C])) i=Mx; 7 if (Mx!=R) 8 for (int j=C; j<=var+1; j++) swap(a[Mx][j],a[R][j]); 9 if (a[R][C]==0) {R--; continue;} 10 for (int i=R+1; i<=equ; i++) if (a[i][C]!=0) { 11 int LCM=lcm(abso(a[i][C]),abso(a[R][C])); 12 int tx=LCM/abso(a[i][C]),ty=LCM/abso(a[R][C]); 13 if (a[i][C]*a[R][C]<0) ty=-ty; 14 for (int j=C; j<=var+1; j++) a[i][j]=a[i][j]*tx-a[R][j]*ty; 15 } 16 } 17 for (int i=R; i<=equ; i++) if (a[i][var+1]!=0) return -1; 18 if (R<=var) return var-R+1; 19 for (int i=n; i; i--) { 20 int res=a[i][var+1]; 21 for (int j=i+1; j<=var; j++) if (a[i][j]!=0) res-=a[i][j]*x[j]; 22 x[i]=res/a[i][i]; 23 } 24 return 0; 25 } 26 void Gauss(){ 27 int row=1,col=1; 28 for (; row<=N&&col<=N; row++,col++) { 29 int Mx_r=row; 30 for (int i=row+1; i<=N; i++) 31 if (abso(a[i][col])>abso(a[Mx_r][col])) Mx_r=i; 32 if (Mx_r!=row) 33 for (int j=col; j<=N+1; j++) swap(a[Mx_r][j],a[row][j]); 34 for (int i=row+1; i<=N; i++) if (a[i][col]) 35 for (int j=col; j<=N+1; j++) a[i][j]^=a[row][j]; 36 } 37 for (int i=N; i>=1; i--) { 38 x[i]=a[i][N+1]; 39 for (int j=i+1; j<=N; j++) x[i]^=(a[i][j]&&x[j]); 40 } 41 }?
割點：
1 void dfs(int x,int p) { 2 low[x]=dfn[x]=++clo; int c=0; 3 for (int j=lnk[x],y; j; j=nxt[j]) { 4 if (son[j]==p) continue; 5 if (!dfn[y=son[j]]) { 6 ++c; 7 dfs(y,x); 8 low[x]=min(low[x],low[y]); 9 if (low[y]>=dfn[x]) { 10 iscut[x]=1; 11 } 12 } else 13 if (dfn[x]>dfn[y]) { 14 low[x]=min(low[x],dfn[y]); 15 } 16 } 17 if (!p&&c<2) iscut[x]=0; 18 }?
歸并排序求逆序?qū)?#xff1a;
1 void msort(int l,int r) { 2 if (l==r) return; 3 int m=(l+r)>>1; 4 msort(l,m),msort(m+1,r); 5 for (int i=l; i<=r; ++i) t[i]=a[i]; 6 int u=l,v=m+1; 7 for (int i=l; i<=r; ++i) { 8 if ((t[u]<t[v]&&u<=m)||v>r) { 9 a[u++]=t[i]; 10 } else { 11 a[v++]=t[i]; 12 ans+=m-i+1; 13 } 14 } 15 }?
強連通分量：
1 void dfs(int x) { 2 low[x]=dfn[x]=++clo,ins[x]=1,s.push(x); 3 for (int j=ori.lnk[x]; j; j=ori.nxt[j]) { 4 if (!dfn[ori.son[j]]) { 5 dfs(ori.son[j]); 6 low[x]=min(low[x],low[ori.son[j]]); 7 } else 8 if (ins[ori.son[j]]) { 9 low[x]=min(low[x],dfn[ori.son[j]]); 10 } 11 } 12 if (low[x]==dfn[x]) { 13 ++scc; 14 for (int y; ; ) { 15 ins[y=s.top()]=0,s.pop(); 16 fa[y]=scc,w[scc]+=a[y]; 17 if (y==x) return; 18 } 19 } 20 }?
斜優(yōu)dp：
1 namespace slopedp { 2 int top; 3 struct point { 4 LL x,y; 5 point() {} 6 point(LL _x,LL _y):x(_x),y(_y) {} 7 }st[N]; 8 double slope(point u,point v) { 9 return 1.0*(v.y-u.y)/(v.x-u.x); 10 } 11 int get(int k) { 12 while (top>1&&slope(st[top-1],st[top])<1.0*k) --top; 13 return st[top].y-k*st[top].x; 14 } 15 void insert(point cur) { 16 while (top>1&&slope(st[top-1],st[top])<slope(st[top],cur)) --top; 17 st[++top]=cur; 18 } 19 int solve() { 20 } 21 }?
gcd和lcm：
1 inline int gcd(int x,int y) { 2 return y?gcd(y,x%y):x; 3 } 4 inline int lcm(int x,int y) { 5 return x/gcd(x,y)*y; 6 }?
exgcd：
1 inline int exgcd(int a,int b,int &X,int &Y) { 2 if (!b) {X=1; Y=0; return a;} 3 int g=exgcd(b,a%b,X,Y),X0=X,Y0=Y; 4 X=Y0,Y=X0-A*Y0/B; 5 return g; 6 }?
floyd多源最短路：
1 for (int k=1; k<=n; ++k) 2 for (int i=1; i<=n; ++i) 3 for (int j=1; j<=n; ++j) 4 f[i][j]=min(f[i][j],f[i][k]+f[k][j]);?
floyd求平面最小環(huán)：
1 for (int k=1; k<=n; ++k) { 2 for (int i=1; i<k; ++i) 3 for (int j=1; j<k; ++j) 4 ans=min(ans,f[i][j]+w[i][k]+w[k][j]); 5 for (int i=1; i<=n; ++i) 6 for (int j=1; j<=n; ++j) 7 f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 8 }?
次小生成樹：
1 namespace SMST { 2 int sum,ans,f[N],g[N][N],pre[N]; bool vis[N]; 3 void solve() { 4 vis[1]=1; 5 for (int i=1; i<=n; ++i) { 6 f[i]=g[1][i]=a[1][i],pre[i]=1; 7 } 8 for ( ; ; ) { 9 int k=-1,minor=inf; 10 for (int i=1; i<=n; ++i) 11 if (!vis[i]&&minor>f[i]) k=i,minor=f[i]; 12 if (k==-1) break; 13 vis[k]=1,sum+=minor; 14 used[k][pre[k]]=used[pre[k]][k]=1; 15 for (int i=1; i<=n; ++i) { 16 if (vis[i]&&i!=k) g[k][i]=g[i][k]=max(f[k],g[i][pre[k]]); 17 if (!vis[i]&&f[i]>d[k][i]) f[i]=d[k][i],pre[i]=k; 18 } 19 } 20 ans=inf; 21 for (int i=1; i<n; ++i) 22 for (int j=i+1; j<=n; ++j) 23 if (!used[i][j]) ans=min(ans,a[i][j]); 24 ans=sum-ans; 25 } 26 }?
線段樹（最簡單版）：
1 #define sgt node 2 class sgt { 3 private: 4 int v,t; node *l,*r; 5 public: 6 #define m ((l)+(r)>>1) 7 node() {l=r=0,v=t=0;} 8 inline void pushup(node* cu) { 9 cu->v=0; 10 if (cu->l!=0) cu->v+=cu->l->v; 11 if (cu->r!=0) cu->v+=cu->r->v; 12 } 13 inline void pushdown(node *cu) { 14 if (cu->l!=0) cu->l->t+=cu->t,cu->l->v+=cu->t; 15 if (cu->r!=0) cu->r->t+=cu->t,cu->r->v+=cu->t; 16 cu->t=0; 17 } 18 inline void setup(node* &cu,int l,int r) { 19 cu=new node; 20 if (l+1==r) {cu->v=cu->t=0; return;} 21 setup(cu->l,l,m),setup(cu->r,m,r); 22 pushup(cu); 23 } 24 inline void update(node* &cu,int l,int r,int aiml,int aimr) { 25 if (l>=aiml&&r<=aimr) {cu->v++,cu->t++; return;} 26 pushdown(cu); 27 if (aimr<=m) update(cu->l,l,m,aiml,aimr); else 28 if (aiml>=m) update(cu->r,m,r,aiml,aimr); 29 else update(cu->l,l,m,aiml,aimr),update(cu->r,m,r,aiml,aimr); 30 pushup(cu); 31 } 32 inline int answer(node* &cu,int l,int r,int x) { 33 if (l+1==r) return cu->v; 34 pushdown(cu); 35 return x<m?answer(cu->l,l,m,x):answer(cu->r,m,r,x); 36 } 37 }?
笛卡爾樹：
1 namespace CartesianTree { 2 struct node { 3 int k,x,i,f,l,r; 4 }a[N]; 5 int s[N],top; 6 bool cmp_k(const node &u,const node &v) { 7 return u.k<v.k; 8 } 9 bool cmp_i(const node &u,const node &v) { 10 return u.i<v.i; 11 } 12 void solve() { 13 a[0].l=a[0].r=a[0].i=0,a[0].k=a[0].x=-inf; 14 sort(a+1,a+1+n,cmp_k); 15 s[top=1]=0; 16 for (int i=1,las=-1; i<=n; i++,las=-1) { 17 while (top&&a[s[top]].x>a[i].x) las=s[top],top--; 18 a[i].f=a[s[top]].i,a[s[top]].r=a[i].i; 19 if (~las) a[i].l=a[las].i,a[las].f=a[i].i; 20 s[++top]=i; 21 } 22 sort(a+1,a+1+n,cmp_i); 23 } 24 }?
旋轉(zhuǎn)式treap：
1 #define Treap node 2 class node { 3 private: 4 int w,k,s,t; node* c[2]; 5 public: 6 node() { 7 c[0]=c[1]=0; s=t=1; 8 } 9 void newnode(node* &cu,int x) { 10 cu=new node(),cu->w=x,cu->k=rand(); 11 } 12 void upd(node* &cu) { 13 cu->s=cu->t; 14 if (cu->c[0]) cu->s+=cu->c[0]->s; 15 if (cu->c[1]) cu->s+=cu->c[1]->s; 16 } 17 void rotate(node* &cu,bool p) { 18 node* tmp=cu->c[p^1]; 19 cu->c[p^1]=tmp->c[p]; 20 tmp->c[p]=cu,cu=tmp; 21 upd(cu->c[p]); 22 upd(cu); 23 } 24 void insert(node* &cu,int x) { 25 if (!cu) { 26 newnode(cu,x); return; 27 } else 28 if (cu->w==x) { 29 ++cu->s; ++cu->t; return; 30 } 31 bool p=x>cu->w; 32 insert(cu->c[p],x); 33 if (cu->k<cu->c[p]->k) { 34 rotate(cu,p^1); 35 } else upd(cu); 36 } 37 void erase(node* &cu,int x) { 38 if (!cu) return; 39 if (cu->w==x) { 40 if (cu->t>1) { 41 --cu->s; --cu->t; return; 42 } 43 if (!cu->c[0]&&!cu->c[1]) { 44 cu=0; return; 45 } 46 if (!cu->c[0]||!cu->c[1]) { 47 cu=cu->c[0]?cu->c[0]:cu->c[1]; 48 return; 49 } 50 bool p=cu->c[0]->k<cu->c[1]->k; 51 rotate(cu,p^1); 52 erase(cu->c[p^1],x); 53 upd(cu); 54 } else { 55 bool p=x>cu->w; 56 erase(cu->c[p],x); 57 upd(cu); 58 } 59 } 60 int rank(node* &cu,int x) { 61 if (!cu) return 0; 62 int s=!cu->c[0]?0:cu->c[0]->s; 63 if (cu->w==x) return s+1; else 64 if (x<cu->w) return rank(cu->c[0],x); 65 else return s+cu->t+rank(cu->c[1],x); 66 } 67 int kth(node* &cu,int x) { 68 if (!cu) return 0; 69 int s=!cu->c[0]?0:cu->c[0]->s; 70 if (x>s&&x<=s+cu->t) return cu->w; 71 if (x<=s) return kth(cu->c[0],x); 72 else return kth(cu->c[1],x-s-cu->t); 73 } 74 void pre(node* &cu,int x) { 75 if (!cu) return; 76 if (x<=cu->w) pre(cu->c[0],x); 77 else ans=cu->w,pre(cu->c[1],x); 78 } 79 void suc(node* &cu,int x) { 80 if (!cu) return; 81 if (x>=cu->w) suc(cu->c[1],x); 82 else ans=cu->w,suc(cu->c[0],x); 83 } 84 }?
字符串哈希：
1 class HashMap { 2 private: 3 static const LL p1=10007,p2=2040803,p3=19260817,sed=255; 4 bool f1[p1+5],f2[p2+5],f3[p3+5]; 5 public: 6 void init() { 7 ms(f1,0),ms(f2,0),ms(f3,0); 8 } 9 bool find(char s[],int len) { 10 LL k=0,k1,k2,k3; 11 for (int i=0; i<len; ++i) k=k*sed+s[i]; 12 k1=(k%p1+p1)%p1; 13 k2=(k%p2+p2)%p2; 14 k3=(k%p3+p3)%p3; 15 return f1[k1]&&f2[k2]&&f3[k3]; 16 } 17 void insert(char s[],int len) { 18 LL k=0,k1,k2,k3; 19 for (int i=0; i<len; ++i) k=k*sed+s[i]; 20 k1=(k%p1+p1)%p1; 21 k2=(k%p2+p2)%p2; 22 k3=(k%p3+p3)%p3; 23 f1[k1]=f2[k2]=f3[k3]=1; 24 } 25 }?
普通哈希拉鏈法：
1 class Hashmap { 2 private: 3 #define p 2040803 4 #define ms(a,x) memset(a,x,sizeof a) 5 LL lnk[p+5],son[N]; int nxt[N],tot; 6 public: 7 void clear() { 8 ms(lnk,-1),ms(nxt,-1),tot=0; 9 } 10 void insert(LL x) { 11 LL k=x%p; if (k<0) k+=p; 12 if (lnk[k]==-1) { 13 lnk[k]=++tot,son[tot]=x; 14 return; 15 } 16 for (int j=lnk[k]; ; j=nxt[j]) { 17 if (nxt[j]==-1) { 18 nxt[j]=++tot,son[j]=x; 19 return; 20 } 21 } 22 } 23 bool find(LL x) { 24 LL k=x%p; if (k<0) k+=p; 25 for (int j=lnk[k]; ~j; j=nxt[j]) { 26 if (son[j]==x) { 27 return 1; 28 } 29 } 30 return 0; 31 } 32 }?
基數(shù)排序：
1 const int ra=1024; 2 void rsort() { 3 p[0]=1; for (int i=1; i<3; ++i) p[i]=p[i-1]*ra; 4 for (int i=0; i<3; ++i) { 5 memset(x,0,sizeof x); 6 for (int j=1; j<=n; ++j) ++x[(a[j]/p[i])&(ra-1)]; 7 for (int j=1; j<ra; ++j) x[j]+=x[j-1]; 8 for (int j=n; j; --j) b[x[(a[j]/p[i])&(ra-1)]--]=a[j]; 9 swap(a,b); 10 } 11 }?
簡易高精：
1 struct bigint { 2 #define ms(a,x) memset(a,x,sizeof a) 3 #define N 1005 4 #define mo 10000 5 int a[N],len; 6 bigint () { 7 ms(a,0),len=0; 8 } 9 bigint (int x) { 10 ms(a,0),len=0; 11 if (x==0) { 12 a[len=1]=0; return; 13 } 14 for (; x; x/=mo) { 15 a[++len]=x%mo; 16 } 17 } 18 bigint (char s[]) { 19 ms(a,0),len=0; 20 len=strlen(s),reverse(s,s+len); 21 for (int i=0; i<len; ++i) { 22 a[i/4+1]=a[i/4+1]+p[i%4]*(s[i]-'0'); 23 } 24 len=(len-1)/4+1; 25 } 26 bigint operator + (const bigint b) { 27 bigint c; c.len=max(len,b.len); 28 for (int i=1; i<=c.len; ++i) { 29 c.a[i]+=a[i]+b.a[i]; 30 c.a[i+1]=c.a[i]/mo; 31 c.a[i]%=mo; 32 } 33 if (c.a[c.len+1]) ++c.len; 34 return c; 35 } 36 bigint operator - (const bigint b) { 37 bigint c; c.len=len; 38 for (int i=1; i<=c.len; ++i) { 39 c.a[i]+=a[i]-b.a[i]; 40 if (c.a[i]<0) { 41 c.a[i]+=mo,--c.a[i+1]; 42 } 43 } 44 while (c.len>1&&!c.a[c.len]) --c.len; 45 return c; 46 } 47 bigint operator * (const bigint b) { 48 bigint c; c.len=len+b.len-1; 49 for (int i=1; i<=len; ++i) { 50 for (int j=1; j<=b.len; ++j) { 51 c.a[i+j-1]+=a[i]*b.a[j]; 52 c.a[i+j]+=c.a[i+j-1]/mo; 53 c.a[i+j-1]%=mo; 54 } 55 } 56 if (c.a[c.len+1]) ++c.len; 57 while (c.len>1&&!c.a[c.len]) --c.len; 58 return c; 59 } 60 bigint operator / (const int b) { 61 bigint c; c.len=len; LL r=0; 62 for (int i=len; i; --i) { 63 r=r*mo+a[i]; 64 c.a[i]=r/b; 65 r%=b; 66 } 67 while (c.len>1&&!c.a[c.len]) --c.len; 68 return c; 69 } 70 bool operator < (const bigint b) { 71 if (len<b.len) return 1; 72 if (len>b.len) return 0; 73 for (int i=len; i; --i) { 74 if (a[i]<b.a[i]) return 1; 75 if (a[i]>b.a[i]) return 0; 76 } 77 return 0; 78 } 79 bool operator > (const bigint b) { 80 if (len<b.len) return 0; 81 if (len>b.len) return 1; 82 for (int i=len; i; --i) { 83 if (a[i]<b.a[i]) return 0; 84 if (a[i]>b.a[i]) return 1; 85 } 86 return 0; 87 } 88 bool operator == (const bigint b) { 89 if (len!=b.len) return 0; 90 for (int i=len; i; --i) { 91 if (a[i]!=b.a[i]) return 0; 92 } 93 return 1; 94 } 95 void write() { 96 printf("%d",a[len]); 97 for (int i=len-1; i; --i) { 98 printf("%04d",a[i]); 99 } 100 putchar('\n'); 101 } 102 }?
轉(zhuǎn)載于:https://www.cnblogs.com/whc200305/p/7802196.html
總結(jié)
- 上一篇： alm系统的使用流程_ALM用户使用手册
- 下一篇： StatusBarUtil 状态栏工具类