Others

模板小记2
模板小记3
模板小记4

dij

// wa 1ci#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define mp(x,y) make_pair((x),(y))
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=5e5+5; 
int n,m,s; 
struct node{int y,z,nt; 
}a[N*2];
int tot,head[N],d[N]; 
bool vis[N]; 
priority_queue<pair<int,int> >q; 
void add(int x,int y,int z){a[++tot]=(node){y,z,head[x]}; head[x]=tot; 
}
void dij(){memset(vis,0,sizeof(vis)); memset(d,0x3f,sizeof(d)); q.push(mp(0,s)); d[s]=0; while (q.size()){int x=q.top().second; q.pop(); if (!vis[x]) vis[x]=1; else continue; for(int i=head[x];i;i=a[i].nt){int y=a[i].y; if (d[y]>d[x]+a[i].z){d[y]=d[x]+a[i].z; q.push(mp(-d[y],y)); // xiao gen dui}}}
}
int main(){scanf("%d%d%d",&n,&m,&s); rep(i,1,m){int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); }dij();rep(i,1,n) printf("%d ",d[i]); return 0; 
}

spfa

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=5e5+5,M=1e4+5; 
int n,m,s; 
struct node{int y,z,nt; 
}a[N*2];
int head[M],tot,d[M]; 
queue<int>q; 
bool vis[M]; 
void add(int x,int y,int z){a[++tot]=(node){y,z,head[x]}; head[x]=tot; 
}	
void spfa(){memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); q.push(s); d[s]=0; vis[s]=1; while (q.size()){int x=q.front(); q.pop(); for(int i=head[x];i;i=a[i].nt){int y=a[i].y; if (d[y]>d[x]+a[i].z){d[y]=d[x]+a[i].z; if (!vis[y]) vis[y]=1,q.push(y); }}vis[x]=0; }
}
int main(){scanf("%d%d%d",&n,&m,&s); int maxn=2147483647; rep(i,1,m){int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } spfa(); //loudiaole rep(i,1,n) if (d[i]==0x3f3f3f3f) printf("%d ",maxn); else printf("%d ",d[i]); return 0; 
}

线性筛PHI

#include<cstdio> 
#include<algorithm>
#include<cstring>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=1e5+5; 
int n,prime[N],v[N],phi[N],m; 
void phi_ask(int k){rep(i,2,k){if (!v[i]) v[i]=i,prime[++m]=i,phi[i]=i-1; rep(j,1,m){if (prime[j]>v[i]||prime[j]>n/i) break; v[i*prime[j]]=prime[j];phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]); }}
}
int main(){scanf("%d",&n); phi_ask(n); phi[1]=1; rep(i,1,n) printf("%d ",v[i]); printf("\n"); rep(i,1,m) printf("%d ",prime[i]); printf("\n"); rep(i,1,n) printf("%d ",phi[i]); return 0; 
}

线性求逆元

#include<cstdio>
#include<algorithm>
using namespace std; 
const int N=1e5+5,mod=1e9+7; 
int f[N]; 
int main(){f[1]=1; for(int i=2;i<=20;i++) f[i]=(mod-mod/i)*f[mod%i]%mod; printf("%d",f[20]); 
}
int q=ksm(n,mod-2); 
for(int i=n-1;i>=1;i--)f[i]=f[i+1]*(i+1)%mod; 

Catalan

$$Catn=\frac{1}{n+1}\ast C_{2n}^n$$

$$=C_{2n}^n-C_{2n}^{n-1}$$

LCA树上差分(小王子)

#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=2e5+5; 
struct node{int y,nt; 
}a[N*2];
int dep[N],f[N][30],W=20,g[N]; 
int head[N],tot; 
int n,m,ans; 
void dfs(int x){for(int i=head[x];i;i=a[i].nt){int y=a[i].y; if (y!=f[x][0]){f[y][0]=x; dep[y]=dep[x]+1; for(int j=1;j<=W;j++) f[y][j]=f[f[y][j-1]][j-1]; dfs(y); }}
}
void add(int x,int y){a[++tot]=(node){y,head[x]}; head[x]=tot; 
}
int get_lca(int x,int y){if (dep[x]<dep[y]) swap(x,y);for(int i=W;i>=0;i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i]; if (x==y) return x; for(int i=W;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; 
}
void dp(int x,int fa){for(int i=head[x];i;i=a[i].nt){int y=a[i].y; if (y==fa) continue; dp(y,x); g[x]+=g[y]; }
}
int main(){scanf("%d%d",&n,&m); rep(i,1,n-1){int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); }dep[1]=1; dfs(1); rep(i,1,m){int x,y; scanf("%d%d",&x,&y); g[x]++,g[y]++,g[get_lca(x,y)]-=2; }dp(1,0); rep(i,2,n) ans+=(g[i]==1)?1:((g[i]==0)?m:0); printf("%lld",ans); return 0; 
}

快速幂

ll ksm(ll x,ll y){ll ans=1;for(;y;y>>=1,(x*=x)%=qh) if (y&1) (ans*=x)%=qh;return ans;
}

最小生成树

#include<cstdio> 
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=2e5+5; 
int n,m,f[N];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
struct node{int x,y,z; 
}a[N*2];
bool cmp(node x,node y){return x.z<y.z; 
}
int main(){scanf("%d%d",&n,&m); rep(i,1,n) f[i]=i; rep(i,1,m) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+m+1,cmp); int cnt=0,ans=0; rep(i,1,m){int x=find(a[i].x),y=find(a[i].y); if (f[x]!=f[y]&&cnt<=m-1){f[y]=x; ans+=a[i].z; cnt++; }if (cnt==n-1) break; }if (cnt==n-1) printf("%d",ans); else printf("orz"); return 0; 
}

对拍

#include<bits/stdc++.h>
using namespace std; 
int main(){double q,w,e; for(int i=1;i<=100;i++){system("data.exe > data.txt"); q=clock(); system("std.exe < data.txt > std.txt"); w=clock(); system("text.exe < data.txt > text.txt"); e=clock(); if (system("fc /W std.txt text.txt >nul")){printf("%d WA\n"); break;} else printf("%d AC\n"); }system("pause>nul"); return 0; 
}

随机数据

#include<bits/stdc++.h>
using namespace std; 
int Q(int x){return 1ll*rand()*rand()%x+1; 
}
int main(){srand((unsigned)time(NULL)); int q=Q(100); printf("%d",q); //随机排列 int a[1005]; for(int i=1;i<=100;i++) a[i]=i; for(int i=1;i<=100;i++) {int x=Q(n),y=Q(n); swap(a[x],a[y]);}//随机连通图/*先随机一条链，然后再添加边 注意去重和自环 */ return 0; 
}

字符串HASH

#include<cstdio>
#include<string>
#include<iostream>
using namespace std; 
const int inf=30001; 
string s,hash[inf]; 
int n,ans; 
int main()
{scanf("%d",&n); for (int i=1;i<=n;i++){cin>>s; int g=0; for(int i=0;i<s.size();i++) g+=s[i];g%=inf;while (hash[g]!=s&&hash[g]!="") g=(g+1)%inf; if (hash[g]=="") hash[g]=s; else ans++;}printf("%d",n-ans);
}

三分

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define db double
using namespace std; 
const db eps=1e-7; 
int n; 
db l,r,mid,a[15]; 
db check(db k){db sum=0; for(int i=n;i>=0;i--) sum=sum*k+a[i]; return sum; 
}
int main(){scanf("%d%lf%lf",&n,&l,&r); for(int i=n;i>=0;i--)scanf("%lf",&a[i]); while(fabs(l-r)>=eps){mid=(l+r)/2; if (check(mid+eps)>check(mid-eps)) l=mid; else r=mid; }printf("%.5lf",r); return 0; 
}

树状数组

单点加，区间查询

#include<cstdio>
#include<algorithm>
using namespace std; 
const int N=5e5+100; 
int n,m,a[N],b[N]; 
void add(int x,int y){for(;x<=n;x+=(x&(-x))) b[x]+=y; 
}
int ask(int x){int cnt=0; for(;x;x-=(x&(-x))) cnt+=b[x]; return cnt; 
}
int main(){scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),add(i,a[i]); for(int i=1;i<=m;i++){int q,x,k; scanf("%d%d%d",&q,&x,&k); if (q==1){add(x,k); } else {printf("%d\n",ask(k)-ask(x-1)); }}return 0; 
}

区间加，单点查询

#include<cstdio> 
#include<algorithm>
using namespace std; 
const int N=5e5+100; 
int a[N],n,m; 
void add(int x,int y){for(;x<=n;x+=(x&(-x))) a[x]+=y; 
}
int ask(int x){int cnt=0; for(;x;x-=(x&(-x))) cnt+=a[x]; return cnt; 
}
int main(){scanf("%d%d",&n,&m); int g=0,x; for(int i=1;i<=n;i++) scanf("%d",&x),add(i,x-g),g=x; for(int i=1;i<=m;i++){int q,x,y,k; scanf("%d",&q); if (q==1){scanf("%d%d%d",&x,&y,&k); add(x,k),add(y+1,-k); } else {scanf("%d",&x); printf("%d\n",ask(x)); }}return 0; 
}

负环

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int inn=100001;  
struct node{ int y,w,next; }a[inn];
int n,m,T,len,t[inn],f[inn],last[inn]; bool b[inn]; 
queue<int>que; 
inline void add(int x,int y,int z){a[++len]=(node){y,z,last[x]}; last[x]=len;
}
inline bool nagetive_ring(){que.push(1); t[1]=1; f[1]=0; while (!que.empty()){int q=que.front(); que.pop(); b[q]=true;for (int i=last[q];~i;i=a[i].next){int s=a[i].y,d=a[i].w; if (f[q]+d<f[s]){f[s]=f[q]+d; t[s]=t[q]+1; if (t[s]>n) return 1;if (!b[s]) b[s]=true,que.push(s); }}b[q]=false; }return 0; 
}	
void spfa(){memset(a,0,sizeof(a)); memset(last,-1,sizeof(last)); memset(f,0x3f3f3f,sizeof(f)); memset(t,0,sizeof(t)); memset(b,0,sizeof(b)); while(!que.empty()) que.pop(); scanf("%d%d",&n,&m); int x,y,z; len=0; for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z); add(x,y,z); if (z>=0) add(y,x,z);}if (nagetive_ring()) printf("YES\n"); else printf("NO\n"); 
}
int main(){scanf("%d",&T); while (T--) spfa(); return 0; 
}

快读快输

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std; 
int read(){int p=0,f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}while (isdigit(c)) p=(p<<3)+(p<<1)+c-48,c=getchar(); return p*f; 
}
void write(int x){if (x>9) write(x/10); putchar(x%10+48); 
}
int main(){int q=read(); write(q); return 0; 
}

线段树

区间加，区间查询

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long 
using namespace std; 
const ll N=1e5+5; 
ll n,m,b[N]; 
struct node{ll sum,add; 
}a[N*4];
void build(ll p,ll l,ll r){if (l==r){a[p].sum=b[l]; a[p].add=0; return; }ll mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); a[p].sum=a[p<<1].sum+a[p<<1|1].sum; 
}
void pushdown(ll p,ll l,ll r){if (a[p].add){ll mid=(l+r)>>1; a[p<<1].sum+=(mid-l+1)*a[p].add; a[p<<1|1].sum+=(r-mid)*a[p].add; //注意(r-mid)a[p<<1].add+=a[p].add; a[p<<1|1].add+=a[p].add;  a[p].add=0; //注意sum不能清零}
}
void add(ll p,ll l,ll r,ll x,ll y,ll z){if (x<=l&&y>=r) {a[p].sum+=(r-l+1)*z; a[p].add+=z; return;}pushdown(p,l,r); ll mid=(l+r)>>1; if (x<=mid) add(p<<1,l,mid,x,y,z); if (y>mid) add(p<<1|1,mid+1,r,x,y,z); a[p].sum=a[p<<1].sum+a[p<<1|1].sum; 
}
ll query(ll p,ll l,ll r,ll x,ll y){if (x<=l&&y>=r){return a[p].sum; }pushdown(p,l,r); ll mid=(l+r)>>1,cnt=0; if (x<=mid) cnt+=query(p<<1,l,mid,x,y); if (y>mid) cnt+=query(p<<1|1,mid+1,r,x,y); return cnt; 
}
int main(){scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) scanf("%lld",&b[i]); build(1,1,n); for(ll i=1;i<=m;i++){ll q,x,y,k; scanf("%lld",&q); if (q==1){scanf("%lld%lld%lld",&x,&y,&k); add(1,1,n,x,y,k); } else {scanf("%lld%lld",&x,&y); printf("%lld\n",query(1,1,n,x,y)); }}return 0; 
}