Giải bài tập toán 12 nâng cao hình họcb ai3
- 1. Industry Student Olympiad in IT & ACM/ICPC DST Team Notebook DST TEAM MEMBERS Hung Bui Hinh Le Viet Pham – – – duyhunghd6@gmail.com a_hinh@zing.vn phamviet_1990@zing.vn Faculty of Information Technology 2011 Group of HaUI Student Olympiad in IT & ACM/ICPC Website: //olympic.fit-haui.edu.vn 1
- 2. THEORETIC ALGORITHM ........................................................................4 1] Number theoretic algorithm .......................................................................................................4 2] Gauss-Jordan ..............................................................................................................................6 3] Reduced Row Echelon Form ......................................................................................................7 4] Fast Fourier transform ................................................................................................................9 5] Simplex algorithm ....................................................................................................................10 6] Prime lower than N...................................................................................................................12 CHAPTER II: TỐI ƯU TỔ HỢP ......................................................................................................15 7] Dinic’s Algorithm.....................................................................................................................15 8] Min cost max-flow ...................................................................................................................16 9] Push relabel Ford-Fulkerson ....................................................................................................18 10] Min Cost Matching...................................................................................................................20 11] Max Bipartite Matching ...........................................................................................................22 12] Lát cắt trên đồ thị......................................................................................................................22 13] Graph Cut Inference .................................................................................................................23 14] Ford-Fulkerson .........................................................................................................................26 CHAPTER III: 1] GRAPH ......................................................................................................................26 GRAPH PRESENTATION ......................................................................................................26 a] Using Adjency List ...............................................................................................................26 b] Danh sách kề có trọng số ......................................................................................................27 2] GRAPH SEARCHING.............................................................................................................29 a] Depth First Search ................................................................................................................29 b] Breath First Search ...............................................................................................................30 3] FIND MIN PATH ....................................................................................................................32 a] Thuật toán FLOYD ...............................................................................................................32 b] Thuật toán DIJKSTRA .........................................................................................................33 c] DIJKSTRA using Adjancy List ............................................................................................34 4] Strong connected Component ..................................................................................................35 CHAPTER IV: 1] STRING .....................................................................................................................37 STRING MATCHING .............................................................................................................37 a] Knuth-Morris-Pratt ...............................................................................................................37 b] Boyer-More...........................................................................................................................39 CHAPTER V: DYNAMIC PROGRAMMING .................................................................................42 2
- 3. QUY HOẠCH ĐỘNG ĐIỂN HÌNH ...........................................................42 1] a] Dãy con đơn điệu dài nhất ....................................................................................................42 b] Longest Increasing Subsequence Code O[NlogN] ...............................................................43 c] Vali [B] .................................................................................................................................45 d] Biến đổi xâu: .........................................................................................................................47 e] Vali [A] .................................................................................................................................49 f] Nhân ma trận ............................................................................................................................51 g] Ghép cặp ...............................................................................................................................52 QUY HOẠCH ĐỘNG TRẠNG THÁI ....................................................................................53 2] a] 3] Trò chơi trên lưới ..................................................................................................................53 MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG BỔ XUNG ......................................................54 CHAPTER VI: GEOMETRY .............................................................................................................56 1] Convex Hull .............................................................................................................................56 2] Geometry Computation ............................................................................................................57 3] JavaGeometry ...........................................................................................................................62 4] Geometry 3D ............................................................................................................................64 5] Delaunay triangulation .............................................................................................................65 CHAPTER VII: SPECIAL DATA STRUCTURE ..............................................................................67 1] Binary index tree ......................................................................................................................67 2] Disjoint-Set...............................................................................................................................67 3] KD-Tree....................................................................................................................................67 4] SuffixArray...............................................................................................................................70 5] Disjoint-Set...............................................................................................................................72 6] Interval tree...............................................................................................................................73 3
- 4. THEORETIC ALGORITHM 1] Number theoretic algorithm // This is a collection of useful code for solving problems that // involve modular linear equations. Note that all of the // algorithms described here work on nonnegative integers.
include
include
include using namespace std; typedef vector VI; typedef pair PII; // return a % b [positive value] int mod[int a, int b] { return [[a%b]+b]%b; } // computes gcd[a,b] int gcd[int a, int b] { int tmp; while[b]{a%=b; tmp=a; a=b; b=tmp;} return a; } // computes lcm[a,b] int lcm[int a, int b] { return a/gcd[a,b]*b; } // returns d = gcd[a,b]; finds x,y such that d = ax + by int extended_euclid[int a, int b, int &x, int &y] { int xx = y = 0; int yy = x = 1; while [b] { int q = a/b; int t = b; b = a%b; a = t; t = xx; xx = x-q*xx; x = t; t = yy; yy = y-q*yy; y = t; } return a; } // finds all solutions to ax = b [mod n] VI modular_linear_equation_solver[int a, int b, int n] { int x, y; VI solutions; int d = extended_euclid[a, n, x, y]; if [![b%d]] { x = mod [x*[b/d], n]; for [int i = 0; i < d; i++] solutions.push_back[mod[x + i*[n/d], n]]; } return solutions; } // computes b such that ab = 1 [mod n], returns -1 on failure int mod_inverse[int a, int n] { int x, y; int d = extended_euclid[a, n, x, y]; if [d > 1] return -1; 4
- 5. remainder theorem [special case]: find z such that // z % x = a, z % y = b. Here, z is unique modulo M = lcm[x,y]. // Return [z,M]. On failure, M = -1. PII chinese_remainder_theorem[int x, int a, int y, int b] { int s, t; int d = extended_euclid[x, y, s, t]; if [a%d != b%d] return make_pair[0, -1]; return make_pair[mod[s*b*x+t*a*y,x*y]/d, x*y/d]; } // Chinese remainder theorem: find z such that // z % x[i] = a[i] for all i. Note that the solution is // unique modulo M = lcm_i [x[i]]. Return [z,M]. On // failure, M = -1. Note that we do not require the a[i]'s // to be relatively prime. PII chinese_remainder_theorem[const VI &x, const VI &a] { PII ret = make_pair[a[0], x[0]]; for [int i = 1; i < x.size[]; i++] { ret = chinese_remainder_theorem[ret.first, ret.second, x[i], a[i]]; if [ret.second == -1] break; } return ret; } // computes x and y such that ax + by = c; on failure, x = y =-1 void linear_diophantine[int a, int b, int c, int &x, int &y] { int d = gcd[a,b]; if [c%d] { x = y = -1; } else { x = c/d * mod_inverse[a/d, b/d]; y = [c-a*x]/b; } } int main[] { // expected: 2 cout n; int tg; int v; for[int i=1;i7 = "first < dist[it->second]]{ dist[it->second] = dist[here] + it->first; dad[it->second] = here; Q.push [make_pair [dist[it->second], it->second]]; } } } printf ["%dn", dist[t]]; if [dist[t] < INF] for[int i=t;i!=-1;i=dad[i]] printf ["%d%c", i, [i==s?'n':' ']]; return 0; } 4] Strong connected Component
include struct edge{int e, nxt;}; int V, E; edge e[MAXE], er[MAXE]; int sp[MAXV], spr[MAXV]; int group_cnt, group_num[MAXV]; bool v[MAXV]; int stk[MAXV]; void fill_forward[int x] { int i; v[x]=true; for[i=sp[x];i;i=e[i].nxt] if[!v[e[i].e]] fill_forward[e[i].e]; stk[++stk[0]]=x; } void fill_backward[int x] { int i; 35
- 36. add_edge[int v1, int v2] //add edge v1->v2 { e [E].e=v2; e [E].nxt=sp [v1]; sp [v1]=E; er[ E].e=v1; er[E].nxt=spr[v2]; spr[v2]=E; } void SCC[] { int i; stk[0]=0; memset[v, false, sizeof[v]]; for[i=1;i=1;i--] if[v[stk[i]]]{group_cnt++; fill_backward[stk[i]];} } 36
- 37. MATCHING a] Knuth-Morris-Pratt using System; namespace Knuth_Morris_Pratt { class Test { private char[] s; private char[] p; public void Nhap[] { Console.Write["Nhap xau S:"]; string stdin1 = Console.ReadLine[]; s = new char[stdin1.Length]; s = stdin1.ToCharArray[]; Console.Write["Nhap xau P:"]; string stdin2 = Console.ReadLine[]; p = new char[stdin2.Length]; p = stdin2.ToCharArray[]; } private int[] compute_MP_map[] // map[i]=| border[p[0..i-1]] | { int m = p.Length; // p is the input pattern int[] MP_map = new int[m + 1]; // lưu ý rằng ta phải tính map[0..m] // init MP_map[0] = -1; // cái này chắc ai cũng hiểu // bay gio di tinh map[1..m] int i = 0; int j = MP_map[i]; while [i < m] { while [j >= 0 && [p[i] != p[j]]] j = MP_map[j]; j++; i++; MP_map[i] = j; } return MP_map; } private int[] compute_KMP_map[] //thuật toán KMP cải tiến { int m = p.Length; int[] KMP_map = new int[m + 1]; int[] MP_map = compute_MP_map[]; KMP_map[0] = -1; KMP_map[m] = MP_map[m]; for [int i = 1; i < m; i++] { int j = MP_map[i]; if [p[i] != p[j]] KMP_map[i] = j; else KMP_map[i] = MP_map[j]; } return KMP_map; } public void Morris_Pratt[] { int[] map = compute_KMP_map[]; int n = s.Length; int m = p.Length; int i = 0; string res = ""; for [int j = 0; j < n; j++] { while [[i >= 0] && [p[i] != s[j]]] i = map[i]; i++; // Có 2 khả năng xảy ra: hoặc là đã đi hết chuỗi p [i=m-1] hoặc là i=-1 , lợi dụng cả 2 điều này if [i == m] { res += [j - m + 1].ToString[] + " "; i = map[i]; 37
- 38. args] { Test object1 = new Test[]; object1.Nhap[]; object1.Morris_Pratt[]; Console.ReadLine[]; } } } C++ IMPLEMENT
include
include using namespace std; int m, n, i, j; int Next[100000]; string a; string b; void PREKMP[] { i=0; j=-1; Next[0]=0; while [i-1 && b[i]!=b[j]] j=Next[j]; i++; j++; if[b[i]==b[j]] Next[i]=Next[j]; else Next[i]=j; } } void KMP[] { i=0; j=0; while[j=0 && a[j]!=b[i]] i=Next[i]; i++; j++; if[i>m-1] { cout