I Am Me
눈덩이처럼 불어나는 근심에도 숨 쉬지 난
I can breathe, I won’t die
If I die 슬퍼하지마 눈물 흘리지마
그 순간에도 미소가
떠오른다
떠오른다
"Cause I am me"
바보 멍청이
"Cause I am free"
바보 멍청이
여도 삶의 주인공은 나인걸
——GOT7
kmp
洛谷3375
#include<bits/stdc++.h> using namespace std; #define N 1000100 char a[N],b[N]; int n,m,fail[N]; int main() { scanf("%s%s",b+1,a+1); n=strlen(a+1); for(int i=2,j=0;i<=n;i++) { while(j>0&&a[i]!=a[j+1])j=fail[j]; if(a[i]==a[j+1])j++; fail[i]=j; } m=strlen(b+1); for(int i=1,j=0;i<=m;i++) { while(j>0&&(j==n||b[i]!=a[j+1]))j=fail[j]; if(b[i]==a[j+1])j++; if(j==n) { printf("%d ",i-n+1); j=fail[j]; } } for(int i=1;i<=n;i++)printf("%d ",fail[i]); return 0; }
堆优化dijkstra
洛谷4779
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define N 100100 typedef pair<ll,ll>pii; ll n,m,s,cnt,ans; ll d[N],vis[N],first[N]; struct email { ll u,v,w; ll nxt; }e[N*4]; inline void add(ll u,ll v,ll w) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v;e[cnt].w=w; } priority_queue<pii>q; void dijkstra(ll s) { memset(vis,0,sizeof(vis)); memset(d,0x3f,sizeof(d)); d[s]=0; q.push(mp(-d[s],s)); while(!q.empty()) { pii x=q.top();q.pop(); ll u=x.second,now=x.first; if(vis[u])continue;vis[u]=1; for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v,w=e[i].w; if(d[v]>d[u]+w) { d[v]=d[u]+w; q.push(mp(-d[v],v)); } } } } int main() { scanf("%lld%lld%lld",&n,&m,&s); for(ll i=1;i<=m;i++) { ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); } dijkstra(s); for(ll i=1;i<=n;i++)printf("%lld ",d[i]); return 0; }
快速幂
洛谷1226
#include<bits/stdc++.h> using namespace std; #define ll long long ll a,b,mod; inline ll ksm(ll a,ll b) { ll ret=1,tmp=b; while(b) { if(b&1)ret=(ret*a)%mod; a=(a*a)%mod; b>>=1; } return (tmp!=0)?ret:0; } int main() { cin>>a>>b>>mod; cout<<a<<"^"<<b<<" mod "<<mod<<"="<<ksm(a,b); }
矩阵快速幂
洛谷3390
#include<bits/stdc++.h> using namespace std; #define N 110 #define ll long long #define mod 1000000007 ll n,k; struct email { ll x[N][N]; }a,ans; inline email mul(email a,email b) { email c; memset(c.x,0,sizeof(c.x)); for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) for(ll k=1;k<=n;k++) c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%mod; return c; } inline email ksm(email a,ll k) { if(k==1)return a; email b=ksm(a,k/2); b=mul(b,b); if(k&1)b=mul(b,a); return b; } int main() { scanf("%lld%lld",&n,&k); for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) scanf("%lld",&a.x[i][j]); ans=ksm(a,k); for(ll i=1;i<=n;i++) { for(ll j=1;j<=n;j++) printf("%lld ",ans.x[i][j]); printf(" "); } }
并查集
洛谷3367
#include<bits/stdc++.h> using namespace std; #define N 10010 int n,m; int fa[N]; inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void combine(int x,int y){fa[find(x)]=find(y);} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1)combine(x,y); else { if(find(x)==find(y))puts("Y"); else puts("N"); } } return 0; }
Kruskal
洛谷3366
#include<bits/stdc++.h> using namespace std; #define N 10010 int n,m,cnt,tot,ans; int fa[N]; struct email { int u,v,w; }e[N*40]; inline void add(int u,int v,int w){e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w;} inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void combine(int x,int y){fa[find(x)]=find(y);} bool cmp(email a,email b){return a.w<b.w;} void kruskal() { for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,w=e[i].w,fax=find(u),fay=find(v); if(fax!=fay)fa[fax]=fay,++tot,ans+=w; if(tot==n-1)break; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } sort(e+1,e+1+m,cmp); kruskal(); if(tot!=n-1)puts("orz"); else printf("%d",ans); return 0; }
割点
洛谷3388
#include<bits/stdc++.h> using namespace std; #define N 50050 int n,m,cnt,tot,ans,root,child; int dfn[N],low[N],cut[N],first[N]; struct email { int u,v; int nxt; }e[N*4]; inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } inline void tarjan(int u,int fa) { dfn[u]=low[u]=++tot;child=0; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa)continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]&&u!=root) cut[u]=1; if(u==root) child++; } else low[u]=min(low[u],dfn[v]); } if(u==root&&child>1)cut[u]=1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i,i); for(int i=1;i<=n;i++)ans+=cut[i]; printf("%d ",ans); for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i); return 0; }
割边
#include<bits/stdc++.h> using namespace std; #define N 50050 int n,m,cnt,tot,ans,cot; int dfn[N],low[N],first[N]; struct email { int u,v; int nxt; }e[N*4],cut[N*4]; inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } inline void tarjan(int u,int fa) { dfn[u]=low[u]=++tot; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa)continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u])cut[++cot]=e[i]; } else low[u]=min(low[u],dfn[v]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i); for(int i=1;i<=cot;i++) { int u=cut[i].u,v=cut[i].v; printf("%d-->%d ",u,v); } return 0; }
缩点
#include<bits/stdc++.h> using namespace std; #define N 50050 int n,m,cnt,tot,ans,gro; int dfn[N],low[N],col[N],siz[N],vis[N],first[N]; stack<int>s; struct email { int u,v; int nxt; }e[N*4]; inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } inline void tarjan(int u) { dfn[u]=low[u]=++tot; s.push(u);vis[u]=1; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ++gro; while(1) { int t=s.top();s.pop();vis[t]=0; col[t]=gro;siz[gro]++; if(t==u)break; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) printf("%d ",col[i]); return 0; }
Floyd
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
逆元
#include<bits/stdc++.h> using namespace std; #define N 3000030 #define ll long long ll b,mod; ll inv[N]; int main() { scanf("%lld%lld",&b,&mod); inv[1]=1; for(ll i=2;i<=b;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(ll i=1;i<=b;i++) printf("%lld ",inv[i]); return 0; }
exgcd
#include<bits/stdc++.h> using namespace std; int b,x,y,mod,gcd; inline int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int ret=exgcd(b,a%b,x,y); int t=x;x=y,y=t-(a/b)*y; return ret; } int main() { cin>>b>>mod; gcd=exgcd(b,mod,x,y); if(gcd!=1)printf("not exist "); else printf("%d ",(x%mod+mod)%mod); return 0; }
线性筛
#include<bits/stdc++.h> using namespace std; #define N 10000010 int n,m,cnt; int prime[N],v[N]; void primes(int n) { for(int i=2;i<=n;i++) { if(!v[i]) { v[i]=i; prime[++cnt]=i; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n||prime[j]>i)break; v[prime[j]*i]=prime[j]; } } } int main() { scanf("%d%d",&n,&m); primes(n); while(m--) { int x; scanf("%d",&x); if(v[x]==x)printf("Yes "); else printf("No "); } return 0; }
欧拉函数
#include<bits/stdc++.h> using namespace std; #define N 10000010 int n,m,cnt; int prime[N],phi[N],v[N]; void primes(int n) { for(int i=2;i<=n;i++) { if(!v[i]) { v[i]=i; prime[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n||prime[j]>i)break; v[prime[j]*i]=prime[j]; phi[i*prime[j]]=phi[i]*((i%prime[j])?(prime[j]-1):prime[j]); } } } int main() { scanf("%d",&n); primes(n); for(int i=1;i<=n;i++)printf("%d ",phi[i]); return 0; }
埃拉托色尼筛
#include<bits/stdc++.h> using namespace std; #define N 1000010 int n,m,cnt; int prime[N],v[N]; void primes(int n) { for(int i=2;i<=n;i++) { if(!v[i]) { prime[++cnt]=i; for(int j=i*i;j<=n;j+=i) v[j]=1; } } } int main() { scanf("%d",&n); primes(n); for(int i=1;i<=cnt;i++)printf("%d ",prime[i]); return 0; }
中国剩余定理
#include<bits/stdc++.h> using namespace std; #define N 20 #define ll long long ll n,x,y,ans; ll a[N],m[N]; inline ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll ret=exgcd(b,a%b,x,y); ll t=x;x=y,y=t-(a/b)*y; return ret; } inline ll CRT(ll a[],ll m[],ll n) { ll ans=0,M=1; for(ll i=1;i<=n;i++)M*=m[i]; for(ll i=1;i<=n;i++) { ll Mi=M/m[i]; exgcd(Mi,m[i],x,y); ans=(ans+x*a[i]*Mi)%M; } if(ans<0)ans+=M; return ans; } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++)scanf("%lld%lld",&m[i],&a[i]); ans=CRT(a,m,n); printf("%lld ",ans); return 0; }
扩展中国剩余定理
#include<bits/stdc++.h> using namespace std; #define N 1000010 #define ll long long ll n,x,y,ans,flag; ll c[N],m[N]; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll ret=exgcd(b,a%b,x,y); ll t=x;x=y,y=t-(a/b)*y; return ret; } inline ll inv(ll a,ll b){ll tmp=exgcd(a,b,x,y);return x=(x%b+b)%b;} int main() { while(scanf("%lld",&n)==1) { for(ll i=1;i<=n;i++)scanf("%lld%lld",&m[i],&c[i]); flag=1; for(ll i=2;i<=n;i++) { ll c1=c[i-1],m1=m[i-1],c2=c[i],m2=m[i],d=gcd(m1,m2); if((c2-c1)%d){flag=0;break;} m[i]=(m1*m2)/d; c[i]=(inv(m1/d,m2/d)*(c2-c1)/d)%(m2/d)*m1+c1; c[i]=(c[i]%m[i]+m[i])%m[i]; } printf("%lld ",flag?c[n]:-1); } return 0; }
LCA
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 10100 int n,t,x,y,cnt,root; int first[N],in[N],dep[N]; int fa[N][20]; struct email { int u,v; int nxt; }e[N*4]; inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } void dfs(int u,int f) { for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==f)continue; fa[v][0]=u; dep[v]=dep[u]+1; dfs(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); int k=dep[x]-dep[y]; for(int i=0;(1<<i)<=k;i++) if(k&(1<<i)) x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } inline void init() { memset(in,0,sizeof(in)); memset(dep,0,sizeof(dep)); memset(first,0,sizeof(first)); memset(fa,0,sizeof(fa)); cnt=0; } int main() { scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u);in[v]++; } for(int i=1;i<=n;i++) if(!in[i]) {root=i;break;} dfs(root,0); scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } }
树的直径
inline void dfs(int u,int fa) { for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if(v==fa)continue; d[v]=d[u]+w; dfs(v,u); } } int main() { ... memset(d,0x3f,sizeof(d)); d[x]=0; dfs(x,x); for(int i=1;i<=n;i++) if(maxx<d[i]) maxx=d[i],p=i; memset(d,0x3f,sizeof(d)); d[p]=0; dfs(p,p); for(int i=1;i<=n;i++) dia=max(dia,d[i]); ... }
线段树
区间加
#include<bits/stdc++.h> using namespace std; #define N 100100 #define lc (p<<1) #define rc (p<<1|1) #define ll long long #define mid (t[p].l+t[p].r>>1) ll n,m; ll a[N]; struct email { ll l,r,sum,lazy; }t[N*4]; inline void pushnow(ll p,ll v) { t[p].lazy+=v; t[p].sum+=(t[p].r-t[p].l+1)*v; } inline void pushup(ll p) { t[p].sum=t[lc].sum+t[rc].sum; } inline void pushdown(ll p) { if(t[p].lazy) { pushnow(lc,t[p].lazy); pushnow(rc,t[p].lazy); t[p].lazy=0; } } inline void build(ll p,ll l,ll r) { t[p].l=l,t[p].r=r; if(l==r) { t[p].sum=a[l]; return ; } ll bm=l+r>>1; build(lc,l,bm);build(rc,bm+1,r); pushup(p); } inline void update(ll p,ll ql,ll qr,ll v) { if(ql<=t[p].l&&qr>=t[p].r) { pushnow(p,v); return ; } pushdown(p); if(ql<=mid)update(lc,ql,qr,v); if(qr>mid)update(rc,ql,qr,v); pushup(p); } inline ll query(ll p,ll ql,ll qr) { ll ret=0; if(ql<=t[p].l&&qr>=t[p].r) return t[p].sum; pushdown(p); if(ql<=mid)ret+=query(lc,ql,qr); if(qr>mid)ret+=query(rc,ql,qr); return ret; } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); for(ll i=1;i<=m;i++) { ll op,x,y,k; scanf("%lld%lld%lld",&op,&x,&y); if(op==1) { scanf("%lld",&k); update(1,x,y,k); } else printf("%lld ",query(1,x,y)); } }
区间乘和区间加
维护两个lazy标记，优先更新乘法标记
#include<bits/stdc++.h> using namespace std; #define N 100100 #define lc (p<<1) #define rc (p<<1|1) #define ll long long #define mid (t[p].l+t[p].r>>1) ll n,m,mod; ll a[N]; struct email { ll l,r,sum,mul,add; }t[N*4]; inline void pushmul(ll p,ll v) { t[p].sum=(t[p].sum*v)%mod; t[p].add=(t[p].add*v)%mod; t[p].mul=(t[p].mul*v)%mod; } inline void pushadd(ll p,ll v) { t[p].add+=v;t[p].add%=mod; t[p].sum+=(t[p].r-t[p].l+1)*v%mod; } inline void pushup(ll p) { t[p].sum=(t[lc].sum+t[rc].sum)%mod; } inline void pushdown(ll p) { if(t[p].mul!=1) { pushmul(lc,t[p].mul); pushmul(rc,t[p].mul); t[p].mul=1; } if(t[p].add) { pushadd(lc,t[p].add); pushadd(rc,t[p].add); t[p].add=0; } } inline void build(ll p,ll l,ll r) { t[p].l=l,t[p].r=r;t[p].mul=1; if(l==r) { t[p].sum=a[l]; return ; } ll bm=l+r>>1; build(lc,l,bm);build(rc,bm+1,r); t[p].sum%=mod; pushup(p); } inline void update(ll p,ll ql,ll qr,ll v) { if(ql<=t[p].l&&qr>=t[p].r) { pushadd(p,v); return ; } pushdown(p); if(ql<=mid)update(lc,ql,qr,v); if(qr>mid)update(rc,ql,qr,v); pushup(p); } inline void update1(ll p,ll ql,ll qr,ll v) { if(ql<=t[p].l&&qr>=t[p].r) { pushmul(p,v); return ; } pushdown(p); if(ql<=mid)update1(lc,ql,qr,v); if(qr>mid)update1(rc,ql,qr,v); pushup(p); } inline ll query(ll p,ll ql,ll qr) { ll ret=0; if(ql<=t[p].l&&qr>=t[p].r) return t[p].sum; pushdown(p); if(ql<=mid)ret=(ret+query(lc,ql,qr))%mod; if(qr>mid)ret=(ret+query(rc,ql,qr))%mod; return ret; } int main() { scanf("%lld%lld%lld",&n,&m,&mod); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); for(ll i=1;i<=m;i++) { ll op,x,y,k; scanf("%lld%lld%lld",&op,&x,&y); if(op==1) { scanf("%lld",&k); update1(1,x,y,k); } else if(op==2) { scanf("%lld",&k); update(1,x,y,k); } else printf("%lld ",query(1,x,y)); } }
树链剖分
#include<bits/stdc++.h> using namespace std; #define N 100100 #define lc (p<<1) #define rc (p<<1|1) #define ll long long #define mid (t[p].l+t[p].r>>1) ll n,m,cnt,tot,mod,root; ll a[N],d[N],f[N],rk[N],id[N],top[N],siz[N],son[N],first[N]; struct email { ll u,v; ll nxt; }e[N*4]; struct tree { ll l,r,sum,lazy; }t[N*4]; inline void add(ll u,ll v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } inline void pushnow(ll p,ll v) { t[p].lazy+=v; t[p].sum=t[p].sum+(t[p].r-t[p].l+1)*v%mod; } inline void pushup(ll p) { t[p].sum=(t[lc].sum+t[rc].sum)%mod; } inline void pushdown(ll p) { if(t[p].lazy) { pushnow(lc,t[p].lazy); pushnow(rc,t[p].lazy); t[p].lazy=0; } } inline void build(ll p,ll l,ll r) { t[p].l=l,t[p].r=r; if(l==r) { t[p].sum=a[rk[l]]; return ; } ll bm=l+r>>1; build(lc,l,bm);build(rc,bm+1,r); pushup(p); } inline void update(ll p,ll ql,ll qr,ll v) { if(ql<=t[p].l&&qr>=t[p].r) { pushnow(p,v); return ; } pushdown(p); if(ql<=mid)update(lc,ql,qr,v); if(qr>mid)update(rc,ql,qr,v); pushup(p); } inline ll query(ll p,ll ql,ll qr) { ll ret=0; if(ql<=t[p].l&&qr>=t[p].r) return t[p].sum; pushdown(p); if(ql<=mid)ret=(ret+query(lc,ql,qr))%mod; if(qr>mid)ret=(ret+query(rc,ql,qr))%mod; return ret; } inline void dfs(ll u,ll fa,ll dep) { d[u]=dep;f[u]=fa;siz[u]=1; for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v; if(v==fa)continue; dfs(v,u,dep+1); siz[u]+=siz[v]; if(!son[u]||siz[v]>siz[son[u]]) son[u]=v; } } inline void dfs2(ll u,ll t) { top[u]=t;id[u]=++tot;rk[tot]=u; if(son[u]==0)return; dfs2(son[u],t); for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v; if(v!=f[u]&&v!=son[u]) dfs2(v,v); } } inline void updtree(ll x,ll y,ll v) { ll fx=top[x],fy=top[y]; while(fx!=fy) { if(d[fx]>d[fy]) { update(1,id[fx],id[x],v); x=f[fx],fx=top[x]; } else { update(1,id[fy],id[y],v); y=f[fy],fy=top[y]; } } if(id[x]<=id[y])update(1,id[x],id[y],v); else update(1,id[y],id[x],v); } inline ll asktree(ll x,ll y) { ll fx=top[x],fy=top[y],ret=0; while(fx!=fy) { if(d[fx]>d[fy]) { ret+=query(1,id[fx],id[x]);ret%=mod; x=f[fx],fx=top[x]; } else { ret+=query(1,id[fy],id[y]);ret%=mod; y=f[fy],fy=top[y]; } } if(id[x]<=id[y])ret+=query(1,id[x],id[y]),ret%=mod; else ret+=query(1,id[y],id[x]),ret%=mod; return ret%mod; } int main() { scanf("%lld%lld%lld%lld",&n,&m,&root,&mod); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); for(ll i=1;i<n;i++) { ll u,v; scanf("%lld%lld",&u,&v); add(u,v);add(v,u); } dfs(root,0,1);dfs2(root,root);build(1,1,n); for(ll i=1;i<=m;i++) { ll op,x,y,k; scanf("%lld%lld",&op,&x); if(op==1) scanf("%lld%lld",&y,&k),updtree(x,y,k); if(op==2) scanf("%lld",&y),printf("%lld ",asktree(x,y)); if(op==3) scanf("%lld",&k),update(1,id[x],id[x]+siz[x]-1,k); if(op==4) printf("%lld ",query(1,id[x],id[x]+siz[x]-1)); } return 0; }
单调队列
#include<bits/stdc++.h> using namespace std; #define N 1000005 int n,t,h,ans; int q[N],L[N],R[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&L[i],&R[i]); t=h=1;q[t++]=1;ans=1; for(int i=1;i<=n;i++) { while(h<t&&L[q[t-1]]<L[i])t--; q[t++]=i; while(h<t&&L[q[h]]>R[i])h++; ans=max(ans,i-(q[h-1]+1)+1); } printf("%d ",ans); return 0; }
树状数组
#include<bits/stdc++.h> using namespace std; #define N 500050 int n,m; int a[N],c[N]; inline int lowbit(int x){return x&(-x);} inline void update(int x,int y) { for(;x<=n;x+=lowbit(x)) c[x]+=y; } inline int query(int x) { int ret=0; for(;x;x-=lowbit(x)) ret+=c[x]; return ret; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int op,x,y,z; scanf("%d",&op); if(op==1) { scanf("%d%d%d",&x,&y,&z); update(x,z),update(y+1,-z); } else { scanf("%d",&x); printf("%d ",query(x)+a[x]); } } }
二维树状数组
inline int lowbit(int x){return x&(-x);} inline void update(int x,int y,int v) { for(;x<=n;x+=lowbit(x)) for(;y<=n;y+=lowbit(y)) c[x][y]+=v; } inline int query(int x,int y) { int ret=0; for(;x;x-=lowbit(x)) for(;y;y-=lowbit(y)) ret+=c[x][y]; return ret; }
匈牙利算法
#include<bits/stdc++.h> using namespace std; #define N 1010 int n,m,e,ans; int ok[N][N],match[N],ask[N]; inline int find(int x) { for(int i=1;i<=m;i++) { if(ok[x][i]) { if(ask[i])continue; ask[i]=1; if(!match[i]||find(match[i])) { match[i]=x; return 1; } } } return 0; } int main() { scanf("%d%d%d",&n,&m,&e); for(int i=1;i<=e;i++) { int x,y; scanf("%d%d",&x,&y); ok[x][y]=1; } for(int i=1;i<=n;i++) { memset(ask,0,sizeof(ask)); if(find(i))ans++; } printf("%d",ans); return 0; }
字符串hash
luogu3370
背这个long long级别的大质数既不那么容易被卡，时间也很省
#include<bits/stdc++.h> using namespace std; #define N 10010 #define base 131 #define ull unsigned long long #define mod 212370440130137957 int n,ans=0; ull a[N]; char s[N]; ull hash(char s[]) { int len=strlen(s); ull ret=0; for(int i=0;i<len;i++) ret=(ret*base+(ull)s[i])%mod; return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s); a[i]=hash(s); } sort(a+1,a+1+n); ans=unique(a+1,a+1+n)-(a+1); printf("%d ",ans); return 0; }
三分
#include<bits/stdc++.h> using namespace std; #define N 20 #define db double #define eps 1e-6 int n; db l,r,lmid,rmid,num[N]; inline db f(db x) { db ret=0; for(int i=n;i>=0;i--) ret+=num[i]*pow(x,i); return ret; } int main() { scanf("%d%lf%lf",&n,&l,&r); for(int i=n;i>=0;i--)scanf("%lf",&num[i]); while(r-l>eps) { lmid=l+(r-l)/3; rmid=r-(r-l)/3; if(f(lmid)<f(rmid))l=lmid; else r=rmid; } printf("%.5lf",r); return 0; }
Manacher
#include<bits/stdc++.h> using namespace std; #define N 30000300 int p[N]; int len,ans=1,mid=1,mx=1; char s[N],pre[N]; void add() { int i=1,j=0;len=strlen(pre+1); s[j]='~';s[++j]='*'; while(i<=len)s[++j]=pre[i++],s[++j]='*'; len=j; } int main() { scanf("%s",pre+1); add(); for(int i=1;i<len;i++) { if(i<mx)p[i]=min(mx-i,p[2*mid-i]); else p[i]=1; while(s[i-p[i]]==s[i+p[i]])p[i]++; if(mx<i+p[i])mx=i+p[i],mid=i; ans=max(ans,p[i]-1); } printf("%d ",ans); return 0; }
树上差分
#include<bits/stdc++.h> using namespace std; #define N 50050 int n,k,cnt,ans; int c[N],dep[N],first[N],fa[N][20]; struct email { int u,v; int nxt; }e[N*4]; void dfs(int u,int f) { for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==f)continue; fa[v][0]=u; dep[v]=dep[u]+1; dfs(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); int k=dep[x]-dep[y]; for(int i=0;(1<<i)<=k;i++) if(k&(1<<i)) x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } inline void dfs2(int u,int f) { for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==f)continue; dfs2(v,u); c[u]+=c[v]; } ans=max(ans,c[u]); } int main() { scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); for(int i=1;i<=k;i++) { int u,v; scanf("%d%d",&u,&v); c[u]++,c[v]++,c[lca(u,v)]--,c[fa[lca(u,v)][0]]--; } dfs2(1,0); printf("%d ",ans); return 0; }
分块
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define N 100010 #define ll long long ll n,m; char op[3]; ll a[N],sum[N],add[N],L[N],R[N],pos[N]; void update(ll l,ll r,ll v) { ll p=pos[l],q=pos[r]; if(p==q) { for(ll i=l;i<=r;i++)a[i]+=v; sum[p]+=v*(r-l+1); } else { for(ll i=p+1;i<=q-1;i++)add[i]+=v; for(ll i=l;i<=R[p];i++)a[i]+=v; sum[p]+=v*(R[p]-l+1); for(ll i=L[q];i<=r;i++)a[i]+=v; sum[q]+=v*(r-L[q]+1); } } ll query(ll l,ll r) { ll p=pos[l],q=pos[r],ret=0; if(p==q) { for(ll i=l;i<=r;i++)ret+=a[i]; ret+=add[p]*(r-l+1); } else { for(ll i=p+1;i<=q-1;i++)ret+=sum[i]+(R[i]-L[i]+1)*add[i]; for(ll i=l;i<=R[p];i++)ret+=a[i]; ret+=add[p]*(R[p]-l+1); for(ll i=L[q];i<=r;i++)ret+=a[i]; ret+=add[q]*(r-L[q]+1); } return ret; } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); int t=sqrt(n); for(ll i=1;i<=t;i++)L[i]=(i-1)*t+1,R[i]=i*t; if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n; for(ll i=1;i<=t;i++) for(ll j=L[i];j<=R[i];j++) pos[j]=i,sum[i]+=a[j]; while(m--) { ll l,r,d; scanf("%s%lld%lld",op,&l,&r); if(op[0]=='C')scanf("%lld",&d),update(l,r,d); else printf("%lld ",query(l,r)); } }