算法模板整理
[導(dǎo)讀]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數(shù)組
{
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++;//如果找到則向后前進(jìn)
if(!s[j+1]){//如果在t中找到完整的s
sum++;//計數(shù)增1
j=next[j];//按next后退
}
}
}///rmp?預(yù)處理?比線段樹快
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;
}///編輯距離
首先定義這樣一個函數(shù)——edit(i,?j)，它表示第一個字符串的長度為i的子串到第二個字符串的長度為j的子串的編輯距離。
顯然可以有如下動態(tài)規(guī)劃公式：
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)?}，當(dāng)?shù)谝粋€字符串的第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]; //對應(yīng)字母相等，dp值不增加
}
else{//三個形參分別對應(yīng)str2在str1的基礎(chǔ)上增加，減少和修改的情況
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出發(fā)到頂點i的最短距離為d[i]
d[i]=min?{d[i],d[j]+e(j,i)}
記當(dāng)前到頂點i的最短路長度為d[i]
并設(shè)初值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;//頂點數(shù)
int?E;//邊數(shù)
//求解從頂點S出發(fā)到所有點的最短距離
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優(yōu)化的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的參數(shù)，堆按照從小到達(dá)的順序取出值
????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?算法
首先，我們假設(shè)有一顆只包含一個頂點V的樹T
然后，貪心地選取T和其他頂點之間項鏈的最小權(quán)值的邊
并把它加入到T中
不斷的進(jìn)行這個操作，就可以得到一個Spanning?tree?了
const?int?MAX_E=1000;
const?int?MAX_V=1000;
int?cost[MAX_V][MAX_V];
int?mincost[MAX_V];//從頂點X出發(fā)的邊到每個頂點的最小權(quán)值
bool?used[MAX_V];//頂點i是否包含在集合X中
int?V;//頂點數(shù)
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到其權(quán)值最小的頂點
????????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];//把邊的長度加入到結(jié)果里
????????for(int?u=0;?u<V;?u++)
????????{
????????????mincost[u]=min(mincost[u],cost[v][u]);
????????}
????}
????return?res;
}Kruskal?算法
按照邊的權(quán)值的順序從小到大查看一遍
如果不產(chǎn)生圈（重邊也算在內(nèi)）
就把當(dāng)前這條邊加入到生成樹中
如何判斷是否產(chǎn)生圈
假設(shè)現(xiàn)在要把連接頂點u和v的邊e加入到生成樹中。
如果加入之前u和v不在同一個連通分量里，
那么加入e也不會產(chǎn)生圈
反之，如果u和v在同一個連通分量里
那么一定會產(chǎn)生圈
可以使用并查集高效地判斷是否屬于同一個連通分量
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;//頂點數(shù)和邊數(shù)
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;
}//定義結(jié)構(gòu)，使用運(yùn)算符重載,自定義優(yōu)先級1??
struct?cmp1{??
????bool?operator?()(int?&a,int?&b){??
????????return?a>b;//最小值優(yōu)先??
????}??
};??
struct?cmp2{??
????bool?operator?()(int?&a,int?&b){??
????????return?a<b;//最大值優(yōu)先??
????}??
};??
//定義結(jié)構(gòu)，使用運(yùn)算符重載,自定義優(yōu)先級2??
struct?number1{??
????int?x;??
????bool?operator?<?(const?number1?&a)?const?{??
????????return?x>a.x;//最小值優(yōu)先??
????}??
};??
struct?number2{??
????int?x;??
????bool?operator?<?(const?number2?&a)?const?{??
????????return?x<a.x;//最大值優(yōu)先??
????}??
};??
priority_queueque;//采用默認(rèn)優(yōu)先級構(gòu)造隊列??
??
????priority_queue<int,vector,cmp1>que1;//最小值優(yōu)先??
????priority_queue<int,vector,cmp2>que2;//最大值優(yōu)先??
??
????priority_queue<int,vector,greater>que3;//注意“>>”會被認(rèn)為錯誤，??
??????????????????????????????????????????????????????//這是右移運(yùn)算符，所以這里用空格號隔開??
????priority_queue<int,vector,less>que4;////最大值優(yōu)先??
??
????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)??????????
????????//如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題，但是沒有成功，所以就不用瞎費(fèi)工夫了）????
????????{????
????????????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;????
}
?
?
?
?
?
?
下載文檔
