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

模板

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;
  6. bool cmp(int a,int b)
  7. {
  8.     return a>b;//小到大
  9. }
  11. sort(a,a+n,cmp);

堆排序

  1. int heap[maxn];
  3. int refresh()
  4. {
  5.     for(int i=1;i<=n/2;i++)
  6.     {
  7.         if(heap[i]<heap[2*i]) swap(heap[i],heap[2*i]);
  8.     }
  9. }
  12. for(int i=1;i<=n;i++)
  13. {
  14.     heap[i]=num[i];
  15. }
  16. 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. }
  8. //素数打表
  9. void prime(int n)
  10. {
  11.     memset(f,1,sizeof(f);
  12.     f[0]=0;
  13.     f[1]=0;
  14.     for(int i=2;i*i<n;i++)
  15.     {
  16.         if(f[i])
  17.         {
  18.             j=2*i;
  19.             while(j<=maxn)
  20.             {
  21.                 f[j]=0;
  22.                 j+=i;
  23.             }
  24.         }
  25.     }
  26. }

快速幂

  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];
  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. }
  18. void dfs(int x)
  19. {
  20.     printf("%d\n",x);
  21.     vis[x]=1;
  22.     for(int i=head[x];i!=0;i=bian[i].nxt)
  23.     {
  24.         if(!vis[bian[i].to]) dfs(bian[i].to);
  25.     }
  26. }
  28. 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];
  11. void add(int a,int b)
  12. {
  13.     cnt++;
  14.     bian[cnt].to=b;
  15.     bian[cnt].nxt=head[a];
  16.     head[a]=cnt;
  17. }
  19. void bfs(int x)
  20. {
  21.     que.push(x);
  22.     while(!que.empty())
  23.     {
  24.         int num=que.top();
  25.         printf("%d\n",num);
  26.         que.pop();
  27.         for(int i=head[num];i!=0;i=bian[i].nxt)
  28.         {
  29.             if(!vis[bian[i].to]) que.push(bian[i].to);
  30.         }
  31.     }
  32. }

dijkstra最短路

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

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

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;
  12. struct node
  13. {
  14.     int to;
  15.     int w;
  16. }edge[200005];
  18. struct cmp
  19. {
  20.     bool operator()(const int &a,const int &b)
  21.     {
  22.         return edge[a].w>edge[b].w;
  23.     }
  24. };
  26. priority_queue < int ,vector<int>,cmp > que;
  28. void add(int x,int y,int z)
  29. {
  30.     cnt++;
  31.     next[cnt]=head[x];
  32.     head[x]=cnt;
  33.     edge[cnt].to=y;
  34.     edge[cnt].w=z;
  35. }
  37. void prim(int x)
  38. {
  39.     inset[x]=1;
  40.     ans++;
  41.     for(int i=head[x];i!=0;i=next[i]) que.push(i);
  42.     while(ans!=n)
  43.     {
  44.         int b=que.top();
  45.         que.pop();
  46.         if(!inset[edge[b].to])
  47.         {
  48.             inset[edge[b].to]=1;
  49.             tot+=edge[b].w;
  50.             ans++;
  51.             for(int i=head[edge[b].to];i!=0;i=next[i]) que.push(i);
  52.         }
  53.     }
  54. }
  56. int main()
  57. {
  58.     scanf("%d%d",&n,&m);
  59.     for(int i=1;i<=m;i++)
  60.     {
  61.         int a,b,c;
  62.         scanf("%d%d%d",&a,&b,&c);
  63.         add(a,b,c);
  64.         add(b,a,c);
  65.     }
  66.     prim(1);
  67.     printf("%d",tot);
  68. }

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. }
  11. void update(int cur)
  12. {
  13.     sum[cur]=sum[cur<<1]+sumpcur<<1|1];
  14. }
  16. void add(int l,int r,int L,int R,int x,int cur)//加点
  17. {
  18.     if(L=<l&&R>=r)
  19.     {
  20.         cov[cur]+=x;//cov就是lazytag
  21.         sum[cur]+=(r-l+1)*x;
  22.         return x;
  23.     }
  24.     int mid=l+r>>1;
  25.     if(L<=mid)add(l,mid,L,R,x,cur<<1);
  26.     if(R>mid)add(mid+1,r,L,R,x,cur<<1|1);
  27. }
  28. int query(int l,int r,int L,int R,int cur)
  29. {
  30.     if(L<=l&&R>=r) return sum[cur];
  31.     if(cov[cur]) pushdown(cur,r-l+1);
  32.     int mid=l+r>>1,ans=0;
  33.     if(L<=mid)ans+=query(l,mid,L,R,cur<<1);
  34.     if(R>mid)ans+=query(mid+1,r,L,R,cur<<1|1);
  35.     return ans;
  36. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注