個(gè)人整理ACM模板.doc

1、0. 頭文件#define _CRT_SBCURE_NO_DEPRECATE#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int maxn = 110;1. const int INF = 0x3f3f3f3f ;經(jīng)典1.埃拉托斯特尼篩法專業(yè)資料/*| 埃式篩法 | 快速篩選素?cái)?shù) |16/11/05ztx|*/int primemaxn;bool is_primemaxn;i

2、nt sieve(int n)int p = 0;for (int i = 0; i = n; +i)is_primei =true ;is_prime 0 = is_prime 1 = false;for (int i = 2; i = n; +i)/注意數(shù)組大小是 nif(is_primei)primep+ = i;for(int j = i + i; j 0)if(n & 1) /判斷是否為奇數(shù)，若是則trueres = (res * x) % m;x = (x * x) % m;n =1;/相當(dāng)于 n /= 2;return res;專業(yè)資料3. 大數(shù)模擬大數(shù)加法/*| 大數(shù)模擬加法

3、| 用string模擬 |16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2)if (s1 = & s2 =) return 0;if (s1 =)returns2;if (s2 =)returns1;string maxx = s1, minn = s2;if (s1.length() = 0; -i)專業(yè)資料maxxa- += minni -0; /a一直在減， 額外還要減個(gè)0for (int i = maxx.length()- 1; i 0;-i)if (maxxi 9)maxxi -=10;/ 注意這個(gè)是

4、減 10maxxi - 1+;if (maxx 0 9)maxx 0 -= 10;maxx = 1 + maxx;return maxx;大數(shù)階乘/*| 大數(shù)模擬階乘 | 用數(shù)組模擬 |16/12/02ztx|專業(yè)資料*/#include #include using namespace std;typedef long long LL;const int maxn = 100010;int nummaxn, len;/*在mult 函數(shù)中，形參部分： len每次調(diào)用函數(shù)都會(huì)發(fā)生改變， n表示每次要乘以的數(shù)，最終返回的是結(jié)果的長(zhǎng)度tip:階乘都是先求之前的 (n-1)!來(lái)求 n!初始化 Ini

5、t 函數(shù)很重要，不要落下*/void Init() len = 1;專業(yè)資料num 0 = 1;int mult( int num, int len, int n) LL tmp = 0;for (LL i = 0; i len; +i) tmp = tmp + numi * n;/ 從最低位開(kāi)始，等號(hào)左邊的tmp 表示當(dāng)前位，右邊的 tmp 表示進(jìn)位（之前進(jìn)的位）numi = tmp %10; /保存在對(duì)應(yīng)的數(shù)組位置，即去掉進(jìn)位后的一位數(shù)tmp = tmp /10;/取整用于再次循環(huán) ,與n和下一個(gè)位置的乘積相加while (tmp) /之后的進(jìn)位處理numlen+ = tmp %10;tm

6、p = tmp /10;return len;int main() Init();專業(yè)資料int n;n = 1977; /求的階乘數(shù)for (int i = 2; i =0; -i)printf (%d ,numi);/從最高位依次輸出 ,數(shù)據(jù)比較多采用 printf 輸出printf (n );return 0;4.GCD/*| 輾轉(zhuǎn)相除法 | 歐幾里得算法 | 求最大公約數(shù) |16/11/05ztx|*/int gcd(int big, int small)專業(yè)資料if (small big) swap(big, small);int temp;while (small != 0) /輾

7、轉(zhuǎn)相除法if (small big) swap(big, small);temp = big % small;big = small;small = temp;return (big);5.LCM/*| 輾轉(zhuǎn)相除法 | 歐幾里得算法 | 求最小公倍數(shù) |16/11/05ztx|*/int gcd(int big, int small)if (small big) swap(big, small);專業(yè)資料int temp;while (small != 0) /輾轉(zhuǎn)相除法if (small big) swap(big, small);temp = big % small;big = small

8、;small = temp;return (big);6. 全排列/*| 求1到n的全排列 , 有條件 |16/11/05ztx, thanks to wangqiqi|*/void Pern(int list, int k, int n) /k表示前 k個(gè)數(shù)不動(dòng)僅移動(dòng)后面n-k位數(shù)if (k = n -1) for (int i = 0; i n; i+) printf (%d , listi);專業(yè)資料printf (n );else for (int i = k; i n; i+) /輸出的是滿足移動(dòng)條件所有全排列swap(listk, listi);Pern(list, k + 1,

9、n);swap(listk, listi);7. 二分搜索/*| 二分搜索 | 要求：先排序 | 16/11/ 05ztx, thanks to wangxiaocai|*/ left 為最開(kāi)始元素 , right 是末尾元素的下一個(gè)數(shù)， x是要找的數(shù)int bsearch(int * A, int left, int right, int x)專業(yè)資料int m ;while (left = x)right = m ;else left = m + 1;/如果要替換為upper_bound,改為 :if (Am = v) x =m+ 1; else y = m;return left ;/*

10、最后 left = right如果沒(méi)有找到 135577 找6，返回 7如果找有多少的 x，可以用 lower_bound 查找一遍，upper_bound查找一遍，下標(biāo)相減C+ 自帶的 lower_bound( a,a+n,x) 返回?cái)?shù)組中最后一個(gè) x的下一個(gè)數(shù)的地址upper_bound( a,a+n,x) 返回?cái)?shù)組中第一個(gè) x的地址專業(yè)資料如果 a+n 沒(méi)有找到 x或x的下一個(gè)地址，返回 a+n 的地址lower_bound( a,a+n,x ）-upper_bound( a,a+n,x) 返回?cái)?shù)組中 x的個(gè)數(shù)*/數(shù)據(jù)結(jié)構(gòu)并查集8. 并查集/*| 合并節(jié)點(diǎn)操作 |16/11/05ztx,

11、 thanks to chaixiaojun|*/int fathermaxn;/儲(chǔ)存 i的father 父節(jié)點(diǎn)void makeSet() for (int i = 0; i maxn; i+)fatheri = i;專業(yè)資料int findRoot( int x) /迭代找根節(jié)點(diǎn)int root = x;/根節(jié)點(diǎn)while (root != fatherroot) / 尋找根節(jié)點(diǎn) root = fatherroot;while (x != root) int tmp = fatherx;fatherx = root;/根節(jié)點(diǎn)賦值x = tmp;return root;void Union(

12、 int x, int y) /將x所在的集合和 y所在的集合整合起來(lái)形成一個(gè)集合。int a, b;a = findRoot(x);b = findRoot(y);fathera = b;/ y 連在 x的根節(jié)點(diǎn)上或fatherb = a 為x連在y的根節(jié)點(diǎn)上；專業(yè)資料/*在findRoot(x) 中：路徑壓縮 迭代 最優(yōu)版關(guān)鍵在于在路徑上的每個(gè)節(jié)點(diǎn)都可以直接連接到根上*/圖論MST最小生成樹(shù)Kruskal9. 克魯斯卡爾算法/*|Kruskal 算法 | 適用于稀疏圖 求最小生成樹(shù) |16/11/05ztx thanks to wangqiqi|*/*第一步：點(diǎn)、邊、加入vector ，把

13、所有邊按從小到大排序?qū)I(yè)資料第二步：并查集部分+ 下面的 code*/void Kruskal() ans = 0;for (int i =0; i len; i+) if (Find(edgei.a) != Find(edgei.b) Union(edgei.a, edgei.b);ans += edgei. len;Prim10.普里姆算法/*|Prim 算法 | 適用于稠密圖 求最小生成樹(shù) | 堆優(yōu)化版，時(shí)間復(fù)雜度：O(elgn)|16/11/05ztx, thanks to chaixiaojun|*/專業(yè)資料struct node int v, len;node( int v = 0

14、, int len = 0) :v(v), len(len) bool operator a.len;vector Gmaxn;int vismaxn;int dismaxn;void init() for (int i = 0; imaxn; i+) Gi.clear();disi = INF;visi =false;int Prim( int s) 專業(yè)資料priority_queueQ; / 定義優(yōu)先隊(duì)列 int ans = 0;Q.push(node(s, 0);/ 起點(diǎn)加入隊(duì)列while (!Q.empty() node now = Q.top(); Q.pop(); / 取出距離最

15、小的點(diǎn) int v = now.v;if (visv) continue ;/同一個(gè)節(jié)點(diǎn)，可能會(huì)推入2次或 2次以上隊(duì)列，這樣第一個(gè)被標(biāo)記后，剩下的需要直接跳過(guò)。visv =true ;/標(biāo)記一下ans += now.len;for (int i = 0; i len) disv2 = len;Q.push(node(v2, disv2);/更新的點(diǎn)加入隊(duì)列并排序return ans;專業(yè)資料Bellman-Ford單源最短路Dijkstra11.迪杰斯特拉算法/*|Dijkstra 算法 | 適用于邊權(quán)為正的有向圖或者無(wú)向圖| 求從單個(gè)源點(diǎn)出發(fā)，到所有節(jié)點(diǎn)的最短路| 優(yōu)化版：時(shí)間復(fù)雜度O(e

16、lbn)|16/11/05ztx, thanks to chaixiaojun|*/struct node int v, len;node( int v = 0, int len = 0) :v(v), len(len) bool operator a.len;專業(yè)資料;vector Gmaxn;bool vismaxn;int dismaxn;void init() for (int i = 0; imaxn; i+) Gi.clear();visi =false;disi = INF;int dijkstra( int s, int e) priority_queueQ;Q.push(no

17、de(s, 0); /加入隊(duì)列并排序diss = 0;while (!Q.empty() node now = Q.top();/取出當(dāng)前最小的Q.pop();int v = now.v;if (visv) continue ;/如果標(biāo)記過(guò)了 , 直接 continue專業(yè)資料visv =true ;for (int i = 0; i disv + len) disv2 = disv + len;Q.push(node(v2, disv2);return dise;SPFA12.最短路徑快速算法（Shortest Path Faster Algorithm）/*|SPFA算法 | 隊(duì)列優(yōu)化 |

18、 可處理負(fù)環(huán) |*/專業(yè)資料vector Gmaxn;bool inqueuemaxn;int distmaxn;void Init()for (int i = 0 ; i maxn ; +i)Gi.clear();disti = INF;int SPFA(int s,int e)int v1,v2,weight;queue Q;memset(inqueue, false,sizeof(inqueue); / 標(biāo)記是否在隊(duì)列中memset(cnt, 0,sizeof(cnt); / 加入隊(duì)列的次數(shù) dists = 0;Q.push(s); / 起點(diǎn)加入隊(duì)列inqueues =true ; /標(biāo)

19、記while (!Q.empty()v1 = Q.front();專業(yè)資料Q.pop();inqueuev1 =false; /取消標(biāo)記for (int i = 0 ; i distv1 + weight)/ 松弛操作distv2 = distv1 + weight;if(inqueuev2 =false)/再次加入隊(duì)列inqueuev2 =true;/cntv2+;/ 判負(fù)環(huán)/if(cntv2 n) return -1;Q.push(v2); return diste;/*不斷的將 s的鄰接點(diǎn)加入隊(duì)列，取出不斷的進(jìn)行松弛操作，直到隊(duì)列為空如果一個(gè)結(jié)點(diǎn)被加入隊(duì)列超過(guò)n-1次，那么顯然圖中有負(fù)環(huán)

20、專業(yè)資料*/Floyd-Warshall13.弗洛伊德算法/*|Floyd 算法 | 任意點(diǎn)對(duì)最短路算法 | 求圖中任意兩點(diǎn)的最短距離的算法|*/for (int i = 0; i n; i+) /初始化為 0for (int j = 0; j n; j+)scanf(%lf , &disij);for (int k = 0; k n; k+) for (int i = 0; i n; i+) for (int j = 0; j n; j+) disij =min (disij, disik + diskj);專業(yè)資料二分圖14.染色法/*| 交叉染色法判斷二分圖 |16/11/05ztx|*

21、/int bipartite( int s) int u, v;queueQ;colors =1;Q.push(s);while (!Q.empty() u = Q.front();Q.pop();for (int i = 0; i Gu.size(); i+) v = Gui;if (colorv =0) colorv = -coloru;Q.push(v);專業(yè)資料elseif (colorv = coloru)return 0;return 1;15.匈牙利算法/*| 求解最大匹配問(wèn)題 | 遞歸實(shí)現(xiàn) |16/11/05ztx|*/vector Gmaxn;bool inpathmaxn;

22、/標(biāo)記int matchmaxn;/記錄匹配對(duì)象void init()memset(match, - 1, sizeof(match);專業(yè)資料for (int i = 0; i maxn; +i) Gi.clear();bool findpath( int k) for (int i = 0; i Gk.size(); +i) int v = Gki;if (!inpathv) inpathv =true;if (matchv = -1 | findpath(matchv) /遞歸matchv = k;/即匹配對(duì)象是 “k妹子 ”的return true ;return false;void

23、 hungary() int cnt = 0;for (int i = 1; i = m; i+) / m 為需要匹配的 “妹子 ”數(shù)memset(inpath, false, sizeof(inpath); /每次都要初始化專業(yè)資料if (findpath(i) cnt+;cout cnt endl;/*| 求解最大匹配問(wèn)題 |dfs 實(shí)現(xiàn) |16/11/05ztx|*/int v1, v2;bool Map 501 501;bool visit 501;int link 501;int result;bool dfs(int x)for (int y = 1; y = v2; +y)if

24、(Mapxy & !visity)visity =true ;if (linky =0 | dfs(linky)專業(yè)資料linky = x;return true ; return false;void Search()for (int x = 1; x = cost; -i)dpi =max(dpi, dpi-cost+weight);/ 完全背包：void complete( int cost, int weight)for (i = cost ; i = v)專業(yè)資料complete(cost, weight);elsek = 1;while (k amount)bag01(k * co

25、st, k * weight);amount -= k;k += k;bag01(cost * amount, weight * amount);/ otherint dp 1000000 ;int c55, m 110;int sum;void CompletePack( int c) for (int v = c; v = c; -v) dpv =max(dpv, dpv - c + c);void multiplePack( int c, int m） if (m * c sum /2)CompletePack(c);elseint k = 1;while (k m)ZeroOnePac

26、k(k * c);m -= k;k =1;if (m != 0)ZeroOnePack(m * c);專業(yè)資料LIS19.最長(zhǎng)上升子序列/*| 最長(zhǎng)上升子序列 | 狀態(tài)轉(zhuǎn)移 |16/11/05ztx|*/*狀態(tài)轉(zhuǎn)移 dpi = max 1.dpj + 1 ;ji; ajai;di 是以 i結(jié)尾的最長(zhǎng)上升子序列與i之前的每個(gè) ajai 的 j的位置的最長(zhǎng)上升子序列+1后的值比較*/void solve()/參考挑戰(zhàn)程序設(shè)計(jì)入門經(jīng)典;for (int i = 0; i n; +i)dpi =1;專業(yè)資料for (int j = 0; j i; +j)if(aj ai)dpi = max(dpi,

27、dpj +1); /*優(yōu)化方法：dpi 表示長(zhǎng)度為 i+1的上升子序列的最末尾元素找到第一個(gè)比 dp末尾大的來(lái)代替*/void solve() for (int i = 0; i n; +i)dpi = INF;for (int i = 0; i n; +i) *lower_bound(dp, dp + n, ai) = ai;/返回一個(gè)指針printf (%dn , *lower_bound(dp, dp + n, INF) - dp;專業(yè)資料/*函數(shù) lower_bound() 返回一個(gè)iterator它指向在 first,last) 標(biāo)記的有序序列中可以插入value，而不會(huì)破壞容器順序

28、的第一個(gè)位置，而這個(gè)位置標(biāo)記了一個(gè)不小于value 的值。*/LCS20. 最長(zhǎng)公共子序列/*| 求最長(zhǎng)公共子序列 | 遞推形式 |16/11/05ztx|*/void solve() for (int i = 0; i n; +i) for (int j = 0; j m; +j) if (s1i = s2j) 專業(yè)資料dpi +1j +1= dpij + 1;else dpi +1j +1= max(dpij + 1, dpi + 1j); 計(jì)算幾何21.向量基本用法/*|16/11/06ztx|*/struct node double x; /橫坐標(biāo)double y; /縱坐標(biāo);type

29、def node Vector;Vector operator + (Vector A, Vector B) return Vector(A.x + B.x, A.y + B.y); 專業(yè)資料Vector operator - (Point A, Point B) return Vector(A.x - B.y, A.y - B.y); Vector operator * (Vector A, double p) return Vector(A.x*p, A.y*p); Vector operator / (Vector A, double p) return Vector(A.x / p,

30、A.y*p); double Dot(Vector A, Vector B) return A.x*B.x + A.y*B.y; /向量點(diǎn)乘double Length(Vector A) return sqrt(Dot(A, A); / 向量模長(zhǎng) double Angle(Vector A, Vector B) return acos(Dot(A, B) / Length(A) / Length(B); / 向量之間夾角double Cross(Vector A, Vector B) / 叉積計(jì)算 公式 return A.x*B.y - A.y*B.x;Vector Rotate(Vector

31、 A,double rad) /向量旋轉(zhuǎn)公式return Vector(A.x* cos(rad) - A.y* sin(rad), A.x* sin(rad) +A.y* cos(rad);專業(yè)資料Point getLineIntersection(Point P, Vector v, Point Q, Vector w) /兩直線交點(diǎn) t1 t2計(jì)算公式Vector u = P - Q;double t = Cross(w, u) / Cross(v, w); / 求得是橫坐標(biāo) return P + v*t; / 返回一個(gè)點(diǎn)22. 求多邊形面積/*|16/11/06ztx|*/node G

32、maxn;int n;double Cross(node a, node b) / 叉積計(jì)算 return a.x*b.y - a.y*b.x;int main()專業(yè)資料while (scanf(%d , &n) != EOF & n) for (int i = 0; i n; i+)scanf(%lf %lf , &Gi.x, &Gi.y);double sum = 0;Gn.x = G 0.x;Gn.y = G 0.y;for (int i = 0; i n; i+) sum += Cross(Gi, Gi +1);/ 或者/for (int i = 0; i n; i+) /sum += fun(Gi, G（