快速幂取模
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<n;i++)
for(int j=v;j>=size[i];j--)
{
dp[j]=max(dp[j],dp[j-size[i]]+value[i]);
}
cout<<dp[v]<<endl;
}完全背包（每种物品有无穷多）
void complete()
{
for(int i=0;i<n;i++)
for(int j=size[i];j<=v;j++)
{
dp[j]=max(dp[j],dp[j-size[i]]+value[i]);
}
cout<<dp[v]<<endl;
}多重背包（每种物品数量有限）
//n 物品数量，v 背包容量
//size 单个物品体积，value 单个物品价值，num 该物品的数量
void multiply()
{
for(int i=0;i<n;i++)
{
int d1=1,d2=num[i];
while(d1<d2)
{
for(int j=v;j>=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<<dp[v]<<endl;
}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<n) //调用递归
dfs(step + 1); //即相当于再一次从头执行一个dfs函数，可以理解为一个嵌套
else
{
for(int i=1;i<=n;i++)
{
printf("%d",ans[i]);
if(i!=n) //用于控制输出格式
printf(" ");
else
printf("
");
}
}
vis[i]=0; //访问完毕返回标记为可访问
//只有当输出了一个结果后才有可能执行
}
}
}
int main()
{
memset(vis,0,sizeof(vis));
step=0;
scanf("%d",&n);
dfs(1);
return 0;
}1~n全排列（利用STL）
void Full(int n)
{
for(int i=0;i<n;i++) a[i]=i+1;
do
{
for(int i=0;i<n;i++)
{
if(i!=0) cout<<" ";
cout<<a[i];
}
cout<<"
";
}
while(next_permutation(a,a+n));
}最长递增子序列
int a[maxn];
int dp[maxn];
int n;
void longest()
{
dp[0]=a[0];
int pos;
int L=1;
for(int i=0;i<n;i++)
{
pos=lower_bound(dp,dp+L,a[i])-dp;
dp[pos]=a[i];
L=max(L,pos+1);
}
cout<<L<<endl;
}DFS模板
void dfs()//参数用来表示状态
{
if(到达终点状态)
{
...//根据题意来添加
return;
}
if(越界或者是不符合法状态)
return;
for(扩展方式)
{
if(扩展方式所达到状态合法)
{
....//根据题意来添加
标记；
dfs（）；
修改（剪枝）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}
}
}判断1~1e9之内的数是不是素数
//是素数prime(n)==true
bool prime(int n)
{
for(int i=2;i*i<=n;i++)
if(n%i==0)
return false;
return n!=1;
}
vector<int> divisor(int n)
{
vector<int> 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<int,int> factor(int n)
{
map<int,int> 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<vis[i]+i)
{
id=i;
mx=vis[i]+i;
}
ans=max(ans,vis[i]);
}
printf("%d
",ans-1);
} To be continued...