信息学竞赛算法指北

蔚落 2021-11-05 12:52 453阅读 0赞

# 排序 #

##### STL排序 #####

#include <bits/stdc++.h> #include <conio.h> using namespace std; int main(){ const int N = 5; int a [N] = {12,35,99,18,76}; sort(a,a+5); for(int i = 0;i<N;i++){ cout<<a[i]<<' '; } return 0; }

##### 桶排序 #####

#include <bits/stdc++.h> #include <conio.h> using namespace std; int main(){ int a = 1,b=100,c=5; int srt[100001] = {0}; //cin>>a>>b>>c; srt[a]++; srt[b]++; srt[c]++; for(int i = 1;i<=100000;i++){ while(srt[i]){ cout<<i<<' '; srt[i]--; } } return 0; }

##### 冒泡排序 #####

#include <bits/stdc++.h> #include <conio.h> using namespace std; int main(){ const int N = 5; int a [N] = {12,35,99,18,76}; for(int i = 0;i<N;i++){ for(int j = 0;j<N-i;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } for(int i = 0;i<N;i++){ cout<<a[i]<<' '; } return 0; }

##### 快速排序 #####

#include <bits/stdc++.h> #include <conio.h> using namespace std; const int N = 5; int a [N] = {12,35,99,18,76}; void qs(int l,int r){ if(l>=r) return ; int t = a[l]; int i = l,j=r; while(i!=j){ //必须先右后左 while(a[j]>=t&&i<j) j--; while(a[i]<=t&&i<j) i++; if(i<j) swap(a[i],a[j]); } a[l] = a[i]; a[i] = t; qs(l,i-1); qs(i+1,r); return ; } int main(){ qs(0,N-1); for(int i = 0;i<N;i++){ cout<<a[i]<<' '; } return 0; }

# 数论 #

### 逆元 ###

*  自己瞎写的，可能是错的

//这个真的太慢了，请看下面那个 #include<bits/stdc++.h> using namespace std; const int A = 3,p=11; unsigned long long inv = 1; int main(){ int i; for(i = 0;;i++){ inv = ((i*p+1)/A)%p; if((A*inv)%p==1) break; } cout << i << ' ' << inv; return 0; }

*  现在才是真正的求逆元，用了exgcd

#include<cstdio> #include<iostream> using namespace std; #define pr pair<int ,int > pr exgcd(int a,int b){ if(b==0) return pr(1,0); pr tmp = exgcd(b,a%b); return pr(tmp.second,tmp.first-a/b*tmp.second); } int main(){ int a,b; cin>>a>>b; int t = exgcd(a,b).first; if(t < 0) t = t + b; cout <<t; return 0; }

### 欧拉函数 ###

int phi(int n){//对n求欧拉 int Ans = n; for(int i = 2;i<=sqrt(n);i++){//找出每一个因数 if(n%i == 0){//是因数 Ans = Ans / i * (i-1);//欧拉函数分解求法 while(n%i==0) n = n / i;//去除该因子 } } if(n>1) Ans = Ans / n * (n-1);//最后还有因子 return Ans; }

# 图论 #

### 最短路 ###

##### SPFA (单源) #####

//Code From 算法竞赛进阶指南 #include <bits/stdc++.h> using namespace std; const int N = 100010, M = 1000010; int head[N],ver[M],edge[M],Next[M],d[N];//d是从初始顶点到其他点的距离,ver使出度,edge是路径长度,Next是下一个该顶点的出度，即原来的第二个出度 int n,m,tot; queue<int> q; bool v[N];//顶点是否已在队列中 void add(int x,int y,int z){ //邻接表的添加 ver[++tot] = y;//ver是终止顶点，tot是总路径数，y是终止顶点 edge[tot] = z;//edge是路径长度 Next[tot] = head[x];//Next是下一个该顶点的出度，即原来的第二个出度 head[x] = tot;//将原来的第二个出度替换为当前添加的出度，原来的第二个出度存放在现在的第二个出度的下一个出度中 } void SPFA(){ memset(d,0x3f,sizeof(d));//默认将d最大化，0x3f 这里不解释,反正很大 memset(v,0,sizeof(v)); d[1] = 0;//1到1的距离为1 v[1] = 1;//1号顶点在队列中,与下面一句组合使用使队列中同一顶点只出现一次 q.push(1);//这里面的1是出发顶点 while(q.size()){//队列不为空时 int x = q.front();//取出队首 q.pop();//删除队首 v[x] = 0;//代表x已被移除队列 for(int i = head[x];i != 0;i=Next[i]){//遍历队首所能到达的每一条边 int y = ver[i];//到达的边 int z = edge[i];//边长 if(d[y]>d[x]+z){//判断是否更改"最小距离" d[y] = d[x] + z; if(!v[y]){ q.push(y);//将y顶点加入队列 v[y] = 1;//代表y顶点已被移出队列 } } } } } int main(){ cin>>n>>m; for(int i = 1;i<=m;i++){//读入m条边 int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } SPFA(); for(int i = 1;i<=n;i++){ cout<<d[i]<<endl; } return 0; } //source:5 5 2 3 2 1 2 -3 1 5 5 4 5 2 3 4 3 //ans:0 -3 -1 2 4

##### Floyd-Wallshall (整张图) #####

#include <bits/stdc++.h> #include <conio.h> using namespace std; int e[200][200]; int n,m; void Floyd_Wallshall(){ for(int k = 1;k<=n;k++){//三层循环通过k来求得当前状态下i->j的路径最小值 for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ if(e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j]; } } } return ; } int main(){ cin>>n>>m; for(int i = 1;i<=n;i++){ memset(e[i],0x3f,sizeof(e[i])); e[i][i] = 0;//初始化 } for(int i = 1;i<=m;i++){ int x,y,z; scanf("%d %d %d",&x,&y,&z);//直接读入 e[x][y] = z;//直接读入 } Floyd_Wallshall(); for(int i = 1;i<=n;i++){//输出 for(int j = 1;j<=n;j++){ printf("%d ",e[i][j]); } printf("\n"); } return 0; }

### 负环 ###

*  SPFA

//Luogu P3385 【模板】负环 #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <ctime> using namespace std; const int MaxN = 2003,MaxM= 3005; int cnt[MaxN]; int tot,T,N,M,d[MaxN]; bool v[MaxN]; int first[MaxN],ver[MaxM * 2],Next[MaxM * 2],wei[MaxM * 2]; void read(int x,int y,int z){ Next[++tot] = first[x]; first[x] = tot; ver[tot] = y; wei[tot] = z; } void spfa(){ int x,y,z; memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); memset(cnt,0,sizeof(cnt)); d[1] = 0; v[1] = 1; queue <int> q; q.push(1); cnt[1] = 1; while(q.size()){ x = q.front(); q.pop(); v[x] = false; for(int i = first[x];i;i=Next[i]){ y = ver[i]; z = wei[i]; if(d[y]>d[x]+z){ d[y] = d[x] + z; cnt[y] = cnt[x]+1; if(cnt[y]>N){ cout<<"YE5"<<endl; return ; } if(!v[y]) q.push(y),v[y] = 1; } } } cout<<"N0"<<endl; return ; } void calc(){ memset(first,0,sizeof(first)); memset(Next,0,sizeof(Next)); tot = 0; scanf("%d %d",&N,&M); int t1,t2,t3; for(int i = 1;i<=M;i++){ scanf("%d %d %d",&t1,&t2,&t3); if(t3>=0) read(t2,t1,t3); read(t1,t2,t3); } spfa(); } int main() { scanf("%d",&T); while(T--) calc(); return 0; }

### 割点割边 ###

##### Tarjan判割点 #####

#include <iostream> #include <cstdio> using namespace std; int n,m; int first[1000],next[10000],ver[10000]; int tot = 0; int dfn[1000],low[1000],num=1; int flag[1000]; void tarjan(int node,int father){ dfn[node] = low[node] = num++; int child = 0; for(int i = first[node];i;i=next[i]){ int togo = ver[i]; if(dfn[togo] == 0){ child++; tarjan(togo,node); low[node] = min(low[node],low[togo]); if(node != 1 && low[togo] >= dfn[node]){ flag[node] = 1; } else if(node == 1 && child == 2){ flag[1] = 1; } } else if (togo != father){ low[node] = min(low[node],low[togo]); } } return ; } void read(int x,int y){ next[tot] = first[x]; first[x] = tot; ver[tot] = y; tot++; return; } int main() { scanf("%d %d",&n,&m); int t1,t2; for(int i = 1;i<=m;i++){ scanf("%d %d",&t1,&t2); read(t1,t2); read(t2,t1); } tarjan(1,1); for(int i = 1;i<=n;i++){ if(flag[i]) cout<<i<<' '; } return 0; } //6 7 1 4 1 3 4 2 3 2 2 5 2 6 5 6 //2

### 并查集 ###

*  Luogu P3367

#include <iostream> #include <cstdio> using namespace std; #define maxn 10002 int N,M; int fa[maxn]; int f(int x){ if(fa[x] == x) return x; return fa[x] = f(fa[x]); } int main() { scanf("%d%d",&N,&M); for(int i = 1;i<=N;i++){ fa[i] = i; } int t1,t2,t3; for(int i = 1;i<=M;i++){ scanf("%d %d %d",&t1,&t2,&t3); if(t1 == 1){ fa[f(t2)] = f(t3); }else { if(f(t2) == f(t3)){ printf("Y\n"); }else{ printf("N\n"); } } } return 0; }

### 二分图匹配 ###

*  Luogu P3386
 *  以下为未优化代码
    
    > 用时: 2533ms / 内存: 7100KB

#include <iostream> #include <bitset> #include <cstdio> using namespace std; #define maxn 2002 #define maxm 1002001 #define itn int bitset <maxn> book; int tot,N,M,sum; int match[maxn],first[maxn],ver[maxm],next[maxm]; void read(int x,int y){ next[++tot] = first[x]; first[x] = tot; ver[tot] = y; } void clean(){ bitset <maxn> nul; book = nul; } bool dfs(int nd){ for(int i = first[nd];i;i=next[i]){ int v = ver[i]; if(!book[v]){ book[v]=1; if(match[v] == 0 || dfs(match[v])){ match[v] = nd; return true; } } } return false; } int main() { int tN,t1,t2; scanf("%d %d %d",&N,&tN,&M); for(int i = 1;i<=M;i++){ scanf("%d %d",&t1,&t2); if(t1>N||t2>tN){ i--,M--; continue; } read(t1,t2); } for(int i = 1;i<=N;i++){ clean(); if(dfs(i)) sum++; } printf("%d",sum); return 0; }

*  以下为优化代码
    
    > 用时: 2213ms / 内存: 2992KB

#include <iostream> #include <bitset> #include <cstdio> using namespace std; #define maxn 2002 #define maxm 1002001 #define itn int bitset <maxn> book; int tot,N,M,sum; int match[maxn],first[maxn],ver[maxm],next[maxm]; inline int qr(){ char ch; int ret = 0,f = 1; ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ ret = ret * 10 + ch - '0'; ch = getchar(); } return f * ret; } inline void read(int x,int y){ next[++tot] = first[x]; first[x] = tot; ver[tot] = y; } inline void clean(){ bitset <maxn> nul; book = nul; } bool dfs(int nd){ for(register int i = first[nd];i;i=next[i]){ int v = ver[i]; if(!book[v]){ book[v]=1; if(match[v] == 0 || dfs(match[v])){ match[v] = nd; return true; } } } return false; } int main() { int tN,t1,t2; //scanf("%d %d %d",&N,&tN,&M); N = qr(); tN = qr(); M = qr(); for(register int i = 1;i<=M;i++){ //scanf("%d %d",&t1,&t2); t1 = qr(); t2 = qr(); if(t1>N||t2>tN){ i--,M--; continue; } read(t1,t2); } for(register int i = 1;i<=N;i++){ clean(); if(dfs(i)) sum++; } printf("%d",sum); return 0; }

### 强联通分量 ###

#### Tarjan ####

*  Luogu P2863

#include <iostream> #include <cstdio> #include <bitset> #include <stack> using namespace std; #define MaxN 10002 #define MaxM 50002 int N,M,tot,id,cnt,ans; bitset <MaxN> ins; bitset <MaxN> use; int color[MaxN] ; int dfn[MaxN],num[MaxN]; int first[MaxN],ver[MaxM],Next[MaxM]; stack <int> s; int qr() { char ch = getchar(); int ans = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) { ans = ans * 10 + ch - '0'; ch = getchar(); } return ans; } void read(int x,int y) { Next[++tot] = first[x]; first[x] = tot; ver[tot] = y; } void tarjan(int nd) { ins[nd] = 1; s.push(nd); dfn[nd] = num[nd] = ++id; for(int i = first[nd]; i; i=Next[i]) { int access = ver[i]; if(!dfn[access]) { tarjan(access); num[nd] = min(num[nd],num[access]); } else if(ins[access]) { num[nd] = min(num[nd],dfn[access]); } } if(dfn[nd] == num[nd]){ cnt++; int v; do{ color[cnt]++; v = s.top(); s.pop(); ins[v] = 0; use[v] = 1; }while(nd != v); } } int main() { N = qr(); M = qr(); int t1,t2; for(int i = 1; i<=M; i++) { t1 = qr(); t2 = qr(); read (t1,t2); } for(int i = 1; i<=N; i++) { if(!use[i]) tarjan(i); } for(int i = 1;i<=cnt;i++){ if(color[i]>1) ans++; } cout<<ans; return 0; }

# 动态规划 #

### 0/1背包 ###

for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) { if (j < w[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]); } }

### 完全背包 ###

#include <iostream> using namespace std; int T,M; struct drug{ int time; int value; }a[105]; int f[1005]; int main() { ios::sync_with_stdio(false); cin>>T>>M; int t1,t2; for(int i = 1;i<=M;i++){ cin>>a[i].time>>a[i].value; } for(int i = 1;i<=M;i++){ for(int j = a[i].time;j<=T;j++){ f[j]=max(f[j],f[j-a[i].time]+a[i].value); } } cout<<f[T]; return 0; }

# 数据结构 #

### 线段树 ###

[线段树讲解][Link 1]

#### 单点修改多点查询 ####

*  ACOJ 12222

#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; #define ll long long #define l(p) p<<1 #define lt(p) t[p<<1] #define r(p) p<<1|1 #define rt(p) t[p<<1|1] #define maxn 100000 #define Mid int mid = (t[p].l+t[p].r)>>1 #define Luogu #ifdef Luogu #define read scanf("%d",&M),build(1,1,N); #endif // Luogu #ifdef Acoj #define read build(1,1,N),scanf("%d",&M); #endif // Acoj struct node{ int l,r; ll w,f; }t[maxn<<2+3]; void build(int p,int l,int r){ t[p].l = l; t[p].r = r; if(l == r){ //int t; //scanf("%d",&t); scanf("%lld",&t[p].w); return; } int mid = (l+r)>>1; build(l(p),l,mid); build(r(p),mid+1,r); t[p].w = lt(p).w+rt(p).w; } void spread(int p){ if(t[p].f){ lt(p).w += t[p].f*(lt(p).r-lt(p).l+1); rt(p).w += t[p].f*(rt(p).r-rt(p).l+1); lt(p).f += t[p].f; rt(p).f += t[p].f; t[p].f = 0; } } void change(int p,int l,int r,int z){ if(t[p].l>=l&&t[p].r<=r){ t[p].w += (ll)z*(t[p].r-t[p].l+1); t[p].f += z; return ; } spread(p); Mid; if(l<=mid) change(l(p),l,r,z); if(r> mid) change(r(p),l,r,z); t[p].w = lt(p).w+rt(p).w; } ll ask(int p,int l,int r){ if(t[p].l>=l&&t[p].r<=r){ return t[p].w; } spread(p); ll ans = 0; Mid; if(l<=mid) ans+=ask(l(p),l,r); if(r> mid) ans+=ask(r(p),l,r); return ans; } int N,M; int main() { scanf("%d",&N); read int t1,t2,t3; for(int i = 1;i<=M;i++){ scanf("%d",&t1); if(t1 == 1){ scanf("%d %d %d",&t1,&t2,&t3); change(1,t1,t2,t3); }else { scanf("%d %d",&t2,&t3); cout<<ask(1,t2,t3)<<endl; } } return 0; }

### 树状数组 ###

#### 单点修改 ####

*  LuoguP3374

#include <iostream> #include <cstdio> using namespace std; int A[500002]; int N,M; int lowbit(int a){ return a&(-a); } void add(int a,int b){ while(a<=N){ A[a]+=b; a += lowbit(a); } } int Find(int a){ int ans = 0; while(a>0){ ans += A[a]; a -= lowbit(a); } return ans; } int main() { int t1,t2,t3; scanf("%d %d",&N,&M); for(int i = 1;i<=N;i++){ scanf("%d",&t1); add(i,t1); } for(int i = 1;i<=M;i++){ scanf("%d",&t1); if(t1 == 1){ scanf("%d %d",&t2,&t3); add(t2,t3); } else { scanf("%d %d",&t2,&t3); cout<<Find(t3)-Find(t2-1)<<endl; } } return 0; }

### ST表 ###

*  这个是真的迷
 *  Luogu P3865

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int a[100005][40]; inline int qr(){ char ch; int ret=0; ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)){ ret = ret * 10 + ch - '0'; ch = getchar(); } return ret; } int main() { int N,M; N=qr();M=qr(); for(int i = 1;i<=N;i++){ a[i][0] = qr(); } for(int i = 1;i<=21;i++){ for(int j = 1;j+(1<<i)-1<=N;j++){ a[j][i] = max(a[j][i-1],a[j+(1<<(i-1))][i-1]); } } int t1,t2; for(int i = 1;i<=M;i++){ t1=qr();t2=qr(); int k = log2(t2-t1+1); printf("%d\n",max(a[t1][k],a[t2-(1<<k)+1][k])); } return 0; }

转载于:https://www.cnblogs.com/byha/p/11243604.html

[Link 1]: https://www.luogu.org/blog/derren/solution-p3372