快速幂取模

int Pow(int a,int b,int c){	int res=1;	while(b>0)	{		if(b&1) res=res*a%c;		a=a*a%c;		b>>=1;	}	return res;}//复杂度O(logn)

gcd

int gcd(int a,int b){	return b==0?a:gcd(b,a%b);}

扩展欧几里得（递归）

int exgcd(int a,int b,int &x,int &y){    if(b==0)    {        x=1;        y=0;        return a;    }    int r=exgcd(b,a%b,x,y);    int t=x;    x=y;    y=t-a/b*y;    return r;}

递归实现n！

int fact(int n){	/*if(n==0||n==1) return 1;	else return n*fact(n-1);*/	return n==0?1:fact(n-1)*n;//上面注释的简化版 }

背包类

01背包（每种物品只有一个）

//n 物品数量，v 背包容量 //size 单个物品体积，value 单个物品价值void bag01(){	for(int i=0;i
    
     =size[i];j--)	{		dp[j]=max(dp[j],dp[j-size[i]]+value[i]);	}	cout<
     
      <
     
    

完全背包（每种物品有无穷多）

void complete(){	for(int i=0;i

多重背包（每种物品数量有限）

//n 物品数量，v 背包容量 //size 单个物品体积，value 单个物品价值，num 该物品的数量 void multiply(){	for(int i=0;i
    
     =d1*size[i];j--)              {                  dp[j]=max(dp[j],dp[j-d1*size[i]]+value[i]*d1);              }              d2-=d1;              d1*=2;          }          for(int j=v;j>=d2*size[i];j--) dp[j]=max(dp[j],dp[j-d2*size[i]]+value[i]*d2);      }     cout<
     
      <
     
    

1~n全排列（递归实现）

int vis[10];//用于标记是否被访问过，0--未访问  1--已访问int ans[10];//用于存储答案int step,n;void dfs(int step){    for(int i=1;i<=n;i++)    {        if(vis[i]==0)        {            vis[i]=1;            ans[step]=i;//将答案存储            if(step

1~n全排列（利用STL）

void Full(int n){	for(int i=0;i

最长递增子序列

int a[maxn];int dp[maxn];int n;void longest(){	dp[0]=a[0];	int pos;	int L=1;	for(int i=0;i

DFS模板

void dfs()//参数用来表示状态{    if(到达终点状态)    {        ...//根据题意来添加        return;    }    if(越界或者是不符合法状态)        return;    for(扩展方式)    {        if(扩展方式所达到状态合法)        {            ....//根据题意来添加            标记；            dfs（）；            修改（剪枝）；            (还原标记)；            //是否还原标记根据题意            //如果加上（还原标记）就是 回溯法        }            }}

判断1~1e9之内的数是不是素数

//是素数prime(n)==truebool prime(int n)  {      for(int i=2;i*i<=n;i++)          if(n%i==0)              return false;      return n!=1;  }  vector
    
      divisor(int n)  {      vector
     
       res;      for(int i=1;i*i<=n;i++)      {          if(n%i==0)          {              res.push_back(i);              if(i!=n/i) res.push_back(n/i);          }      }      return res;  }  map
      
        factor(int n)  {      map
       
         res;      for(int i=2;i*i<=n;i++)      {          while(n%i==0)          {              ++res[i];              n/=i;          }          if(n!=1) res[n]=1;          return res;      }  }
       
      
     
    

Warshall算法求传递闭包（O(n^3)）

void Warshall(){	for(int i=1;i<=n;i++)	{		for(int j=1;j<=n;j++)		{			if(a[j][i])			{				for(int k=0;k<=n;k++)				{					a[j][k]=a[j][k]|a[i][k];				}			}		}	}}

最长回文子串长度（Manacher算法）

//复杂度O(n) void Manacher()  {      l=strlen(ch);      //处理字符串，在字符串开头，结尾都加上'#'       for(int i=l;i>0;i--)//注意是从最后一位开始处理       {          ch[2*i]=ch[i-1];          ch[2*i+1]='#';      }      ch[0]='$';//避免出现越界问题       ch[1]='#';      int id,mx,ans;//id最大回文子串中心的位置，mx最大回文子串的边界       id=mx=ans=0;      for(int i=1;i<=2*l+1;i++)      {          if(mx>i) vis[i]=min(vis[2*id-i],mx-i);            else vis[i]=1;            while(ch[i+vis[i]]==ch[i-vis[i]]) vis[i]++;            if(mx

To be continued...