基本算法

• 快速幂

1 ll ksm(ll a,ll b) 2 { 3     ll ans=1; 4     while(b) 5     { 6         if(b&1) ans=ans*a%p; 7         b>>=1; 8         a=a*a%p; 9     }10     return ans;11 }

• 64位大整数乘法

1 ll mul(ll a,ll b) 2 { 3     ll ans=0; 4     while(b) 5     { 6         if(b&1) ans=(ans+a)%p; 7         b>>=1; 8         a=a*2%p; 9     }10     return ans;11 }

• 离散化

1     for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];2     sort(b+1,b+1+n);3     int cnt=unique(b+1,b+1+n)-(b+1);4     for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;

• 归并排序求逆序对

1 void mergesort(int l,int r) 2 { 3     if(l==r) return ; 4     int mid=(l+r)>>1; 5     mergesort(l,mid); 6     mergesort(mid+1,r); 7     int i=l,j=mid+1,k=l-1; 8     while(i<=mid&&j<=r) 9     {10         if(a[i]<=a[j]) b[++k]=a[i],i++;11         else b[++k]=a[j],j++,(ans+=mid-i+1)%=moder;12     }13     while(i<=mid) b[++k]=a[i],i++;14     while(j<=r) b[++k]=a[j],j++;15     for(int qwq=l;qwq<=r;qwq++) a[qwq]=b[qwq];16 }

• 全排列

1 void dfs(int x) 2 { 3     for(int i=1;i<=n;i++) 4         if(!vis[i]) 5         { 6             seq[x]=i; 7             vis[i]=1; 8             if(x==n) work(); 9             else dfs(x+1);10             vis[i]=0;11         }12 }

• ST表

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int n,m; 8 int st[100090][30]; 9 10 int sta(int l,int r)11 {12     int k=log2(r-l+1);13     return max(st[l][k],st[r-(1<
        
       
      

• 两种二分

1 while(l
      
       >1; 4     if(check(mid)) r=mid; 5     else l=mid+1; 6 } 7 while(l
       
        >1;10     if(check(mid)) r=mid-1;11     else l=mid;12 }
       
      

1 double eps=1e-8;2 while(l+eps

• 康拓展开及其求逆 

1 void Recantor(ll x) 2 { 3     memset(vis,0,sizeof(vis)); 4     x--; 5     int j=0; 6     for(int i=1;i<=n;i++) 7     { 8         ll t=x/fac[n-i]; 9         for(j=1;j<=n;j++)10             if(!vis[j])11             {12                 if(!t) break;13                 t--;14             }15         printf("%d ",j);16         vis[j]=1;17         x%=fac[n-i]; 18     }19     printf("\n");20 }21 22 ll cantor()23 {24     ll ans=1;25     for(int i=1;i<=n;i++)26     {27         int tot=0;28         for(int j=i+1;j<=n;j++)29             if(a[j]

其他算法

• 莫队算法（不带修）

1 bool cmp(query a,query b) 2 { 3     return (a.l/block)^(b.l/block) ? a.l
      
       b.r); 4 }//奇偶块排序 5  6  7  8     block=sqrt(n); 9     for(int i=1;i<=n;i++) scanf("%d",&seq[i]);10     for(int i=1;i<=m;i++)11     {12         scanf("%d%d",&ask[i].l,&ask[i].r);13         ask[i].id=i;14         ask[i].in=ask[i].l/block;15     }16     sort(ask+1,ask+1+m,cmp);17     for(int i=1;i<=m;i++)18     {19         int l=ask[i].l,r=ask[i].r;20         while(posl
       
        r) remove(posr--);22         while(posl>l) add(--posl);23         while(posr
       
      

数学

• 预处理阶乘和处理逆元求组合数

1 ll exgcd(ll a,ll b,ll &x,ll &y) 2 { 3     if(b==0)   4     {   5           x=1;   6           y=0;   7           return a;   8     }   9     int gu=exgcd(b,a%b,x,y);  10     int t=x;  11     x=y;  12     y=t-a/b*y;  13     return gu;  14 15 }16 17 ll niyuan(ll hu)18 {19     x=0,y=0;20     ll tmp=exgcd(hu,p,x,y);21     return (x+p)%p;22 }23 24 ll C(ll k,ll m)25 {26     ll up=fac[k]%p;27     ll down=fac[m]%p*fac[k-m]%p;28     ll ans=up*niyuan(down)%p;29     return ans;30 }31 32 void pre()33 {34     fac[0]=1;35     for(int i=1;i<=n+1;i++)36         fac[i]=(ll)fac[i-1]*i%p;37 }

• 杨辉三角求组合数

1     C[0][0]=1;C[1][1]=1;2     for(int i=1;i<=n;i++) C[i][0]=1,C[i][i]=1;3     for(int i=1;i<=n;i++)4         for(int j=1;j<=i;j++)5             (C[i][j]=C[i-1][j]+C[i-1][j-1])%=moder;

 

数据结构

• $vector$实现普通平衡树 慎用！！！

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int n; 8 vector
         
          v; 9 10 int main()11 {12     scanf("%d",&n);13     for(int i=1;i<=n;i++)14     {15         int op=0,x=0;16         scanf("%d%d",&op,&x);17         if(op==1) v.insert(upper_bound(v.begin(),v.end(),x),x);18         else if(op==2) v.erase(lower_bound(v.begin(),v.end(),x));19         else if(op==3) printf("%d\n",lower_bound(v.begin(),v.end(),x)-v.begin()+1);20         else if(op==4) printf("%d\n",v[x-1]);21         else if(op==5) printf("%d\n",*--lower_bound(v.begin(),v.end(),x));22         else if(op==6) printf("%d\n",*upper_bound(v.begin(),v.end(),x));23     }24     return 0;25 }26 /*27 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：28 1. 插入x数29 2. 删除x数(若有多个相同的数，因只删除一个)30 3. 查询x数的排名(若有多个相同的数，因输出最小的排名)31 4. 查询排名为x的数32 5. 求x的前驱(前驱定义为小于x，且最大的数)33 6. 求x的后继(后继定义为大于x，且最小的数)34 */
         
        
       
      

图论

• Floyd算法。复杂度$O(n^3)$

1     memset(dis,0x3f,sizeof(dis)); 2     for(int i=1;i<=v;i++) dis[i][i]=0,dis[0][i]=0;//这一步很重要 3     for(int i=1;i<=e;i++) 4     { 5         int x=0,y=0,z=0; 6         scanf("%d%d%d",&x,&y,&z); 7         dis[x][y]=min(dis[x][y],z); 8         dis[y][x]=min(dis[y][x],z); 9     }10     for(int kk=1;kk<=v;kk++)11         for(int i=1;i<=v;i++)12             for(int j=1;j<=v;j++)13                 dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);

• Dijkstra+堆优化。复杂度$O(mlogn)$。稠密图优。好像不能用来跑最长路诶（

1 void dijkstra() 2 { 3     priority_queue
      
       
         >q; 4     memset(dis,0x3f,sizeof(dis)); 5     dis[s]=0;q.push(make_pair(0,s)); 6     while(!q.empty()) 7     { 8         int u=q.top().second;q.pop(); 9         if(vis[u]) continue;10         vis[u]=1;11         for(int i=head[u];i;i=edge[i].next)12         {13             int v=edge[i].to;14             if(dis[v]>dis[u]+edge[i].val)15             {16                 dis[v]=dis[u]+edge[i].val;17                 q.push(make_pair(-dis[v],v));18             }19         }20     }21 }
       
      

• spfa过世算法复杂度理解为$O(nm)$。但稀疏图$O(km)$。

1 void spfa() 2 { 3     memset(dis,0x3f,sizeof(dis)); 4     queue
      
       q; 5     q.push(s),vis[s]=1,dis[s]=0; 6     while(!q.empty()) 7     { 8         int u=q.front();q.pop(); 9         vis[u]=0;10         for(int i=head[u];i;i=edge[i].next)11         {12             int v=edge[i].to;13             if(dis[v]>dis[u]+edge[i].val)14             {15                 dis[v]=dis[u]+edge[i].val;16                 if(!vis[v]) q.push(v),vis[v]=1;17             }18         }19     }20 }
      

• 判断树上两路径是否相交

*　　题目：LuoguP3398仓鼠找sugar / 计蒜客NOIP提高组模拟一试T2 敌对势力 / hihocoder 11D（题目找不到了==可以看这位dalao的）

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define maxn 100090   6   7 using namespace std;  8   9 int n,m,tot,t; 10 int head[maxn],d[maxn],f[maxn][20]; 11 struct node{ 12     int to,next; 13 }edge[maxn*2]; 14  15 void add(int x,int y) 16 { 17     edge[++tot].to=y; 18     edge[tot].next=head[x]; 19     head[x]=tot; 20 } 21  22 void LCA_prework() 23 { 24     queue
          
           q; 25     q.push(1);d[1]=1; 26     while(!q.empty()) 27     { 28         int u=q.front();q.pop(); 29         for(int i=head[u];i;i=edge[i].next) 30         { 31             int v=edge[i].to; 32             if(d[v]) continue; 33             d[v]=d[u]+1; 34             f[v][0]=u; 35             for(int j=1;j<=t;j++) 36                 f[v][j]=f[f[v][j-1]][j-1]; 37             q.push(v); 38         } 39     } 40 } 41  42 int LCA(int x,int y) 43 { 44     if(d[x]>d[y]) swap(x,y); 45     for(int i=t;i>=0;i--) 46         if(d[f[y][i]]>=d[x]) y=f[y][i]; 47     if(x==y) return x; 48     for(int i=t;i>=0;i--) 49         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 50     return f[x][0]; 51 } 52  53 int main() 54 { 55     scanf("%d%d",&n,&m); 56     t=log2(n)+1; 57     for(int i=1;i<=n-1;i++) 58     { 59         int x=0,y=0; 60         scanf("%d%d",&x,&y); 61         add(x,y);add(y,x); 62     } 63     LCA_prework(); 64     for(int i=1;i<=m;i++) 65     { 66         int a=0,b=0,c=0,e=0; 67         scanf("%d%d%d%d",&a,&b,&c,&e); 68         int Chemist=LCA(a,b); 69         int cellur=LCA(c,e); 70         if(Chemist==cellur) 71         { 72             printf("NO\n"); 73             continue; 74         } 75         if(d[Chemist]>d[cellur]) 76         { 77             if(LCA(Chemist,c)==Chemist||LCA(Chemist,e)==Chemist) 78             {  79                 printf("NO\n"); 80                 continue; 81             } 82             else 83             {
    //没有相交输出yes  84                 printf("YES\n"); 85                 continue; 86             } 87         } 88         else 89         { 90             if(LCA(cellur,a)==cellur||LCA(cellur,b)==cellur) 91             { 92                 printf("NO\n"); 93                 continue; 94             } 95             else 96             { 97                 printf("YES\n"); 98                 continue; 99             }100         }101     }102     103     return 0;104 }
          
         
        
       
      

• 最短路计数

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int n,m,fake;int vis[2090],dis[2090];ll f[2090];int e[2090][2090];void spfa(){    memset(dis,63,sizeof(dis));    fake=dis[233];    queue
          
           q;    q.push(1);vis[1]=1;dis[1]=0;f[1]=1;    while(!q.empty())    {        int u=q.front();q.pop();        vis[u]=0;        if(u==n) continue;        for(int i=1;i<=n;i++)        {            if(dis[i]==dis[u]+e[u][i])                f[i]+=f[u];            if(dis[i]>dis[u]+e[u][i])            {                dis[i]=dis[u]+e[u][i];                f[i]=f[u];            }            if(f[i]&&!vis[i]) vis[i]=1,q.push(i);          }        f[u]=0;    }}int main(){    scanf("%d%d",&n,&m);    memset(e,63,sizeof(e));    for(int i=1;i<=m;i++)    {        int x=0,y=0,z=0;        scanf("%d%d%d",&x,&y,&z);        e[x][y]=min(e[x][y],z);    }    spfa();    if(fake==dis[n]) printf("No answer");    else printf("%d %lld",dis[n],f[n]);    return 0;}
          
         
        
       
      

以上是过世算法$spfa$，现在我来为大家表演一下$dijkstra$。（搬运逛公园的30部分分）dij不用清空，非常优秀。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 100090 6  7 using namespace std; 8 typedef long long ll; 9 10 int T,n,m,k,tot;11 int head[maxn];12 bool vis[maxn];13 ll moder,f[maxn],dis[maxn];14 struct node{15     int to,next,val;16 }edge[maxn<<2];17 18 void add(int x,int y,int z)19 {20     edge[++tot].to=y;21     edge[tot].next=head[x];22     head[x]=tot;23     edge[tot].val=z;24 }25 26 void Clear()27 {28     tot=0;29     memset(head,0,sizeof(head));30     memset(vis,0,sizeof(vis));31     memset(f,0,sizeof(f));32 }33 34 void dijkstra()35 {36     priority_queue
          
           
             >q;37 for(int i=1;i<=n;i++) dis[i]=3e9;38 q.push(make_pair(0,1));dis[1]=0;f[1]=1;39 while(!q.empty())40 {41 int u=q.top().second;q.pop();42 if(vis[u]) continue;43 vis[u]=1;44 for(int i=head[u];i;i=edge[i].next)45 {46 int v=edge[i].to;47 if(dis[v]>dis[u]+edge[i].val)48 {49 dis[v]=dis[u]+edge[i].val;50 q.push(make_pair(-dis[v],v));51 (f[v]=f[u])%=moder;52 }53 else if(dis[v]==dis[u]+edge[i].val)54 (f[v]+=f[u])%=moder;55 }56 }57 }58 59 int main()60 {61 scanf("%d",&T);62 while(T--)63 {64 scanf("%d%d%d%lld",&n,&m,&k,&moder);65 for(int i=1;i<=m;i++)66 {67 int x=0,y=0,z=0;68 scanf("%d%d%d",&x,&y,&z);69 add(x,y,z);70 }71 dijkstra();72 // if(dis[n]==3e9) printf("-1");73 printf("%lld\n",f[n]);74 //for(int i=1;i<=n;i++) printf("%lld ",dis[i]);75 Clear();76 }77 return 0;78 }
           
          
         
        
       
      

• kruskal算法求最小生成树：基于边。比较好理解，先对所有边进行排序，用并查集维护联通关系。复杂度为$O(mlogm)$。（其实不用找到n-1条边就退出...）

1 /* 2 最小生成树Kruskal算法 3 快排权值+并查集看是否连通 4 */  5 #include
      
        6 #include
       
         7  8 using namespace std; 9 10 int n,m,cnt,ans;11 int fa[5090];12 struct node{13     int f,t,w;14 }edge[400090];15 16 bool cmp(node a,node b)17 {18     return a.w
       
      

• Prim算法求最小生成树：基于点，逐步扩展。随便找一个点作为起点，设$dis$为添加了这个点需要增加的边权，然后每次在尚未被进入生成树的节点中寻找最小的$dis$，记录它的位置，这一次就把他加入生成树，并更新其他点的$dis$。复杂度$O(n^2)$。注意是否$vis$。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define maxn 5090 5  6 using namespace std; 7 typedef long long ll; 8  9 int n,m,tot;10 ll ans;11 int head[maxn],dis[maxn],vis[maxn];12 struct node{13     int to,next,val;14 }edge[400090];15 16 void add(int x,int y,int z)17 {18     edge[++tot].to=y;19     edge[tot].next=head[x];20     head[x]=tot;21     edge[tot].val=z;22 }23 24 void prim()25 {26     memset(dis,127,sizeof(dis));27     dis[1]=0;28     for(int k=1;k<=n;k++)29     {30         int u=-1,sta=0x3f3f3f3f;31         for(int i=1;i<=n;i++)32             if(dis[i]
        
       
      

• 树的直径方法一：两遍bfs/dfs【不能处理有负权边情况】【记录路径】

1 int bfs(int x) 2 { 3     queue
      
       q; 4     memset(d,0x3f,sizeof(d)); 5     memset(pre,0,sizeof(pre)); 6     fake=d[233]; 7     q.push(x);d[x]=0; 8     while(!q.empty()) 9     {10         int u=q.front();q.pop();11         for(int i=head[u];i;i=edge[i].next)12         {13             int v=edge[i].to;14             if(d[v]==fake) q.push(v),pre[v]=i,d[v]=d[u]+1;15         }16     }17     int top=x;18     for(int i=1;i<=n;i++)19         if(d[i]>d[top]) top=i;20     return top; 21 }22 int get_d()23 {24     p=bfs(1);25     p=bfs(p);26     return d[p];27 }
      

• 树的直径方法二：树形dp

1 void Treedp(int u) 2 { 3     vis[u]=1; 4     for(int i=head[u];i;i=edge[i].next) 5     { 6         int v=edge[i].to; 7         if(vis[v]) continue; 8         Treedp(v); 9         ans=max(ans,f[x]+f[y]+edge[i].val)10         f[x]=max(f[x],f[y]+edge[i].val);11     }12 }

• 强连通分量/缩点（in有向图）

1 void tarjan(int u) 2 { 3     dfn[u]=low[u]=++dfs_clock; 4     st.push(u); 5     for(int i=head[u];i;i=edge[i].next) 6     { 7         int v=edge[i].to; 8         if(!dfn[v]) 9         {10             tarjan(v);11             low[u]=min(low[u],low[v]);12         }13         else if(!scc[v]) low[u]=min(low[u],dfn[v]);14     }15     if(low[u]==dfn[u])16     {17         scc_cnt++;18         while(1)19         {20             int x=st.top();st.pop();21             scc[x]=scc_cnt;22             if(x==u) break;23         }24     }25 }26 —————————————————————————————————————27     for(int i=1;i<=n;i++)//在主程序中28         if(!dfn[i]) tarjan(i);29     for(int x=1;x<=n;x++)30         for(int i=head[x];i;i=edge[i].next)31         {32             int y=edge[i].to;33             if(scc[x]!=scc[y])34                 ADD(scc[x],scc[y]);35         }

• 树上倍增求LCA

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 500090 6  7 using namespace std; 8  9 int n,m,s,tot,t;10 int d[maxn],head[maxn],f[maxn][31];11 struct node{12     int to,next;13 }edge[maxn<<1];14 15 void add(int x,int y)16 {17     edge[++tot].to=y;18     edge[tot].next=head[x];19     head[x]=tot;20 }21 22 void init()23 {24     queue
          
           q;25     q.push(s);d[s]=1;26     while(!q.empty())27     {28         int u=q.front();q.pop();29         for(int i=head[u];i;i=edge[i].next)30         {31             int v=edge[i].to;32             if(d[v]) continue;33             d[v]=d[u]+1;34             f[v][0]=u;35             for(int j=1;j<=t;j++)36                 f[v][j]=f[f[v][j-1]][j-1];37             q.push(v);38         }39     }40 }41 42 int lca(int x,int y)43 {44     if(d[x]
           
            =0;i--) 46 if(d[f[x][i]]>=d[y]) x=f[x][i];47 if(x==y) return x;48 for(int i=t;i>=0;i--)49 if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];50 return f[x][0];51 }52 53 int main()54 {55 scanf("%d%d%d",&n,&m,&s);56 t=log2(n)+1;57 for(int i=1;i<=n-1;i++)58 {59 int x=0,y=0;60 scanf("%d%d",&x,&y);61 add(x,y),add(y,x);62 }63 init();64 for(int i=1;i<=m;i++)65 {66 int x=0,y=0;67 scanf("%d%d",&x,&y);68 printf("%d\n",lca(x,y));69 }70 return 0;71 }
           
          
         
        
       
      

字符串

• $trie$树

1 tot=0; 2 void insert() 3 { 4     int p=0; 5     int len=strlen(tmp+1); 6     for(int i=1;i<=len;i++) 7     { 8         int qwq=tmp[i]-'0'; 9         if(!trie[p][qwq]) trie[p][qwq]=++tot;10         p=trie[p][qwq];11     }12 }

•  最小表示法

1 void work() 2 { 3     n=strlen(str+1);ans=0; 4     for(int i=1;i<=n;i++) str[n+i]=str[i]; 5     int i=1,j=2,k; 6     while(i<=n&&j<=n) 7     { 8         for(k=0;k<=n&&str[i+k]==str[j+k];k++); 9         if(k>=n) break;10         if(str[i+k]>str[j+k])11         {i=i+k+1;if(i==j) i++;}12         else13         {j=j+k+1;if(i==j) j++;}14     }15     ans=min(i,j);16     printf("%d\n",ans);17 }18 //注意数组开二倍+

 

其他技巧

• 编译命令：-Wshadow -Wconversion  -Wextra / 打开wall警告开关
• 简单重载运算符：
• 更多有关$lowerbound$和$upperbound$：
• 生成数据前，一定要记得调用种子！！即（在挂文件后）

srand(time(NULL));

• 生成数据的批处理文件（$bat$）

1 @echo off 2 :loop 3  4 rand.exe 5  6 baoli.exe 7  8 sol.exe 9 10 fc baoli.out sol.out11 12 if not errorlevel 1 goto loop13 14 pause 15 16 goto loop

• 生成数据

1 int random(int lim)2 {3     return (unsigned long long)rand()*rand()%lim; 4 }5 6 7 调用时：int x=random(100)+1;

 

看到小数据范围：暴搜 全排列 二进制枚举  状压

$O(n^3)$：考虑枚举区间？