线性筛
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"bitset"using namespace std;const int MAXN=1e7+5;int n;int pri[MAXN/10];int mu[MAXN],phi[MAXN];bitset b;int main(){ scanf("%d",&n);mu[1]=phi[1]=1; for(int i=2;i<=n;++i){ if(!b[i]) pri[++pri[0]]=i,mu[i]=-1,phi[i]=i-1; for(int j=1;j<=pri[0]&&pri[j]*i<=n;++j){ b[i*pri[j]]=1; if(i%pri[j]) mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]]; else{mu[i*pri[j]]=0,phi[i*pri[j]]=pri[j]*phi[i];break;} } }return 0;}
线性求逆元
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=20000528;int n,p;int inv[MAXN];int main(){ scanf("%d%d",&n,&p);inv[1]=1; for(int i=2;i<=n;++i) inv[i]=(long long)(p-(p/i))*inv[p%i]%p; for(int i=1;i<=n;++i) printf("%d\n",inv[i]); return 0;} 三分法
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const double eps=1e-8;const double ct=1.0/3;int n;double L,R;double a[14];double calc(double x){ double s=a[0]; for(int i=1;i<=n;++i) s=s*x+a[i]; return s;}int main(){ scanf("%d%lf%lf",&n,&L,&R); for(int i=0;i<=n;++i) scanf("%lf",&a[i]); double l=L,r=R; while(r-l>eps){ double mid1=l+(r-l)*ct,mid2=r-(r-l)*ct; if(calc(mid1)>calc(mid2)) r=mid2; else l=mid1; }printf("%.5lf",l); return 0;} 线段树
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<18;int n,m,p;int a[MAXN];int tree[MAXN],tag[2][MAXN];void build(int k,int l,int r){ tag[0][k]=0;tag[1][k]=1; if(l==r){ tree[k]=a[l]; return; }int i=k<<1,mid=l+r>>1; build(i,l,mid);build(i|1,mid+1,r); tree[k]=(tree[i]+tree[i|1])%p;}void init(){ scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n);return;}void pd(int k,int l,int r){ if(l==r||(!tag[0][k]&&tag[1][k]==1)) return; int i=k<<1,mid=l+r>>1; tag[0][i]=((long long)tag[0][i]*tag[1][k]%p+tag[0][k])%p; tag[0][i|1]=((long long)tag[0][i|1]*tag[1][k]%p+tag[0][k])%p; tag[1][i]=(long long)tag[1][i]*tag[1][k]%p; tag[1][i|1]=(long long)tag[1][i|1]*tag[1][k]%p; tree[i]=((long long)tree[i]*tag[1][k]%p+(long long)tag[0][k]*(mid-l+1)%p)%p; tree[i|1]=((long long)tree[i|1]*tag[1][k]%p+(long long)tag[0][k]*(r-mid)%p)%p; tag[0][k]=0;tag[1][k]=1;return;}void ctag(int k,int l,int r,int le,int ri,int x,bool kd){ pd(k,l,r); if(le<=l&&r<=ri){ tag[kd][k]=x; if(kd) tree[k]=(long long)tree[k]*x%p; else tree[k]=(tree[k]+(long long)x*(r-l+1))%p; return; }int i=k<<1,mid=l+r>>1; if(le<=mid) ctag(i,l,mid,le,ri,x,kd); if(mid >1; if(le<=mid) sum=cask(i,l,mid,le,ri); if(mid 树链剖分LCA
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<19;int n,m,root,np;int h[MAXN],top[MAXN],dep[MAXN];int f[MAXN],sn[MAXN],siz[MAXN];struct rpg{ int li,nx;}a[MAXN<<1];inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||'9' hwysn){ hwysn=siz[a[i].nx]; sn[x]=a[i].nx; } } }return;}void dfs2(int x,int tpx){ top[x]=tpx; if(sn[x]) dfs2(sn[x],tpx); for(int i=h[x];i;i=a[i].li){ if(a[i].nx!=f[x]&&a[i].nx!=sn[x]){ dfs2(a[i].nx,a[i].nx); } }return;}int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]] 树链剖分
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<17;int n,m,root,MOD,np;int siz[MAXN],sn[MAXN],f[MAXN],id[MAXN],num[MAXN];int ren[MAXN],top[MAXN],dep[MAXN],h[MAXN];int tree[MAXN<<1],pls[MAXN<<1];struct rpg{ int li,nx;}a[MAXN<<1];inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||'9' hwysn){ hwysn=siz[a[i].nx]; sn[x]=a[i].nx; } } }return;}void dfs2(int x,int tpx){ top[x]=tpx;id[x]=++id[0];ren[id[x]]=num[x]; if(sn[x]) dfs2(sn[x],tpx); for(int i=h[x];i;i=a[i].li){ if(a[i].nx!=f[x]&&a[i].nx!=sn[x]){ dfs2(a[i].nx,a[i].nx); } }return;}void build(int k,int l,int r){ if(l==r){ tree[k]=ren[l]; return; }int i=k<<1,mid=l+r>>1; build(i,l,mid);build(i|1,mid+1,r); tree[k]=(tree[i]+tree[i|1])%MOD;}void init(){ n=read(),m=read(),root=read(),MOD=read(); for(int i=1;i<=n;++i) num[i]=read(); for(int i=1;i >1; pls[i]=(pls[i]+pls[k])%MOD; pls[i|1]=(pls[i|1]+pls[k])%MOD; tree[i]=(tree[i]+pls[k]*(mid-l+1))%MOD; tree[i|1]=(tree[i|1]+pls[k]*(r-mid))%MOD; pls[k]=0;return;}void cpls(int k,int l,int r,int le,int ri,int x){ pd(k,l,r); if(le<=l&&r<=ri){ pls[k]=x; tree[k]=(tree[k]+x*(r-l+1))%MOD; return; }int i=k<<1,mid=l+r>>1; if(le<=mid) cpls(i,l,mid,le,ri,x); if(mid dep[y]) swap(x,y); cpls(1,1,n,id[x],id[y],z); return;}int cask(int k,int l,int r,int le,int ri){ pd(k,l,r); if(le<=l&&r<=ri) return tree[k]; int i=k<<1,mid=l+r>>1,sum=0; if(le<=mid) sum=cask(i,l,mid,le,ri); if(mid dep[y]) swap(x,y); sum=(sum+cask(1,1,n,id[x],id[y]))%MOD; return sum;}void solve(){ while(m--){ int k=read(); if(k==1){int x=read(),y=read(),z=read();ccpls(x,y,z);} else if(k==2){int x=read(),y=read();printf("%d\n",ccask(x,y));} else if(k==3){int x=read(),z=read();cpls(1,1,n,id[x],id[x]+siz[x]-1,z);} else {int x=read();printf("%d\n",cask(1,1,n,id[x],id[x]+siz[x]-1));} }return;}main(){ init(); solve(); return 0;} 矩阵快速幂
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=105;const int MOD=1e9+7;int n;long long k;struct matrix{ long long val[MAXN][MAXN]; void reset(){memset(val,0,sizeof(val));} matrix Mmul(matrix a,matrix b) { matrix c;c.reset(); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ for(int k=1;k<=n;++k){ c.val[i][j]=(c.val[i][j]+a.val[i][k]*b.val[k][j])%MOD; } } }return c; } matrix MFpw(matrix a,long long b,int siz) { matrix x;x.reset(); for(int i=1;i<=siz;++i) x.val[i][i]=1; while(b){ if(b&1) x=Mmul(x,a); b>>=1;a=Mmul(a,a); }return x; } void write() { for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ printf("%lld ",val[i][j]); }puts(""); }return; }}a;int main(){ scanf("%d%lld",&n,&k); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ scanf("%lld",&a.val[i][j]); } }a=a.MFpw(a,k,n); a.write(); return 0;} 可持久化线段树
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<18;int n,m,cnt;int rev[MAXN],rt[MAXN];int val[MAXN<<5],L[MAXN<<5],R[MAXN<<5];struct rpg{ int a,b,id;}v[MAXN];bool cmp1(rpg a,rpg b){return a.a >1; val[id]=val[rid]+1; if(l==r) return; ++cnt; if(x<=mid) L[id]=cnt,R[id]=R[rid],ins(L[rid],cnt,x,l,mid); else R[id]=cnt,L[id]=L[rid],ins(R[rid],cnt,x,mid+1,r); return;}int query(int lid,int rid,int x,int l,int r){ if(l==r) return l; int mid=l+r>>1;int ct=val[L[rid]]-val[L[lid]]; if(x<=ct) return query(L[lid],L[rid],x,l,mid); return query(R[lid],R[rid],x-ct,mid+1,r);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&v[i].a),v[i].id=i; sort(v+1,v+n+1,cmp1); for(int i=1;i<=n;++i) v[i].b=i,rev[i]=v[i].a; sort(v+1,v+n+1,cmp2); for(int i=1;i<=n;++i) ++cnt,rt[i]=cnt,ins(rt[i-1],rt[i],v[i].b,1,n); while(m--){ int l,r,c;scanf("%d%d%d",&l,&r,&c); printf("%d\n",rev[query(rt[l-1],rt[r],c,1,n)]); }return 0;} 树状数组（单修区查）
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=5e5+5;int n,m;int btre[MAXN];inline int read(){ int x=0;bool f=0;char ch=getchar(); while(ch<'0'||'9' 二维树状数组（单修区查）
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e5+5;int n,m;long long BIT[2][MAXN];void cadd(int x,long long v){ for(int i=x;i<=n;i+=i&(-i)){ BIT[0][i]+=v; BIT[1][i]+=v*(x-1); }return;}long long query(int x){ long long sum=0; for(int i=x;i;i-=i&(-i)){ sum+=BIT[0][i]*x; sum-=BIT[1][i]; }return sum;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ long long x;scanf("%lld",&x); cadd(i,x);cadd(i+1,-x); }while(m--){ int p,l,r; scanf("%d%d%d",&p,&l,&r); if(p==1){long long x;scanf("%lld",&x);cadd(l,x);cadd(r+1,-x);} else printf("%lld\n",query(r)-query(l-1)); }return 0;} 树状数组（区修区查）
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1<<11|1;int n,m,q;long long bit[4][MAXN][MAXN];void cadd(int x,int y,long long v){ for(int i=x;i<=n;i+=i&(-i)){ for(int j=y;j<=m;j+=j&(-j)){ bit[0][i][j]+=v; bit[1][i][j]+=v*(x-1); bit[2][i][j]+=v*(y-1); bit[3][i][j]+=v*(x-1)*(y-1); } }return;}long long cask(int x,int y){ long long sum=0; for(int i=x;i;i&=i-1){ for(int j=y;j;j&=j-1){ sum+=bit[0][i][j]*x*y; sum-=bit[1][i][j]*y; sum-=bit[2][i][j]*x; sum+=bit[3][i][j]; } }return sum;}void cad(int sx,int sy,int tx,int ty,long long v){ cadd(sx,sy,v); cadd(sx,ty+1,-v); cadd(tx+1,sy,-v); cadd(tx+1,ty+1,v); return;}long long query(int sx,int sy,int tx,int ty){ return cask(tx,ty)-cask(tx,sy-1)-cask(sx-1,ty)+cask(sx-1,sy-1);}int main(){ scanf("%d%d",&n,&m); while(scanf("%d",&q)==1){ int sx,sy,tx,ty; scanf("%d%d%d%d",&sx,&sy,&tx,&ty); if(q==1){long long x;scanf("%lld",&x);cad(sx,sy,tx,ty,x);} else printf("%lld\n",query(sx,sy,tx,ty)); }return 0;} EXGCD
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;int x,y,n,m,k;int exgcd(int a,int b,int &x,int &y){ if(!b){x=1;return a;} int c=exgcd(b,a%b,y,x); y-=a/b*x;return c;}int main(){ scanf("%d%d%d",&n,&m,&k); int c=exgcd(n,m,x,y); if(k%c) puts("-1"); else printf("%d %d",x*k/c,y*k/c); return 0;} EXCRT
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;int n;long long a,b,ans,asmd;long long Fml(long long a,long long b,long long MOD){ long long x=0; while(b){ if(b&1) x=(x+a)%MOD; b>>=1;a=(a<<1)%MOD; }return x;}long long Exgcd(long long a,long long b,long long &x,long long &y){ if(!b){x=1,y=0;return a;} long long c=Exgcd(b,a%b,y,x); y-=a/b*x;return c;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%lld%lld",&a,&b); if(i==1){ans=b,asmd=a;continue;} long long x,y,nw=((b-ans)%a+a)%a; long long c=Exgcd(asmd,a,x,y); nw/=c;x=Fml(x,nw,a/c); ans+=x*asmd;asmd*=a/c; ans=(ans%asmd+asmd)%asmd; }printf("%lld\n",ans); return 0;} Lucas
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e5+5;int T,n,m,MOD;int fac[MAXN],inv[MAXN];int Lucas(int m,int n){ if(n SA
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e6+5;char ch[MAXN];int ln,maxn;int SA[MAXN],rnk[MAXN],bnk[MAXN],id[MAXN];void shel(){ memset(bnk,0,sizeof(bnk)); for(int i=1;i<=ln;++i) ++bnk[rnk[i]]; for(int i=1;i<=maxn;++i) bnk[i]+=bnk[i-1]; for(int i=ln;i;--i) SA[bnk[rnk[id[i]]]--]=id[i]; return;}int main(){ scanf("%s",ch+1);ln=strlen(ch+1); for(int i=1;i<=ln;++i) rnk[i]=ch[i],id[i]=i,maxn=max(maxn,rnk[i]); shel(); for(int k=1;k <<=1){ for(int i=1;i<=k;++i) id[i]=ln-k+i; int ct=k;for(int i=1;i<=ln;++i) if(SA[i]>k) id[++ct]=SA[i]-k; shel();swap(id,rnk);rnk[SA[1]]=1; for(int i=2;i<=ln;++i) rnk[SA[i]]=(id[SA[i]]==id[SA[i-1]]&&id[SA[i]+k]==id[SA[i-1]+k])?rnk[SA[i-1]]:rnk[SA[i-1]]+1; if(rnk[SA[ln]]==ln) break; maxn=rnk[SA[ln]]; }for(int i=1;i<=ln;++i) printf("%d ",SA[i]); return 0;} Kruskal
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=5005;const int MAXM=2e5+5;int n,m,sum;int f[MAXN];struct rpg{ int ls,nx,ln;}a[MAXM];bool cmp(rpg a,rpg b){return a.ln Dijkstra
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"bitset"using namespace std;const int MAXN=1e5+5;const int INF=2e9;int n,m,s,np;int hp[MAXN],h[MAXN],ln[MAXN],id[MAXN];struct rpg{ int li,nx,ln;}a[MAXN<<1];inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||'9' >1;j;i=j,j>>=1){ if(ln[hp[i]] ln[hp[j]]) swap(hp[i],hp[j]),swap(id[hp[i]],id[hp[j]]); else break; }return;}void dijkstra(){ for(int i=1;i<=n;++i) ln[i]=INF; ln[s]=0;ins(s); while(hp[0]){ int nw=hp[1];pop(); for(int i=h[nw];i;i=a[i].li){ if(ln[a[i].nx]>ln[nw]+a[i].ln){ ln[a[i].nx]=ln[nw]+a[i].ln; if(!id[a[i].nx]) ins(a[i].nx); else up(id[a[i].nx]); } } }return;}int main(){ n=read(),m=read(),s=read(); for(int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); add(x,y,z); }dijkstra(); for(int i=1;i<=n;++i) printf("%d ",ln[i]); return 0;} 高精度（压9位）
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e4+5;const int MOD=1e9;const int siz=9;char ch[2][MAXN];long long num[6][MAXN];void slv(int id){ int ln=strlen(ch[id]); for(int i=ln-1;i+1>=siz;i-=siz){ ++num[id][0]; for(int j=i-siz+1;j<=i;++j) num[id][num[id][0]]=(num[id][num[id][0]]<<3)+(num[id][num[id][0]]<<1)+(ch[id][j]^'0'); }if(ln%siz){ ++num[id][0]; for(int i=0;i num[id2][0]) return 1; if(num[id1][0] num[id2][i]) return 1; if(num[id1][i] =MOD) ++num[id][i+1],num[id][i]-=MOD; }if(num[id][num[id][0]+1]) ++num[id][0]; return;}void ry(int id){ for(int i=1;i<=num[id][0];++i){ if(num[id][i]&1&&i>1) num[id][i-1]+=MOD>>1; num[id][i]>>=1; }if(!num[id][num[id][0]]&&num[id][0]>1) --num[id][0]; return;}void pls(int id1,int id2,int id3){ num[id3][0]=max(num[id1][0],num[id2][0])+1; for(int i=1;i<=num[id3][0];++i){ num[id3][i]+=num[id1][i]+num[id2][i]; if(num[id3][i]>=MOD) ++num[id3][i+1],num[id3][i]-=MOD; }if(!num[id3][num[id3][0]]&&num[id3][0]>1) --num[id3][0]; return;}void mnu(int id1,int id2,int id3){ num[id3][0]=max(num[id1][0],num[id2][0]); if(cmp(id1,id2)==-1) putchar('-'),swap(id1,id2); for(int i=1;i<=num[id3][0];++i){ num[id3][i]+=num[id1][i]-num[id2][i]; if(num[id3][i]<0) --num[id3][i+1],num[id3][i]+=MOD; }while(!num[id3][num[id3][0]]&&num[id3][0]>1) --num[id3][0]; return;}void mul(int id1,int id2,int id3){ num[id3][0]=num[id1][0]+num[id2][0]; for(int i=1;i<=num[id1][0];++i){ for(int j=1;j<=num[id2][0];++j){ num[id3][i+j-1]+=num[id1][i]*num[id2][j]; if(num[id3][i+j-1]>=MOD) num[id3][i+j]+=num[id3][i+j-1]/MOD,num[id3][i+j-1]%=MOD; } }while(!num[id3][num[id3][0]]&&num[id3][0]>1) --num[id3][0]; return;}void div(int id1,int id2,int id3,int id4,int ck,int rk){ num[ck][0]=num[ck][1]=1; while(cmp(id1,id2)>0){ly(id2),ly(ck);} while(num[ck][0]>1||num[ck][1]){ if(cmp(id1,id2)>=0){ clear(id4);mnu(id1,id2,id4);cpy(id1,id4); clear(rk);pls(id3,ck,rk);cpy(id3,rk); }ry(id2),ry(ck); }return;}int main(){ init(); pls(0,1,2);write(2);clear(2); mnu(0,1,2);write(2);clear(2); mul(0,1,2);write(2);clear(2);clear(3); div(0,1,2,3,4,5);write(2);write(0); return 0;} Gauss
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=105;const double eps=1e-8;int n;struct matrix{ double val[MAXN][MAXN]; bool fl1,fl2; double fabs(double x){return x>-eps?x:-x;} void Gauss() { for(int i=1;i<=n;++i){ int p=i; for(int j=i+1;j<=n;++j) if(fabs(val[j][i])>fabs(val[p][i])) p=j; swap(val[i],val[p]);if(fabs(val[i][i]) n+1) fl2=1; }return; } void write() { if(fl1){puts("-1");return;} if(fl2){puts("0");return;} for(int i=1;i<=n;++i){ if(fabs(val[i][n+1]) ST
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e5+5;int n,m;int ST[17][MAXN];int log[MAXN];int query(int l,int r){return max(ST[log[r-l+1]][l],ST[log[r-l+1]][r-(1< >log[i]+1) ++log[i]; }for(int i=1;i<=log[n];++i){ for(int j=1;j<=n-(1< Trie
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXL=505;const int MAXN=2005;int n,m,siz;char ch[MAXN];struct rpg{ int sn[80]; int vis;}Trie[MAXN*MAXL];void ins(char *ch){ int nw=0,ln=strlen(ch); for(int i=0;i 缩点+DAG上DP
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"bitset"using namespace std;const int MAXN=1e4+5;const int MAXM=1e5+5;int n,m,np,ans;int h[MAXN],siz[MAXN],clr[MAXN],rsiz[MAXN];int stk[MAXN],low[MAXN],dfn[MAXN],q[MAXN],idg[MAXN];int x[MAXM],y[MAXM];bitset vis;struct rpg{ int li,nx;}a[MAXM];void add(int ls,int nx){a[++np]=(rpg){h[ls],nx};h[ls]=np;}void Tarjan(int x){ low[x]=dfn[x]=++dfn[0]; stk[++stk[0]]=x;vis[x]=1; for(int i=h[x];i;i=a[i].li){ if(!dfn[a[i].nx]) Tarjan(a[i].nx),low[x]=min(low[x],low[a[i].nx]); else if(vis[a[i].nx]) low[x]=min(low[x],dfn[a[i].nx]); }if(dfn[x]==low[x]){ clr[x]=++clr[0];vis[x]=0;rsiz[clr[x]]=siz[x]; while(stk[stk[0]]!=x){ clr[stk[stk[0]]]=clr[x]; rsiz[clr[x]]+=siz[stk[stk[0]]]; vis[stk[stk[0]--]]=0; }--stk[0]; }return;}void Torp(){ int hd=1,tl=0; for(int i=1;i<=clr[0];++i) if(!idg[i]) q[++tl]=i,siz[i]=rsiz[i]; while(hd<=tl){ int nw=q[hd++];ans=max(ans,siz[nw]); for(int i=h[nw];i;i=a[i].li){ siz[a[i].nx]=max(siz[a[i].nx],siz[nw]+rsiz[a[i].nx]); if(!--idg[a[i].nx]) q[++tl]=a[i].nx; } }return;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&siz[i]); for(int i=1;i<=m;++i){scanf("%d%d",&x[i],&y[i]);add(x[i],y[i]);} for(int i=1;i<=n;++i) if(!clr[i]) Tarjan(i); memset(h,0,sizeof(h));np=0;memset(siz,0,sizeof(siz)); for(int i=1;i<=m;++i) if(clr[x[i]]!=clr[y[i]]) add(clr[x[i]],clr[y[i]]),++idg[clr[y[i]]]; Torp();printf("%d\n",ans); return 0;}
割点
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"bitset"using namespace std;const int MAXN=1e5+5;int n,m,np,cnt;int h[MAXN],stk[MAXN],dfn[MAXN],low[MAXN],ans[MAXN];bitset cut;struct rpg{ int li,nx;}a[MAXN<<1];void add(int ls,int nx){ a[++np]=(rpg){h[ls],nx};h[ls]=np; a[++np]=(rpg){h[nx],ls};h[nx]=np;}void Tarjan(int x,int root){ low[x]=dfn[x]=++dfn[0]; for(int i=h[x];i;i=a[i].li){ if(!dfn[a[i].nx]){ Tarjan(a[i].nx,root);low[x]=min(low[x],low[a[i].nx]); if(low[a[i].nx]>=dfn[x]&&x!=root) cut[x]=1; if(x==root) ++cnt; }else low[x]=min(low[x],dfn[a[i].nx]); }if(x==root&&cnt>=2) cut[x]=1;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);add(x,y);} for(int i=1;i<=n;++i) if(!dfn[i]) cnt=0,Tarjan(i,i); for(int i=1;i<=n;++i) if(cut[i]) ans[++ans[0]]=i;printf("%d\n",ans[0]); sort(ans+1,ans+ans[0]+1);for(int i=1;i<=ans[0];++i) printf("%d ",ans[i]); return 0;}
二维凸包
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"cmath"using namespace std;const int MAXN=10005;int n;int stk[2][MAXN];double ans;struct rpg{ double x,y;}a[MAXN];bool cmp(rpg a,rpg b){return a.x==b.x?a.y 1&&check(stk[0][stk[0][0]-1],stk[0][stk[0][0]],i)) --stk[0][0]; stk[0][++stk[0][0]]=i; }for(int i=1;i<=n;++i){ while(stk[1][0]>1&&!check(stk[1][stk[1][0]-1],stk[1][stk[1][0]],i)) --stk[1][0]; stk[1][++stk[1][0]]=i; }for(int i=1;i AC自动机
#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=1e6+5;const int siz=26;int n,cnt;long long ans;int q[MAXN];char ch[MAXN];struct Trie{ int vis,fail; int sn[siz];}T[MAXN];void ins(char *ch){ int nw=0,ln=strlen(ch+1); for(int i=1;i<=ln;++i){ if(!T[nw].sn[ch[i]-'a']) T[nw].sn[ch[i]-'a']=++cnt; nw=T[nw].sn[ch[i]-'a']; }++T[nw].vis; return;}void Getfail(){ int hd=1,tl=0; for(int i=0;i<26;++i) if(T[0].sn[i]) q[++tl]=T[0].sn[i]; while(hd<=tl){ int nw=q[hd++]; for(int i=0;i<26;++i){ if(T[nw].sn[i]){ T[T[nw].sn[i]].fail=T[T[nw].fail].sn[i]; q[++tl]=T[nw].sn[i]; }else T[nw].sn[i]=T[T[nw].fail].sn[i]; } }return;}void query(char *ch){ int ln=strlen(ch+1),nw=0; for(int i=1;i<=ln;++i){ nw=T[nw].sn[ch[i]-'a']; for(int j=nw;j&&T[j].vis!=-1;j=T[j].fail) ans+=T[j].vis,T[j].vis=-1; }return;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%s",ch+1),ins(ch); Getfail();scanf("%s",ch+1); query(ch);printf("%lld\n",ans); return 0;} LCT
bool nrt(int x) {return sn[0][f[x]]==x||sn[1][x]==x;}void pushup(int x);void pushtag(int x) {swap(sn[0][x],sn[1][x]);tag[x]^=1;}void pushdown(int x) {if(tag[x]) pushtag(sn[0][x]),pushtag(sn[1][x]),tag[x]=0;}void psd(int x) {if(nrt(x)) psd(f[x]);pushdown(x);}bool gsn(int x) {return sn[1][f[x]]==x;}void ro(int x){ int y=f[x],z=f[y],k=gsn(x),w=sn[!k][x]; if(nrt(y)) sn[gsn(y)][z]=x;sn[!k][x]=y,sn[k][y]=w; if(w) f[w]=y;f[y]=x,f[x]=z,pushup(y); return;}void splay(int x) {psd(x);while(nrt(x)){if(nrt(f[x])) ro(gsn(x)^gsn(f[x])?x:f[x]);ro(x);}pushup(x);}void acs(int x) {for(int y=0;x;x=f[y=x]) splay(x),sn[1][x]=y,pushup(x);}void mkrt(int x) {acs(x),splay(x),pushtag(x);}int fdrt(int x) {acs(x),splay(x);while(sn[0][x]) pushdown(x),x=sn[0][x];splay(x);return x;}void split(int x,int y) {mkrt(x),acs(y),splay(y);}void link(int x,int y) {mkrt(x);if(fdrt(y)!=x) f[x]=y;}void cut(int x,int y) {mkrt(x);if(fdrt(y)==x&&f[y]==x&&!sn[0][y]) f[y]=sn[1][x]=0,pushup(x);}