CSP2019前夕整理一下模板，順便供之后使用
1. 數(shù)據(jù)結(jié)構(gòu)
1.1. 虛樹
描述:
給定樹上的\(k\)個關(guān)鍵點，構(gòu)建出一棵虛樹，只有關(guān)鍵點和任意兩個關(guān)鍵點的LCA會被保留，且原樹上的祖先關(guān)系和虛樹上祖先關(guān)系保持一致。可以證明虛樹最多有\((2k-1)\)個點。
把所有關(guān)鍵點按DFS序排序，用一個棧維護(hù)動態(tài)加點連邊即可。時間復(fù)雜度\(O(k\log n)\).
注意事項:
一定要處理好最先加入棧中的點(所有點的LCA).
代碼:
addedge0_(u,v)表示在\(u\)和\(v\)之間連邊，邊權(quán)根據(jù)實際情況確定。
bool cmp(int x,int y) {return dfn[x]<dfn[y];}
void build()
{sort(ky+1,ky+kyn+1,cmp); rt = ky[1]; for(int i=2; i<=kyn; i++) rt = LCA(rt,ky[i]).first;tp = 1; stk[tp] = rt; n0++; kid[n0] = rt; isky[ky[1]] = true;for(int i=(rt==ky[1]?2:1); i<=kyn; i++){int u = ky[i],lca = LCA(stk[tp],u).first;if(lca==stk[tp]) {tp++; stk[tp] = u; n0++; kid[n0] = u; isky[u] = true;}else{while(tp>1 && dep[stk[tp-1]]>dep[lca]) {addedge0_(stk[tp],stk[tp-1]); tp--;}addedge0_(stk[tp],lca); tp--;if(stk[tp]!=lca){tp++; stk[tp] = lca; n0++; kid[n0] = lca;}tp++; stk[tp] = u; n0++; kid[n0] = u; isky[u] = true;}}while(tp>1){addedge0_(stk[tp],stk[tp-1]);tp--;}
}
1.2. 左偏樹
描述:
可并堆的一種實現(xiàn)，支持插入、刪除、合并、取最小值等堆操作，單個操作時間復(fù)雜度均不超過\(O(\log n)\).
代碼:
int merge(int u,int v)
{if(u==0||v==0) return u+v;if(val[u]>val[v]) swap(u,v);son[u][1] = merge(son[u][1],v);if(dis[son[u][1]]>dis[son[u][0]]) {swap(son[u][1],son[u][0]);}dis[u] = dis[son[u][1]]+1;return u;
}
void insert(int u,int x)
{siz++; val[siz] = x;rtn[u] = merge(rtn[u],siz);
}
int popnode(int u)
{return merge(son[u][0],son[u][1]);
}
1.3. KD樹
暫無
2. 字符串
2.1. 后綴數(shù)組
描述:
倍增法求后綴數(shù)組，時間復(fù)雜度\(O(n\log n)\).
sa[i]: 排在第\(i\)位的后綴
rk[i]: 后綴\(i\)的排名
h[i]: 后綴\(i\)與其前一名的后綴的LCP。
height[i]: 第\(i\)名與其前一名的后綴的LCP.
注意:
(1) w1處不可令h[1]=1然后從\(2\)開始循環(huán)。
代碼:
namespace SA
{int height[N+3],h[N+3],tmp[N+3],st[lgN+2][N+3],buc[N+3];void buildSA(){int *x = rk,*y = tmp;for(int i=1; i<=S; i++) buc[i] = 0;for(int i=1; i<=n; i++) buc[x[i]=a[i]]++;for(int i=1; i<=S; i++) buc[i] += buc[i-1];for(int i=n; i>=1; i--) sa[buc[x[i]]--] = i;int p = 0,s = S;for(int j=1; p<n; j<<=1){p = 0;for(int i=n-j+1; i<=n; i++) y[++p] = i;for(int i=1; i<=n; i++) {if(sa[i]>j) y[++p] = sa[i]-j;}for(int i=1; i<=s; i++) buc[i] = 0;for(int i=1; i<=n; i++) buc[x[y[i]]]++;for(int i=1; i<=s; i++) buc[i] += buc[i-1];for(int i=n; i>=1; i--) sa[buc[x[y[i]]]--] = y[i];p = 1; swap(x,y); x[sa[1]] = 1;for(int i=2; i<=n; i++) x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p:++p;s = p;}for(int i=1; i<=n; i++) rk[sa[i]] = i;for(int i=1; i<=n; i++) //w1{h[i] = h[i-1]==0?0:h[i-1]-1;while(i+h[i]<=n && sa[rk[i]-1]+h[i]<=n && a[i+h[i]]==a[sa[rk[i]-1]+h[i]]) {h[i]++;}}for(int i=1; i<=n; i++) height[i] = h[sa[i]];for(int i=1; i<=n; i++) st[0][i] = height[i];for(int j=1; j<lgN; j++){for(int i=1; i+(1<<j)-1<=n; i++) {st[j][i] = min(st[j-1][i],st[j-1][i+(1<<j-1)]);}}}int querymin(int l,int r){int g = lg2[r-l+1]; int *adr = st[g];return min(adr[l],adr[r-(1<<g)+1]);}int LCP(int x,int y){if(x==y) return n-x+1; if(rk[x]>rk[y]) swap(x,y);return querymin(rk[x]+1,rk[y]);}
}
using SA::buildSA;
using SA::LCP;
2.2. 擴展KMP
描述:
求出一個串的每個后綴與整個串的LCP. 與Manacher算法極其類似，時間復(fù)雜度\(O(n)\).
z[i]: 后綴\(i\)與母串的LCP長度。
代碼:
void Z_box()
{int mx = 0,mxid = 0; z[1] = m;for(int i=2; i<=m; i++){if(a[i]!=a[1]) {z[i] = 0;}else if(i>mx) {z[i] = 1;}else {z[i] = min(z[i-mxid+1],mx-i+1);}while(i+z[i]<=m && a[i+z[i]]==a[z[i]+1]) {z[i]++;}if(i+z[i]-1>mx) {mx = i+z[i]-1; mxid = i;}}
}
2.3. Manacher算法
描述:
求出以每個位置為中心的最長回文子串，時間復(fù)雜度\(O(n)\).
注意事項:
(1) 不要把\(2n+1\)寫成\(n\).
代碼:
void manacher()
{for(int i=n; i>=1; i--) a[2*i] = a[i];for(int i=1; i<=2*n+1; i+=2) a[i] = '#';int mxid = 1,mx = 1; p[1] = 1;for(int i=2; i<=2*n+1; i++){if(i>mx) {p[i] = 1;}else {p[i] = min(p[2*mxid-i],mx-i+1);}while(i-p[i]>0 && i+p[i]<=2*n+1 && a[i+p[i]]==a[i-p[i]]) {p[i]++;}if(i+p[i]-1>mx) {mx = i+p[i]-1; mxid = i;}}
}
2.4. 后綴自動機
描述:
增量法構(gòu)造后綴自動機，時間復(fù)雜度\(O(n)\).
注意廣義后綴自動機必須對Trie樹進(jìn)行BFS建立才能保證復(fù)雜度為節(jié)點數(shù)，否則復(fù)雜度退化為所有葉子節(jié)點總深度。
注意事項:
(1) 不要忘記初始化三個變量。
代碼:
void init()
{siz = lstpos = rtn = 1;
}
void insertchar(char ch)
{int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1; sz[np]++;for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}if(p==0) {fa[np] = rtn;}else{int q = son[p][ch];if(len[q]==len[p]+1) {fa[np] = q;}else{siz++; int nq = siz; len[nq] = len[p]+1;memcpy(son[nq],son[q],sizeof(son[q]));fa[nq] = fa[q]; fa[q] = fa[np] = nq;for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}}}
}
2.5. 回文自動機
描述:
一個字符串本質(zhì)不同的回文子串個數(shù)不超過\(n\). 回文自動機上一個節(jié)點代表一個回文子串。
增量法構(gòu)造回文自動機，時間復(fù)雜度\(O(n)\).
代碼:
void initPAM()
{siz = 1; fail[0] = fail[1] = 1; len[0] = 0; len[1] = -1; lstpos = 1;
}
void insertchar(int id)
{int p = lstpos;while(a[id-1-len[p]]!=a[id]) {p = fail[p];}if(!son[p][a[id]]){siz++; int u = siz,v = fail[p];while(a[id-1-len[v]]!=a[id]) {v = fail[v];}fail[u] = son[v][a[id]]; len[u] = len[p]+2; son[p][a[id]] = u;}lstpos = son[p][a[id]];
}
2.6. Lyndon分解
描述:
若一個串的最小循環(huán)表示為它本身，則稱作Lyndon串。
將一個串劃分為若干Lyndon串，稱作Lyndon劃分。一個串的Lyndon劃分方案唯一。
Lyndon劃分的Duval算法，時間復(fù)雜度\(O(n)\).
代碼:
暫無
2.7. 最小循環(huán)表示
暫無
3. 圖論
3.1. Tarjan算法
3.1.1. 強連通分量
描述:
Tarjan求有向圖的強連通分量。構(gòu)建DFS樹，統(tǒng)計每個點的DFS時間戳(dfn[u])以及其所到達(dá)的時間戳最小的點(low[u]), 若后者為該點本身，則求出一個極大強連通分量。時間復(fù)雜度\(O(n+m)\).
注意事項:
注意要從每個未遍歷的點出發(fā)進(jìn)行遍歷。
代碼:
void tarjan(int u)
{cnt++; dfn[u] = cnt; low[u] = cnt; ins[u] = true;tp++; sta[tp] = u;for(int i=fe0[u]; i; i=e0[i].nxt){if(!dfn[e0[i].v]) {tarjan(e0[i].v); low[u] = min(low[u],low[e0[i].v]);}else if(ins[e0[i].v]) low[u] = min(low[u],dfn[e0[i].v]);}if(low[u]==dfn[u]){num++; ca[num] = a[u];while(sta[tp]!=u){ins[sta[tp]] = false;clr[sta[tp]] = num;ca[num] += a[sta[tp]];tp--;}ins[u] = false; clr[u] = num; tp--;}
}
3.1.2. 點雙連通分量
描述:
Tarjan算法求無向圖的點雙連通分量。構(gòu)建DFS樹，low[u]的定義改為該點經(jīng)過至多一條非樹邊到達(dá)的最小的時間戳，若某個點\(u\)存在至少一個兒子\(v\)滿足\(low[v]\ge dfn[u]\), 則\(u\)是割點。時間復(fù)雜度\(O(n+m)\).
點雙連通分量一定是邊雙連通分量，割邊的兩個端點一定是割點。
代碼:
(建圓方樹)
namespace Graph
{const int N = 1e6;const int M = 4e6;struct Edge{int v,nxt;} e[(M<<1)+3];int fe[N+3];int fa[N+3];int dfn[N+3],low[N+3],stk[N+3];int n,en,cnt,tp;void addedge(int u,int v){en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en;}void Tarjan(int u){cnt++; dfn[u] = low[u] = cnt;tp++; stk[tp] = u;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==fa[u]) continue;if(!dfn[v]){fa[v] = u; Tarjan(v);low[u] = min(low[u],low[v]);if(low[v]>=dfn[u]){Tree::n++; Tree::addedge(u,Tree::n); Tree::addedge(Tree::n,u);while(tp>0){Tree::addedge(Tree::n,stk[tp]);Tree::addedge(stk[tp],Tree::n);tp--;if(stk[tp+1]==v) {break;}}}}else {low[u] = min(low[u],dfn[v]);}}}void buildTree(){Tree::n = n;for(int i=1; i<=n; i++) Tree::a[i] = 1;for(int i=1; i<=n; i++){if(!dfn[i]) {Tarjan(i);}}}
}
3.1.3. 邊雙連通分量
描述:
把點雙連通分量的\(\ge\)改成\(\gt\)即可。
代碼:
略。
3.2. 歐拉回路
3.2.1. 無向圖歐拉回路
描述:
若無向圖連通且度數(shù)為奇數(shù)的點個數(shù)不超過\(2\), 則存在歐拉回路。DFS時記錄回溯的路徑，即可構(gòu)造出一條歐拉回路，時間復(fù)雜度\(O(m)\).
注意事項:
(1) 一定要使用自殺式遍歷，否則時間復(fù)雜度退化為平方級。
代碼:
namespace Undirected
{struct Edge{int v,nxt;} e[M+2];int fe[N+2];int dgr[N+2];int ans[(N<<1)+2];bool vis[M+2];int n,m,en,tp;void addedge(int u,int v){en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en;dgr[u]++;}void dfs(int u){for(int i=fe[u]; i; i=fe[u]){fe[u] = e[i].nxt;if(vis[(i+1)>>1]) continue;vis[(i+1)>>1] = true;dfs(e[i].v);tp++; ans[tp] = (i&1) ? ((i+1)>>1) : -((i+1)>>1);}}void solve(){scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){int x,y;scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}for(int i=1; i<=n; i++){if(dgr[i]&1){printf("NO");return;}}tp = 0; dfs(e[1].v);if(tp<m) {printf("NO"); return;}printf("YES\n");for(int i=tp; i>=1; i--){printf("%d ",ans[i]);}}
}
3.2.2. 有向圖歐拉回路
描述:
有向圖中每個點入度等于出度是存在歐拉回路的必要條件。依然可以通過記錄回溯路徑的方法構(gòu)造歐拉回路。時間復(fù)雜度\(O(m)\).
代碼:
namespace Directed
{struct Edge{int v,nxt;} e[M+2];int fe[N+2];int ind[N+2];int oud[N+2];int ans[(N<<1)+2];bool vis[M+2];int n,m,en,tp;void addedge(int u,int v){en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en;oud[u]++; ind[v]++;}void dfs(int u){for(int i=fe[u]; i; i=fe[u]){fe[u] = e[i].nxt;if(vis[i]) continue;vis[i] = true;dfs(e[i].v);tp++; ans[tp] = i;}}void solve(){scanf("%d%d",&n,&m); tp = 0;for(int i=1; i<=m; i++){int x,y; scanf("%d%d",&x,&y);addedge(x,y);}for(int i=1; i<=n; i++){if(ind[i]!=oud[i]) {printf("NO"); return;}}dfs(e[1].v);if(tp<m) {printf("NO"); return;}printf("YES\n");for(int i=tp; i>=1; i--) printf("%d ",ans[i]);}
}
4. 數(shù)論
4.1. 擴展歐幾里得算法
描述:
求解不定方程\(ax+by=\gcd(a,b)\). 時間復(fù)雜度\(O(\log(a+b))\).
代碼:
llong exgcd(llong a,llong b,llong &x,llong &y)
{if(b==0) {x = 1,y = 0; return x;}llong nx,ny; llong ret = exgcd(b,a%b,nx,ny);x = ny; y = nx-a/b*ny;return ret;
}
4.2. 擴展中國剩余定理
描述:
求解同余方程組，模數(shù)可以不互質(zhì)。具體做法是將模數(shù)不互質(zhì)的方程進(jìn)行合并。
代碼:
暫無
4.3. 擴展BSGS
暫無
4.4. 二次剩余之Cipolla算法
暫無
5. 多項式
暫無
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖
總結(jié)
以上是生活随笔為你收集整理的【学习笔记】OI模板整理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
