版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上0. 頭文件#define _CRT_SBCURE_NO_DEPRECATE#include <set>#include <cmath>#include <queue>#include <stack>#include <vector>#include <string>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorith
2、m>#include <functional>using namespace std;const int maxn = 110;1. const int INF = 0x3f3f3f3f;經(jīng)典1.埃拉托斯特尼篩法/* |埃式篩法| |快速篩選素?cái)?shù)| |16/11/05ztx|*/int primemaxn; bool is_primemaxn;int sieve(int n) int p = 0; for(int i = 0; i <= n; +i) is_primei = true; is_prime0 = is_prime1 = false; for (int i
3、= 2; i <= n; +i) / 注意數(shù)組大小是n if(is_primei) primep+ = i; for(int j = i + i; j <= n; j += i) / 輕剪枝,j必定是i的倍數(shù) is_primej = false; return p; / 返回素?cái)?shù)個(gè)數(shù)2.快速冪/* |快速冪| |16/11/05ztx|*/typedef long long LL; / 視數(shù)據(jù)大小的情況而定LL powerMod(LL x, LL n, LL m) LL res = 1; while (n > 0) if (n & 1) / 判斷是否為奇數(shù),若是則tr
4、ue res = (res * x) % m; x = (x * x) % m; n >>= 1; / 相當(dāng)于n /= 2; return res;3.大數(shù)模擬大數(shù)加法/* |大數(shù)模擬加法| |用string模擬| |16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2) if (s1 = "" && s2 = "") return "0" if (s1 = "") return s2; if (s2 = &q
5、uot;") return s1; string maxx = s1, minn = s2; if (s1.length() < s2.length() maxx = s2; minn = s1; int a = maxx.length() - 1, b = minn.length() - 1; for (int i = b; i >= 0; -i) maxxa- += minni - '0' / a一直在減 , 額外還要減個(gè)'0' for (int i = maxx.length()-1; i > 0;-i) if (maxxi &
6、gt; '9') maxxi -= 10;/注意這個(gè)是減10 maxxi - 1+; if (maxx0 > '9') maxx0 -= 10; maxx = '1' + maxx; return maxx;大數(shù)階乘/* |大數(shù)模擬階乘| |用數(shù)組模擬| |16/12/02ztx|*/#include <iostream>#include <cstdio>using namespace std;typedef long long LL;const int maxn = ;int nummaxn, len;/* 在mu
7、lt函數(shù)中,形參部分:len每次調(diào)用函數(shù)都會(huì)發(fā)生改變,n表示每次要乘以的數(shù),最終返回的是結(jié)果的長(zhǎng)度 tip: 階乘都是先求之前的(n-1)!來求n! 初始化Init函數(shù)很重要,不要落下*/void Init() len = 1; num0 = 1;int mult(int num, int len, int n) LL tmp = 0; for(LL i = 0; i < len; +i) tmp = tmp + numi * n; /從最低位開始,等號(hào)左邊的tmp表示當(dāng)前位,右邊的tmp表示進(jìn)位(之前進(jìn)的位) numi = tmp % 10; / 保存在對(duì)應(yīng)的數(shù)組位置,即去掉進(jìn)位后的一
8、位數(shù) tmp = tmp / 10; / 取整用于再次循環(huán),與n和下一個(gè)位置的乘積相加 while(tmp) / 之后的進(jìn)位處理 numlen+ = tmp % 10; tmp = tmp / 10; return len;int main() Init(); int n; n = 1977; / 求的階乘數(shù) for(int i = 2; i <= n; +i) len = mult(num, len, i); for(int i = len - 1; i >= 0; -i) printf("%d",numi); / 從最高位依次輸出,數(shù)據(jù)比較多采用printf
9、輸出 printf("n"); return 0;4.GCD/* |輾轉(zhuǎn)相除法| |歐幾里得算法| |求最大公約數(shù)| |16/11/05ztx|*/int gcd(int big, int small) if (small > big) swap(big, small); int temp; while (small != 0) / 輾轉(zhuǎn)相除法 if (small > big) swap(big, small); temp = big % small; big = small; small = temp; return(big);5.LCM/* |輾轉(zhuǎn)相除法|
10、|歐幾里得算法| |求最小公倍數(shù)| |16/11/05ztx|*/int gcd(int big, int small) if (small > big) swap(big, small); int temp; while (small != 0) / 輾轉(zhuǎn)相除法 if (small > big) swap(big, small); temp = big % small; big = small; small = temp; return(big);6.全排列/* |求1到n的全排列, 有條件| |16/11/05ztx, thanks to wangqiqi|*/void Per
11、n(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); printf("n"); else for (int i = k; i < n; i+) / 輸出的是滿足移動(dòng)條件所有全排列 swap(listk, listi); Pern(list, k + 1, n); swap(listk, listi); 7.二分搜索/* |二分搜索| |要求:先排序| |16/11/05ztx,
12、 thanks to wangxiaocai|*/ left為最開始元素, right是末尾元素的下一個(gè)數(shù),x是要找的數(shù)int bsearch(int *A, int left, int right, int x) int m; while (left < right) m = left + (right - left) / 2; if (Am >= x) right = m; else left = m + 1; / 如果要替換為 upper_bound, 改為:if (Am <= v) x = m+1; else y = m; return left;/* 最后left
13、= right 如果沒有找到找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的地址 如果a+n內(nè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, thanks to chaixiaojun|*/int father
14、maxn; / 儲(chǔ)存i的father父節(jié)點(diǎn) void makeSet() for (int i = 0; i < maxn; i+) fatheri = i; 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(int x, int y) / 將x所在
15、的集合和y所在的集合整合起來形成一個(gè)集合。 int a, b; a = findRoot(x); b = findRoot(y); fathera = b; / y連在x的根節(jié)點(diǎn)上 或fatherb = a為x連在y的根節(jié)點(diǎn)上; /* 在findRoot(x)中: 路徑壓縮 迭代 最優(yōu)版 關(guān)鍵在于在路徑上的每個(gè)節(jié)點(diǎn)都可以直接連接到根上*/圖論MST最小生成樹Kruskal9.克魯斯卡爾算法/* |Kruskal算法| |適用于 稀疏圖 求最小生成樹| |16/11/05ztx thanks to wangqiqi|*/* 第一步:點(diǎn)、邊、加入vector,把所有邊按從小到大排序 第二步:并查集
16、部分 + 下面的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算法| |適用于 稠密圖 求最小生成樹| |堆優(yōu)化版,時(shí)間復(fù)雜度:O(elgn)| |16/11/05ztx, thanks to chaixiaojun|*/struct node int v, len; node(int v = 0, int len = 0) :
17、v(v), len(len) bool operator < (const node &a)const / 加入隊(duì)列的元素自動(dòng)按距離從小到大排序 return len> a.len; ;vector<node> Gmaxn;int vismaxn;int dismaxn;void init() for (int i = 0; i<maxn; i+) Gi.clear(); disi = INF; visi = false; int Prim(int s) priority_queue<node>Q; / 定義優(yōu)先隊(duì)列 int ans = 0;
18、Q.push(node(s,0); / 起點(diǎn)加入隊(duì)列 while (!Q.empty() node now = Q.top(); Q.pop(); / 取出距離最小的點(diǎn) int v = now.v; if (visv) continue; / 同一個(gè)節(jié)點(diǎn),可能會(huì)推入2次或2次以上隊(duì)列,這樣第一個(gè)被標(biāo)記后,剩下的需要直接跳過。 visv = true; / 標(biāo)記一下 ans += now.len; for (int i = 0; i<Gv.size(); i+) / 開始更新 int v2 = Gvi.v; int len = Gvi.len; if (!visv2 &&
19、disv2 > len) disv2 = len; Q.push(node(v2, disv2); / 更新的點(diǎn)加入隊(duì)列并排序 return ans; Bellman-Ford單源最短路Dijkstra11.迪杰斯特拉算法/* |Dijkstra算法| |適用于邊權(quán)為正的有向圖或者無向圖| |求從單個(gè)源點(diǎn)出發(fā),到所有節(jié)點(diǎn)的最短路| |優(yōu)化版:時(shí)間復(fù)雜度 O(elbn)| |16/11/05ztx, thanks to chaixiaojun|*/struct node int v, len; node(int v = 0, int len = 0) :v(v), len(len) boo
20、l operator < (const node &a)const / 距離從小到大排序 return len > a.len; ; vector<node>Gmaxn; bool vismaxn; int dismaxn;void init() for (int i = 0; i<maxn; i+) Gi.clear(); visi = false; disi = INF; int dijkstra(int s, int e) priority_queue<node>Q; Q.push(node(s, 0); / 加入隊(duì)列并排序 diss =
21、 0; while (!Q.empty() node now = Q.top(); / 取出當(dāng)前最小的 Q.pop(); int v = now.v; if (visv) continue; / 如果標(biāo)記過了, 直接continue visv = true; for (int i = 0; i<Gv.size(); i+) / 更新 int v2 = Gvi.v; int len = Gvi.len; if (!visv2 && disv2 > disv + len) disv2 = disv + len; Q.push(node(v2, disv2); retur
22、n dise; SPFA12.最短路徑快速算法(Shortest Path Faster Algorithm)/* |SPFA算法| |隊(duì)列優(yōu)化| |可處理負(fù)環(huán)|*/vector<node> 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<int> Q; memset(inqueue,false,sizeof(inq
23、ueue); / 標(biāo)記是否在隊(duì)列中 memset(cnt,0,sizeof(cnt); / 加入隊(duì)列的次數(shù) dists = 0; Q.push(s); / 起點(diǎn)加入隊(duì)列 inqueues = true; / 標(biāo)記 while(!Q.empty() v1 = Q.front(); Q.pop(); inqueuev1 = false; / 取消標(biāo)記 for(int i = 0 ; i < Gv1.size() ; +i) / 搜索v1的鏈表 v2 = Gv1i.vex; weight = Gv1i.weight; if(distv2 > distv1 + weight) / 松弛操作
24、 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ì)列超過n-1次,那么顯然圖中有負(fù)環(huán) */Floyd-Warshall13.弗洛伊德算法/* |Floyd算法| |任意點(diǎn)對(duì)最短路算法| |求圖中任意兩點(diǎn)的最短距離的算法|*/for (int i = 0; i <
25、; n; i+) / 初始化為0 for (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); 二分圖14.染色法/* |交叉染色法判斷二分圖| |16/11/05ztx|*/int bipartite(int s) int u, v; queue<int>Q; co
26、lors = 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); else if (colorv = coloru) return 0; return 1; 15.匈牙利算法/* |求解最大匹配問題| |遞歸實(shí)現(xiàn)| |16/11/05ztx|*/vector<int>Gmaxn; bool inpathmaxn; / 標(biāo)記 int match
27、maxn; / 記錄匹配對(duì)象 void init() memset(match, -1, sizeof(match); 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;
28、 void hungary() int cnt = 0; for (int i = 1; i <= m; i+) / m為需要匹配的“妹子”數(shù) memset(inpath, false, sizeof(inpath); / 每次都要初始化 if (findpath(i) cnt+; cout << cnt << endl; /* |求解最大匹配問題| |dfs實(shí)現(xiàn)| |16/11/05ztx|*/int v1, v2; bool Map501501; bool visit501; int link501; int result; bool dfs(int x) f
29、or (int y = 1; y <= v2; +y) if (Mapxy && !visity) visity = true; if (linky = 0 | dfs(linky) linky = x; return true; return false; void Search() for (int x = 1; x <= v1; x+) memset(visit,false,sizeof(visit); if (dfs(x) result+; 動(dòng)態(tài)規(guī)劃背包16.17.18背包問題/* |01背包| |完全背包| |多重背包| |16/11/05ztx|*/ 0
30、1背包: void bag01(int cost,int weight) for(i = v; i >= cost; -i) dpi = max(dpi, dpi-cost+weight); / 完全背包: void complete(int cost, int weight) for(i = cost ; i <= v; +i) dpi = max(dpi, dpi - cost + weight); / 多重背包: void multiply(int cost, int weight, int amount) if(cost * amount >= v) complete
31、(cost, weight); else k = 1; while (k < amount) bag01(k * cost, k * weight); amount -= k; k += k; bag01(cost * amount, weight * amount); / otherint dp;int c55, m110;int sum;void CompletePack(int c) for (int v = c; v <= sum / 2; +v) dpv = max(dpv, dpv - c + c); void ZeroOnePack(int c) for (int v
32、 = sum / 2; v >= c; -v) dpv = max(dpv, dpv - c + c); void multiplePack(int c, int m) if (m * c > sum / 2) CompletePack(c); else int k = 1; while (k < m) ZeroOnePack(k * c); m -= k; k <<= 1; if (m != 0) ZeroOnePack(m * c); LIS19.最長(zhǎng)上升子序列/* |最長(zhǎng)上升子序列| |狀態(tài)轉(zhuǎn)移| |16/11/05ztx|*/* 狀態(tài)轉(zhuǎn)移dpi = max
33、 1.dpj + 1 ; j<i; aj<ai; di是以i結(jié)尾的最長(zhǎng)上升子序列 與i之前的 每個(gè)aj<ai的 j的位置的最長(zhǎng)上升子序列+1后的值比較*/void solve() / 參考挑戰(zhàn)程序設(shè)計(jì)入門經(jīng)典; for(int i = 0; i < n; +i) dpi = 1; for(int j = 0; j < i; +j) if(aj < ai) dpi = max(dpi, dpj + 1); /* 優(yōu)化方法: dpi表示長(zhǎng)度為i+1的上升子序列的最末尾元素 找到第一個(gè)比dp末尾大的來代替 */ void solve() for (int i =
34、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; /* 函數(shù)lower_bound()返回一個(gè) iterator 它指向在first,last)標(biāo)記的有序序列中可以插入value,而不會(huì)破壞容器順序的第一個(gè)位置,而這個(gè)位置標(biāo)記了一個(gè)不小于value的值。*/LCS20.最長(zhǎng)公共子序列/* |求最長(zhǎng)公共子序列| |遞推形式|
35、|16/11/05ztx|*/void solve() for (int i = 0; i < n; +i) for (int j = 0; j < m; +j) if (s1i = s2j) 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) ; typedef node Vector;Vector operator + (Vector A, V
36、ector B) return Vector(A.x + B.x, A.y + B.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, A.y*p); double Dot(Vector A, Vector B) return A.x*
37、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 A, double rad) / 向量旋轉(zhuǎn) 公式 return Vector(A.x*co
38、s(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad); 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 Gmaxn; int n; double Cross(node a, node b) / 叉
39、積計(jì)算 return a.x*b.y - a.y*b.x; int main() 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 = G0.x; Gn.y = G0.y; for (int i = 0; i < n; i+) sum += Cross(Gi, Gi + 1); / 或者 /for (int i = 0; i
40、 < n; i+) /sum += fun(Gi, G(i + 1)% n); / sum = sum / 2.0; printf("%.1fn", sum); system("pause"); return 0; 23.判斷線段相交/* |16/11/06ztx|*/node P35105; double Cross_Prouct(node A,node B,node C) / 計(jì)算BA叉乘CA return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); bool Intersect(node A,node B
41、,node C,node D) / 通過叉乘判斷線段是否相交; if(min(A.x,B.x)<=max(C.x,D.x)&& / 快速排斥實(shí)驗(yàn); min(C.x,D.x)<=max(A.x,B.x)&& min(A.y,B.y)<=max(C.y,D.y)&& min(C.y,D.y)<=max(A.y,B.y)&& Cross_Prouct(A,B,C)*Cross_Prouct(A,B,D)<0&& / 跨立實(shí)驗(yàn); Cross_Prouct(C,D,A)*Cross_Prouct(C,D,B)<0) / 叉乘異號(hào)表示在兩側(cè); return true; else return false; 24.求三角形外心/* |16/11/06ztx|*/Point circumcenter(const Point &a, const Point &b, const Point &c) /返回三角形的外心 Point ret; double
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 頭癬的臨床護(hù)理
- 《教育學(xué)術(shù)的表達(dá)》課件
- 變量與函數(shù)說課課件
- 孕期翻身困難的健康宣教
- 【培訓(xùn)課件】營(yíng)銷團(tuán)隊(duì)由管理邁向經(jīng)營(yíng)
- 頜下腺炎的健康宣教
- 《機(jī)械制造基礎(chǔ)》課件-05篇 第五單元 超聲加工
- 先天性無子宮的健康宣教
- 《高新新認(rèn)定培訓(xùn)》課件
- JJF(陜) 117-2024 全自動(dòng)陰離子合成洗滌劑分析儀 校準(zhǔn)規(guī)范
- 2024年咨詢工程師(經(jīng)濟(jì)政策)考試題庫(kù)附完整答案(奪冠系列)
- 期末檢測(cè)卷(一)2024-2025學(xué)年人教PEP版英語四年級(jí)上冊(cè)(含答案含聽力原文無聽力音頻)
- 高中名詞性從句語法填空單句練習(xí)題上(1-40)
- 2025醫(yī)院內(nèi)部審計(jì)工作計(jì)劃范文
- 《頸動(dòng)脈介入治療》課件
- 第14課 文化傳承的多種載體及其發(fā)展說課稿-2023-2024學(xué)年高中歷史統(tǒng)編版(2019)選擇性必修3文化交流與傳播
- 企業(yè)發(fā)展未來5年規(guī)劃
- 樁工機(jī)械使用前驗(yàn)收表
- 2024-2025學(xué)年四年級(jí)科學(xué)上冊(cè)第一單元《聲音》測(cè)試卷(教科版)
- 2024年交管12123學(xué)法減分考試題庫(kù)附完整答案(網(wǎng)校專用)
- 健康膳食解碼智慧樹知到期末考試答案2024年
評(píng)論
0/150
提交評(píng)論