[关闭]
@P2Oileen 2017-08-10T02:47:20.000000Z 字数 5636 阅读 479

模板

1


搜索

dfs

  1. int dfs()
  2. {
  3. if(edge) return something;
  4. if(jianzhi) return 0;
  5. for(int i=状态1;i<=最后一个状态;i++)
  6. {
  7. if(满足条件&&!vis[i]) dfs(i);
  8. vis[i]=1;
  9. }
  10. }

bfs

  1. int bfs()
  2. {
  3. while(!que.empty())
  4. {
  5. int x=que.front();
  6. vis[que.front()]=1;
  7. que.pop();
  8. for(int i=状态1;i<最后一个状态;i++)
  9. {
  10. if(状态合法 && !vis[i]) que.push(i);
  11. }
  12. }
  13. }

排序

选择排序

  1. selection sort()
  2. {
  3. for(int i=0;i<n;i++)
  4. {
  5. for(int j=i+1;j<n;j++)
  6. if(a[i]>a[j]) swap(a[i],a[j]);
  7. }
  8. }

插入排序

  1. insertion sort
  2. {
  3. for(int i=0;i<n;i++)
  4. {
  5. for(int j=i;j>0;j--)
  6. {
  7. if(a[j]<a[j-1]) swap(a[j],a[j-1]);
  8. else break;
  9. }
  10. }
  11. }

冒泡排序

  1. bubble sort
  2. {
  3. for(int i=n;i>=0;i--)
  4. {
  5. for(int j=1;j<i;j++) if(a[j-1]>a[j]) swap(a[j-1],a[j]);
  6. }
  7. }

桶排序

  1. bucket sort
  2. {
  3. for(int i=0;i<=100;i++) b[i]=0;
  4. for(int i=1;i<n;i++) b[a[i]]++;
  5. for(int i=0;i<100;i++) if(b[i]!=0) while(b[i]--) printf("%d\n",i);
  6. }

快速排序

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. bool cmp(int a,int b)
  6. {
  7. return a>b;//小到大
  8. }
  9. sort(a,a+n,cmp);

堆排序

  1. int heap[maxn];
  2. int refresh()
  3. {
  4. for(int i=1;i<=n/2;i++)
  5. {
  6. if(heap[i]<heap[2*i]) swap(heap[i],heap[2*i]);
  7. }
  8. }
  9. for(int i=1;i<=n;i++)
  10. {
  11. heap[i]=num[i];
  12. }
  13. refresh();

数论

GCD

  1. int GCD(int a,int b)
  2. {
  3. return b==0?a:GCD(b,a%b);
  4. }

LCM

  1. int lcm(int a,int b)
  2. {
  3. return a / gcd(a, b) * b;
  4. }

素数

  1. //单个素数
  2. bool is_prime(int x)
  3. {
  4. for(int i=2;i*i<x;i++) if(x % i==0) return 0;
  5. return 1;
  6. }
  7. //素数打表
  8. void prime(int n)
  9. {
  10. memset(f,1,sizeof(f);
  11. f[0]=0;
  12. f[1]=0;
  13. for(int i=2;i*i<n;i++)
  14. {
  15. if(f[i])
  16. {
  17. j=2*i;
  18. while(j<=maxn)
  19. {
  20. f[j]=0;
  21. j+=i;
  22. }
  23. }
  24. }
  25. }

快速幂

  1. int ksm(int x,int y)
  2. {
  3. if(y==1) return x;
  4. int num=ksm(x,y/2);
  5. if(y%2==0) return num*num;
  6. else return num*num*x;
  7. }

exgcd

  1. int exgcd(int a,int b,int &x,int &y)
  2. {
  3. int x1,y1;
  4. if(b==0)
  5. {
  6. x=1;
  7. y=0;
  8. return a;
  9. }
  10. else
  11. {
  12. x:=y1;
  13. y:=x1-(a/b)*y1;
  14. return exgcd(b, a % b, x1, y1);
  15. }
  16. }

位运算

功能 示例 位运算
去掉最后一位 (101101->10110) x >> 1
在最后加一个0 (101101->1011010) x << 1
在最后加一个1 (101101->1011011) x << 1+1
把最后一位变成1 (101100->101101) x | 1
把最后一位变成0 (101101->101100) x | 1-1
最后一位取反 (101101->101100) x ^ 1
把右数第k位变成1 (101001->101101,k=3) x | (1 << (k-1))
把右数第k位变成0 (101101->101001,k=3) x & !(1 << (k-1))
右数第k位取反 (101001->101101,k=3) x ^ (1 << (k-1))
取末三位 (1101101->101) x & 7
取末k位 (1101101->1101,k=5) x & (1<< k -1)
取右数第k位 (1101101->1,k=4) x >> (k-1) & 1
把末k位变成1 (101001->101111,k=4) x | (1 << k-1)
末k位取反 (101001->100110,k=4) x ^ (1 << k-1)
把右边连续的1变成0 (100101111->100100000) x & (x+1)
把右起第一个0变成1 (100101111->100111111) x | (x+1)
把右边连续的0变成1 (11011000->11011111) x | (x-1)
取右边连续的1 (100101111->1111) (x ^ (x+1)) >> 1
去掉右起第一个1的左边 (100101000->1000) x & (x ^ (x-1))

!a=-a-1;

图论

图上dfs

  1. int head[10005]={0};
  2. int cnt=0;
  3. int vis[10005];
  4. struct edge
  5. {
  6. int to;
  7. int nxt=0;
  8. }bian[100005];
  9. void add(int a,int b)
  10. {
  11. cnt++;
  12. bian[cnt].to=b;
  13. bian[cnt].nxt=head[a];
  14. head[a]=cnt;
  15. }
  16. void dfs(int x)
  17. {
  18. printf("%d\n",x);
  19. vis[x]=1;
  20. for(int i=head[x];i!=0;i=bian[i].nxt)
  21. {
  22. if(!vis[bian[i].to]) dfs(bian[i].to);
  23. }
  24. }
  25. dfs(1);

图上bfs

  1. queue <int> que;
  2. int head[10005]={0};
  3. int cnt=0;
  4. int vis[10005];
  5. struct edge
  6. {
  7. int to;
  8. int nxt=0;
  9. }bian[100005];
  10. void add(int a,int b)
  11. {
  12. cnt++;
  13. bian[cnt].to=b;
  14. bian[cnt].nxt=head[a];
  15. head[a]=cnt;
  16. }
  17. void bfs(int x)
  18. {
  19. que.push(x);
  20. while(!que.empty())
  21. {
  22. int num=que.top();
  23. printf("%d\n",num);
  24. que.pop();
  25. for(int i=head[num];i!=0;i=bian[i].nxt)
  26. {
  27. if(!vis[bian[i].to]) que.push(bian[i].to);
  28. }
  29. }
  30. }

dijkstra最短路

  1. #include<cstdio>
  2. #include<cstring>
  3. const int N = 100500;
  4. const int M = 200500;
  5. int head[N],to[M],next[M],w[M],cnt;
  6. int dis[N]; //最短路长度
  7. bool vis[N];
  8. int n,m;
  9. void add(int x,int y,int z)
  10. {
  11. cnt++;
  12. next[cnt]=head[x];
  13. head[x]=cnt;
  14. to[cnt]=y;
  15. w[cnt]=z;
  16. }
  17. memset(dis,0x3f,sizeof dis);
  18. dis[1]=0;
  19. for(k=1;k<=n;k++)
  20. {
  21. int minp,minz=0x3f3f3f3f;
  22. for(i=1;i<=n;i++)
  23. {
  24. if(vis[i])
  25. {
  26. if(dis[i]<minz)
  27. {
  28. minz=dis[i];
  29. minp=i;
  30. }
  31. }
  32. }
  33. vis[minp]=1;
  34. int now=head[minp];
  35. while(now)
  36. {
  37. int tox=to[now];
  38. if(dis[tox]>dis[minp]+w[now]) dis[tox]=dis[minp]+w[now];
  39. now=next[now];
  40. }
  41. }
  42. for(i=1;i<=n;i++)
  43. printf("%d\n",dis[i]);
  44. }

floyd

  1. for(k=1;k<=n;k++)
  2. for(i=1;i<=n;i++)
  3. for(j=1;j<=n;j++)
  4. if(e[i][j]>e[i][k]+e[k][j])
  5. e[i][j]=e[i][k]+e[k][j];

spfa

  1. struct node
  2. {
  3. int to;
  4. int w;
  5. }bian[100005];
  6. void add(int a,int b,int c)
  7. {
  8. cnt++;
  9. nxt[cnt]=head[a];
  10. head[a]=cnt;
  11. bian[cnt].to=b;
  12. bian[cnt].w=c;
  13. }
  14. void spfa()
  15. {
  16. while(!que.empty())
  17. {
  18. int x=que.front();
  19. que.pop();
  20. vis[x]=0;
  21. for(int i=head[x];i!=0;i=nxt[i])
  22. {
  23. if(dist[x]+bian[i].w<dist[bian[i].to])
  24. {
  25. dist[bian[i].to]=dist[x]+bian[i].w;
  26. if(!vis[bian[i].to])
  27. {
  28. que.push(bian[i].to);
  29. vis[bian[i].to]=1;
  30. }
  31. }
  32. }
  33. }
  34. }
  35. memset(dist,0x3f3f3f3f,sizeof(dist));
  36. dist[1]=0;
  37. que.push(1);
  38. spfa();
  39. for(int i=1;i<=n;i++)
  40. {
  41. if(dist[i]!=4557430888798830399) printf("%lld\n",dist[i]);
  42. else printf("INF\n");
  43. }

prim(priority_queue优化)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <queue>
  5. using namespace std;
  6. int inset[50005],head[50005],next[200005];
  7. int ans=0;
  8. int cnt=0;
  9. int tot=0;
  10. int n,m;
  11. struct node
  12. {
  13. int to;
  14. int w;
  15. }edge[200005];
  16. struct cmp
  17. {
  18. bool operator()(const int &a,const int &b)
  19. {
  20. return edge[a].w>edge[b].w;
  21. }
  22. };
  23. priority_queue < int ,vector<int>,cmp > que;
  24. void add(int x,int y,int z)
  25. {
  26. cnt++;
  27. next[cnt]=head[x];
  28. head[x]=cnt;
  29. edge[cnt].to=y;
  30. edge[cnt].w=z;
  31. }
  32. void prim(int x)
  33. {
  34. inset[x]=1;
  35. ans++;
  36. for(int i=head[x];i!=0;i=next[i]) que.push(i);
  37. while(ans!=n)
  38. {
  39. int b=que.top();
  40. que.pop();
  41. if(!inset[edge[b].to])
  42. {
  43. inset[edge[b].to]=1;
  44. tot+=edge[b].w;
  45. ans++;
  46. for(int i=head[edge[b].to];i!=0;i=next[i]) que.push(i);
  47. }
  48. }
  49. }
  50. int main()
  51. {
  52. scanf("%d%d",&n,&m);
  53. for(int i=1;i<=m;i++)
  54. {
  55. int a,b,c;
  56. scanf("%d%d%d",&a,&b,&c);
  57. add(a,b,c);
  58. add(b,a,c);
  59. }
  60. prim(1);
  61. printf("%d",tot);
  62. }

kruskal(待补充)

匈牙利算法

  1. bool find(int x){
  2. int i,j;
  3. for (j=1;j<=m;j++){//扫描每个妹子
  4. if (line[x][j]==true&&used[j]==false)//如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题,但是没有成功,所以就不用瞎费工夫了)
  5. {
  6. used[j]=1;
  7. if (girl[j]==0 || find(girl[j]))
  8. { //名花无主或者能腾出个位置来,这里使用递归
  9. girl[j]=x;
  10. return true;
  11. }
  12. }
  13. }
  14. return false;
  15. }

线段树

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void pushdown(int cur,int x)
  4. {
  5. cov[cur<<1]=cov[cur<<1|1]=cov[cur];
  6. sum[cur<<1]+=cov[cur]*(x+1>>1);
  7. sum[cur<<1|1]+=cov[cur]*(x>>1);
  8. cov[cur]=0;
  9. }
  10. void update(int cur)
  11. {
  12. sum[cur]=sum[cur<<1]+sumpcur<<1|1];
  13. }
  14. void add(int l,int r,int L,int R,int x,int cur)//加点
  15. {
  16. if(L=<l&&R>=r)
  17. {
  18. cov[cur]+=x;//cov就是lazytag
  19. sum[cur]+=(r-l+1)*x;
  20. return x;
  21. }
  22. int mid=l+r>>1;
  23. if(L<=mid)add(l,mid,L,R,x,cur<<1);
  24. if(R>mid)add(mid+1,r,L,R,x,cur<<1|1);
  25. }
  26. int query(int l,int r,int L,int R,int cur)
  27. {
  28. if(L<=l&&R>=r) return sum[cur];
  29. if(cov[cur]) pushdown(cur,r-l+1);
  30. int mid=l+r>>1,ans=0;
  31. if(L<=mid)ans+=query(l,mid,L,R,cur<<1);
  32. if(R>mid)ans+=query(mid+1,r,L,R,cur<<1|1);
  33. return ans;
  34. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注