算法模板整理
时间：2018-10-17 11:24:01
手机看文章
扫描二维码
随时随地手机看文章
[导读]ll exmod[100005],rmod[100005];
ll multimod(ll a,ll b,ll mod)
{
ll ans = 0;
for ( ; b; b >
ll exmod[100005],rmod[100005];
ll multimod(ll a,ll b,ll mod)
{
ll ans = 0;
for ( ; b; b >>= 1, a = (a<>=1;
}
return res;
}
void Init()
{
memset(exmod,0,sizeof(exmod));
exmod[0]=1;
for(int i=1; i<100005; i++)
exmod[i]=(exmod[i-1]*i)%INF;
for(int i=1; iN)return 0;
if(K==N)return 1;
if(K==0)return 1;
return (((exmod[N]*rmod[K])%INF)*rmod[N-K])%INF;
}///kmp
#define M 1000010
char s[M],t[M];
int next[M],sum;
void getNext()//求next数组
{
int i,j;
next[0]=-1;
for(i=1,j=-1;s[i];i++){
while(j!=-1&&s[i]!=s[j+1])j=next[j];//从s[j+1]开始找与s[i]相同的字母
if(s[j+1]==s[i])j++;
next[i]=j;//如果找到相同字母，next[i]记录此位置,否则next[i]=next[i-1]
}
}
void kmp()
{
int i,j;
sum=0;
getNext();
for(i=0,j=-1;t[i];i++){
while(j!=-1&&s[j+1]!=t[i])j=next[j];//按next[j]后退找出与t[i]相同的s[j+1]
if(s[j+1]==t[i])j++;//如果找到则向后前进
if(!s[j+1]){//如果在t中找到完整的s
sum++;//计数增1
j=next[j];//按next后退
}
}
}///rmp 预处理 比线段树快
void rmq_init()
{
int i,j,k,m;
m=(int)(log(n)/log(2.0));
for(i=1; i<=n; i++)
{
mx[i][0]=mm[i][0]=A[i];
}
for(j=1; j<=m; j++)
{
for(i=1; i<=n; i++)
{
mx[i][j]=mx[i][j-1];
k=1<<(j-1);
if(i+k<=n)
mx[i][j]=max(mx[i][j],mx[i+k][j-1]);
}
}
for(j=1; j<=m; j++)
{
for(i=1; i<=n; i++)
{
mm[i][j]=mm[i][j-1];
k=1<<(j-1);
if(i+k<=n)
mm[i][j]=min(mm[i][j],mm[i+k][j-1]);
}
}
}
int rmq_query(int l,int r)
{
int i,j,m;
m=(int)(log(r-l+1)/log(2.0));
i=max(mx[l][m],mx[r-(1<<m)+1][m]);
j=min(mm[l][m],mm[r-(1<<m)+1][m]);
return i-j;
}///输出串中最对称最长的对称长度
int f(char *gg){
int maxlen = 1;//最大长度
int len=strlen(gg);
int record[len];//存包含该位及前个元素最长对称子串
record[0]=1;
int i=1;
for(;i=0 && gg[i] == gg[i-record[i-1]-1]){
max = max>(record[i-1] + 2)? max:(record[i-1] +2);
}
int k = 1;
while(gg[i] == gg[i-k]){
k++;
}
max = max>k? max:k;
record[i] = max;
if(record[i]>maxlen) maxlen=record[i];
}
return maxlen;
}///编辑距离
首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式：
if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
for(i=0;i<len1;i++){
dp[i][0] = i ;
}
for(j=0;j<len2;j++){
dp[0][j] = j ;
}
for(i=1;i<=len1;i++){
for(j=1;j<=len2;j++){
if(str1[i-1] == str2[j-1]){
dp[i][j] = dp[i-1][j-1]; //对应字母相等，dp值不增加
}
else{//三个形参分别对应str2在str1的基础上增加，减少和修改的情况
dp[i][j] = min( dp[i][j-1]+1 , dp[i-1][j]+1 , dp[i-1][j-1]+1 );
}
}
}
return dp[len1][len2];单元最短路径
Bellman-Ford 算法
记从起点S出发到顶点i的最短距离为d[i]
d[i]=min {d[i],d[j]+e(j,i)}
记当前到顶点i的最短路长度为d[i]
并设初值d[s]=0,d[i]=INF
再不断使用 上面的公式更新d的值
从顶点from指向顶点to的cost值
const int MAX_E=1000;
const int MAX_V=1000;
struct edge
{
int from;
int to;
int cost;
};
edge es[MAX_E];//边
int d[MAX_E];//最短距离
int V;//顶点数
int E;//边数
//求解从顶点S出发到所有点的最短距离
void shortest_path(int s)
{
for(int i=0; i<V; i++)
d[i]=INF;
d[s]=0;
while(true)
{
bool update=false;
for(int i=0; id[e.from]+e.cost) //精华
{
d[e.to]=d[e.from]+e.cost;
update=true;
}
}
if(!update)
break;
}
}单元最短路径
priority_queue优化的Dijkstra
const int MAX_E=1000;
const int MAX_V=1000;
struct edge
{
int to;
int cost;
};
typedef pairP;//first是最短距离，second是顶点编号
int V;
VectorG[MAX_V];
int d[MAX_V];
void Dijkstra(int s)
{
//通过指定greater的参数，堆按照从小到达的顺序取出值
priority_queue<P, vector, greater> que;
fill(d,d+V,INF);
d[s]=0;
que.push(P(0,s));
while(!que.empty())
{
P p = que.top();
que.pop();
int v=p.second;
if(d[v]<p.first)
continue;
for(int i=0; id[v]+e.cost)
{
d[e.to]=d[v]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}最小生成树 Spanning tree
Prim 算法
首先，我们假设有一颗只包含一个顶点V的树T
然后，贪心地选取T和其他顶点之间项链的最小权值的边
并把它加入到T中
不断的进行这个操作，就可以得到一个Spanning tree 了
const int MAX_E=1000;
const int MAX_V=1000;
int cost[MAX_V][MAX_V];
int mincost[MAX_V];//从顶点X出发的边到每个顶点的最小权值
bool used[MAX_V];//顶点i是否包含在集合X中
int V;//顶点数
int Prim()
{
for(int i=0; i<V; i++)
{
mincost[i]=INF;
used[i]=false;
}
mincost[0]=0;
int res=0;
while(true)
{
int v=-1;//从不属于X的顶点集合中选择X到其权值最小的顶点
for(int u=0; u<V; u++)
{
if(!used[u]&&(v==-1||mincost[u]<mincost[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;//把顶点v加入到X
res+=mincost[v];//把边的长度加入到结果里
for(int u=0; u<V; u++)
{
mincost[u]=min(mincost[u],cost[v][u]);
}
}
return res;
}Kruskal 算法
按照边的权值的顺序从小到大查看一遍
如果不产生圈（重边也算在内）
就把当前这条边加入到生成树中
如何判断是否产生圈
假设现在要把连接顶点u和v的边e加入到生成树中。
如果加入之前u和v不在同一个连通分量里，
那么加入e也不会产生圈
反之，如果u和v在同一个连通分量里
那么一定会产生圈
可以使用并查集高效地判断是否属于同一个连通分量
const int MAX_E=1000;
const int MAX_V=1000;
struct edge
{
int u;
int v;
int cost;
};
bool cmp(edge e1,edge e2)
{
return e1.cost<e2.cost;
}
edge es[MAX_E];
int V,E;//顶点数和边数
int set[MAX_V];//并查集
void init_union_find(int n)
{
for(int i=0; i<n; i++)
set[i]=i;
}
void find(int x)
{
if(set[x]==x)
return x;
else
return set[x]=find(set[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
if(yx)
set[y]=x;
}
bool same(int x,int y)
{
return find(x)==find(y);
}
int kruskal()
{
sort(es,es+E,cmp);//从小到大排序
init_union_find(V);//并查集初始化
int res=0;
for(int i=0; i<E; i++)
{
edge e=es[i];
if(same(e.u,e.v))
{
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}//定义结构，使用运算符重载,自定义优先级1
struct cmp1{
bool operator ()(int &a,int &b){
return a>b;//最小值优先
}
};
struct cmp2{
bool operator ()(int &a,int &b){
return a<b;//最大值优先
}
};
//定义结构，使用运算符重载,自定义优先级2
struct number1{
int x;
bool operator < (const number1 &a) const {
return x>a.x;//最小值优先
}
};
struct number2{
int x;
bool operator < (const number2 &a) const {
return x<a.x;//最大值优先
}
};
priority_queueque;//采用默认优先级构造队列
priority_queue<int,vector,cmp1>que1;//最小值优先
priority_queue<int,vector,cmp2>que2;//最大值优先
priority_queue<int,vector,greater>que3;//注意“>>”会被认为错误，
//这是右移运算符，所以这里用空格号隔开
priority_queue<int,vector,less>que4;////最大值优先
priority_queueque5;
priority_queueque6;匈牙利算法 求最大匹配
bool find(int x)
{
int i,j;
for (j=1;j<=m;j++)
{ //扫描每个妹子
if (line[x][j]==true && used[j]==false)
//如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）
{
used[j]=1;
if (girl[j]==0 || find(girl[j]))
{
//名花无主或者能腾出个位置来，这里使用递归
girl[j]=x;
return true;
}
}
}
return false;
}
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //这个在每一步中清空
if find(i) all+=1;
}
下载文档
