Hash：
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #define REP(i,k,n) for(long long i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline long long read(){ long long x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } long long ha[100010]; long long n,m,S; char s[100010],t[100010]; long long sum[10010],poww[100010]; long long k=1e9,k1=1e7; int main(){ scanf("%s%s",s+1,t+1); n=strlen(s+1),m=strlen(t+1); poww[0]=1; REP(i,1,n) poww[i]=(poww[i-1]*k)%k1; REP(i,1,n) sum[i]=(sum[i-1]*k+(s[i]-'a'))%k1; REP(i,1,m) S=(S*k+(t[i]-'a'))%k1; REP(i,m,n) if(S%k1==(sum[i]-sum[i-m]*poww[m])%k1) cout<<i<<endl; }
Kmp：
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; char s[100010],t[100010]; int nxt[100010]; void getnxt(){ int j=1; nxt[1]=0; REP(i,2,m){ while(t[i+1]!=t[j+1] && j!=0) j=nxt[j]; if(t[i+1]==t[j+1]) nxt[i+1]=j+1,j++; else nxt[i+1]=0; } } void pipei(){ int j=0; REP(i,0,n){ while(s[i+1]!=t[j+1] && j!=0) j=nxt[j]; if(s[i+1]==t[j+1]) j++; if(j==m) cout<<i<<endl,j=nxt[j]; } } int main(){ scanf("%s%s",s+1,t+1); n=strlen(s+1),m=strlen(t+1); getnxt(); pipei(); }
AC-automata machine:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } queue <int> Q; int n; int tree[100010][30],total=1,isend[100010],nxt[100010]; char t[100010],s[100010]; void insert(char *s){ int l=strlen(s+1),u=1; REP(i,1,l){ if(!tree[u][s[i]-'a']) tree[u][s[i]-'a']=++total; u=tree[u][s[i]-'a']; } isend[u]=1; return ; } void getnxt(){ REP(i,0,25) tree[0][i]=1; Q.push(1),nxt[1]=0; while(!Q.empty()){ int u=Q.front();Q.pop(); REP(i,0,25) if(!tree[u][i]) tree[u][i]=tree[nxt[u]][i]; else nxt[tree[u][i]]=tree[nxt[u]][i],Q.push(tree[u][i]); } return ; } void search(){ int u=1; REP(i,1,strlen(s+1)){ int j=tree[u][s[i]-'a'],ans=0; while(j>1) ans+=isend[j],isend[j]=0,j=nxt[j]; u=tree[u][s[i]-'a']; if(ans) cout<<i<<endl; } } int main(){ in(n); REP(i,1,n) scanf("%s",t+1),insert(t); getnxt(); scanf("%s",s+1); search(); }
SPFA:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } queue <int> Q; int n,m; int total,head[100010],to[100010],nxt[100010],val[100010],dis[100010],vis[100010]; void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } void SPFA(){ memset(dis,127,sizeof(dis)); Q.push(1),dis[1]=0; while(!Q.empty()){ int u=Q.front();Q.pop();vis[u]=0; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(!vis[to[e]]){ vis[to[e]]=1; Q.push(to[e]); } } } return ; } int main(){ in(n),in(m); int a,b,c; REP(i,1,m) in(a),in(b),in(c),adl(a,b,c); SPFA(); REP(i,1,n) cout<<dis[i]<<" "; }
Dijkstra:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; int total,head[100010],to[100010],nxt[100010],val[100010]; int vis[100010],dis[100010]; struct node{ int ind,val; }; priority_queue <node> Q; bool operator < (node a,node b){ return a.val>b.val; } void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } void Dijkstra(){ memset(dis,127,sizeof(dis)); Q.push(node{1,0});dis[1]=0; while(!Q.empty()){ int u=Q.top().ind;Q.pop();vis[u]=1; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; Q.push(node{to[e],dis[to[e]]}); } } return ; } int main(){ in(n),in(m); int a,b,c; REP(i,1,m) in(a),in(b),in(c),adl(a,b,c); Dijkstra(); REP(i,1,n) cout<<dis[i]<<" "; }
Negative ring:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; int total,head[100010],to[100010],nxt[100010],val[1000010]; int dis[100010],vis[100010]; void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } void dfs(int u){ for(int e=head[u];e;e=nxt[e]){ if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(!vis[to[e]]){ vis[to[e]]=1; dfs(to[e]); vis[to[e]]=0; } else cout<<"polite",exit(0); } } return ; } int main(){ in(n),in(m); int a,b,c; REP(i,1,m) in(a),in(b),in(c),adl(a,b,c); dis[1]=0; dfs(1); }
Get negative Ring:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <stack> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; int total,head[100010],to[100010],nxt[100010],val[1000010]; int dis[100010],vis[100010],book[100010]; stack <int> S; void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } void dfs(int u){ book[u]=1; for(int e=head[u];e;e=nxt[e]){ if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(!vis[to[e]]){ vis[to[e]]=1; S.push(to[e]); dfs(to[e]); S.pop(); vis[to[e]]=0; } else{ while(!S.empty() && S.top()!=to[e]) cout<<S.top()<<" ",S.pop(); cout<<S.top(),S.pop(),exit(0); } } } return ; } int main(){ in(n),in(m); int a,b,c; REP(i,1,m) in(a),in(b),in(c),adl(a,b,c); REP(i,1,n) if(!book[i]) S.push(i),vis[i]=1,memset(dis,0,sizeof(dis)),dfs(i); S.push(1); } /* 4 5 1 2 1 2 3 -1 3 1 -2 3 4 2 1 4 3 */
lowest common ancestor:
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <stack> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; int total,head[100010],to[100010],nxt[100010]; int tree[100010][30],depth[100010]; inline void adl(int a,int b){ total++; to[total]=b; nxt[total]=head[a]; head[a]=total; return ; } inline void dfs(int u,int fa){ REP(i,1,21) tree[u][i]=tree[tree[u][i-1]][i-1]; for(int e=head[u];e;e=nxt[e]) if(to[e]!=fa){ depth[to[e]]=depth[u]+1; tree[to[e]][0]=u; dfs(to[e],u); } return ; } inline int lca(int u,int v){ if(depth[u]<depth[v]) swap(u,v); int d=depth[u]-depth[v]; for(int i=0;(1<<i)<=d;i++) if((1<<i) & d) u=tree[u][i]; if(u==v) return u; for(int i=21;i>=0;i--) if(tree[u][i]!=tree[v][i]) u=tree[u][i],v=tree[v][i]; return tree[u][0]; } int main(){ in(n); int a,b; REP(i,1,n-1) in(a),in(b),adl(a,b),adl(b,a); depth[1]=1,dfs(1,0); in(m); REP(i,1,m){ in(a),in(b); printf("%d ",lca(a,b)); } return 0; }
binary index tree：
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <stack> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m; int tree[4000010]; inline void add(int i,int a){ for(;i<=n;i+=(i&-i)) tree[i]+=a; return ; } inline int get(int i){ int ans=0; for(;i>0;i-=(i&-i)) ans+=tree[i]; return ans; } int main(){ in(n); int a,b,p; REP(i,1,n) in(a),add(i,a); in(m); REP(i,1,m){ in(p); if(p==1) in(a),in(b),add(a,b); else in(a),in(b),printf("%d ",get(b)-get(a-1)); } } /* 3 1 2 3 100 1 2 5 */
ST table：
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <stack> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int n,m,a,b; int s[10000010][30]; int Log[100000010]; int main(){ in(n); REP(i,1,n) in(s[i][0]); REP(j,1,21) for(int i=1;i+(1<<j-1)<=n;i++) s[i][j]=min(s[i][j-1],s[i+(1<<j-1)][j-1]); Log[1]=0; REP(i,2,21) Log[i]=Log[i>>1]+1; in(m); REP(i,1,m){ in(a),in(b); int x=Log[b-a+1]; cout<<x<<" "<<b-(1<<x)+1<<endl; cout<<min(s[a][x],s[b-(1<<x)+1][x])<<endl; } return 0; }
exgcd：
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <stack> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int a,b,d,x,y,t; void exgcd(int a,int b,int &d,int &x,int &y){ if(b==0) x=1,y=0,d=a; else exgcd(b,a%b,d,x,y),t=x,x=y,y=t-a/b*y; return ; } int main(){ in(a),in(b); exgcd(a,b,d,x,y); cout<<x<<" "<<y<<endl; }
持续更新......
dititally DP:
Chinese remainder theorem：