-1,2 C++ C++ hansonyu /6 (? 10/ TOI 2 TOI TOI 3 TOI 20 TOI /4 TOI TOI APIO 4 TOI 12 4 IOI 5 APIO TOI (

Size: px

Start display at page:

Download "-1,2 C++ C++ hansonyu /6 (? 10/ TOI 2 TOI TOI 3 TOI 20 TOI /4 TOI TOI APIO 4 TOI 12 4 IOI 5 APIO TOI ("

栋既后
5 years ago
Views:

1 hansonyu /6 (? 10/ TOI 2 TOI TOI 3 TOI 20 TOI /4 TOI TOI APIO 4 TOI 12 4 IOI 5 APIO TOI (? 7/28 IOI /11 11/12 NPSC I

2 1.3 OJ TIOJ UVa ACM-ICPC POI ZJ CF OJ tioj.infor.org OJ 1997 uva.onlinejudge.org icpcarchive.ecs.baylor.edu main.edu.pl/en C++11 feedback zerojudge.tw UVa (? 1~2 codeforces.com OJ code 1.4 cplusplus C++ reference en.cppreference.com/w/cpp C++ C++ reference ppt II

3 1.5 ISBN Introduction to Algorithms O-notation O-notation f(x) = O(g(x)) as x c x 0 f(x) c g(x) x x 0 g(x) f(x) x = O(x 2 ), 2x = O(123456x + 7), x 213 = O(2 x ) O-notation 7x x O(x 3 ), O(x 2 + x), O(7x 2 ) O(x 2 ) 2.2 C++ O-notation O-notation A A(n) = 1000n 3 = O(n 3 ) B B(n) = n 4 = O(n 4 ) n 1 A B n A B B n = 10 6 A III

4 B A Algorithm 1: Insertion sort 1 function insertion_sort(array, length) 2 for i = 1 to length(a) x = A[i] 4 j = i 5 while j > 0 and A[j] > x 6 A[j] = A[j - 1] 7 j = j end while 9 A[j] = x 10 end for 11 end function insertion sort n n 1 O(n) n(n 1)/2 O(n 2 ) Worst case O(n 2 ) C C O(1) IV

5 O(n) O(n) O(n) O(n) O(n) O(1) vector push_back disjoint set O(n) O(n 2 ) treap O(n) O(log n) hash function 3 C++ C C++ C C++ library C++ C Standard Template Library STL C++ namespace std 3.2 C++ C++ C T C template C++ C int C V

6 double C C ( ) C<(int double)> ( ) int double priority_queue<a, B, C> C++ C Iterator C C C C++ STL i i *i 1. Random Access s s s s 2. Bidirectional Forward Input 2. Output const C++ O(1) C C::iterator C::reverse_iterator c c.begin() c.end() c.rbegin c.rend() c.begin() c c.end() c *c.end() *c.rend() VI

7 3.4 vector vector <vector> vector vector v 1. vector<t> v(size_type a, const T& b) v b a a b T v vector O(a) 2. v[i] v i i [0, size) undefined behavior O(1) 3. v.size() v O(1) 4. v.push_back(t a) v a O(1) 5. v.pop_back() v v O(1) 6. v.empty() bool v O(1) 7. v.clear() v O(size) v 8. v.resize(size_type a, const T& b) v a v O(D(size a)) D T v b a b T O(C(a size)) reallocate O(Ca) C T 9. v.reserve(size_type n) n T O(size) n < size vector vector reserve vector<bool> bool 1 bit bool[] 1/8 3.5 string string <string> basic_string<char> string vector<char> s VII

8 1. s = t t string C s t O(size s + size t ) 2. s += t t string C s t O(size s + size t ) 3. s.c_str() s C C++11 O(1) 4. s t s t O(max(size s, size t )) 5. cin >> s s 6. cout << s s 7. getline(cin, s, char c) s c c '\n' string vector string s.size() s.length() string 3.6 deque deque <deque> deque vector vector d d.pop_front() a d.push_front(a) deque vector deque 3.7 list list <list> list doubly linked list O(1) O(1) vector i O(i) s 1. list<t> s(size_type a, const T& b) vector 2. s.push_front(t a) s.push_back(t a) s.pop_front() s.pop_back() deque 3. s.size() s C++98 O(size) C++11 O(1) VIII

9 4. s.empty() bool v O(1) 5. s.insert(iterator p, T a) p a a O(1) 6. s.insert(iterator p, size_type n, T a) p n a O(n) 7. s.erase(iterator p) p p O(1) 8. s.erase(iterator first, iterator last) [first,last) last 9. s.splice(iterator p, list& x, iterator first, iterator last) first last x [first,last) x p x last first x s first last x s x list list O(1) insert erase list C++11 forward_list reverse_iterator 3.8 Container adaptor (?) Container adaptor container adaptor 3.9 stack stack <stack> LIFO stack T C T C stack C empty size back push_back pop_back vector deque list stack s IX

10 1. stack<t, C> s(c& a) s a C C deque<t> a s O(size) 2. s.size() s.empty() vector 3. s.top() s O(1) 4. s.push() s O(1) 5. s.pop() s O(1) C vector<t> stack vector vector stack 3.10 queue queue <queue> FIFO queue T C stack queue C empty size front back push_back pop_front deque list queue q 1. queue<t, C> q(c& a) q a C C deque<t> a q O(size) 2. q.size() q.empty() vector 3. q.front() sq O(1) 4. q.back() q O(1) 4. q.push() q O(1) 5. q.pop() q O(1) C stack queue deque 3.11 priority_queue <queue> priority_queue priority_queue binary heap priority_queue X

11 priority_queue priority_queue T Con Cmp T Con Cmp Con empty size front push_back pop_back vector deque Cmp Cmp less<t> priority_queue greater<t> priority_queue priority_queue pq 1. priority_queue<t, Con, Cmp> pq pq O(1) 2. priority_queue<t, Con, Cmp> pq(iterator first, iterator last) pq [first,last) iterator O(size) 3. pq.size() pq.empty() vector 4. pq.top() pq O(1) 5. pq.push(t a) a pq O(log size) 6. pq.pop() pq O(log size) O(size) push O(size log size) priority_queue 3.12 pair pair <utility> <pair> pair pair pair p 1. pair<a, B> p(a a, B b) A B p a b 2. p = s s pair p s 3. p s s pair 4. p.first p.second XI

12 pair make_pair make_pair make_pair(a a B b) pair<a, B> a b C++11 pair tuple <tuple> 3.13 set set <set> set O(log n) key set s 1. set<k> s s O(1) 2. s.size() s.empty() vector 3. s.insert(k k) s k O(log size) 4. s.erase(iterator first, iterator last) [first,last) last first O(1) 5. s.erase(k k) k set 0 1 O(log size) 6. s.find(k k) k m.end() O(log size) 7. s.count(k k) k set 0 1 O(log size) 8. s.lower_bound(k k) k O(log size) 9. s.upper_bound(k k) k O(log size) set set::iterator set::reverse_iterator set O(1) lower_bound upper_bound [l,u) [s.lower_bound(l), s.upper_bound(u) ) C++ XII

13 3.14 map map <map> map set O(log n) map K T K T map pair<k, T> pair map m 1. map<k, T> m m O(1) 2. m.size() m.empty() m.erase(iterator first, iterator last) m.erase(k k) m.find(k k) m.count(k k) m.lower_bound(k k) m.upper_bound(k k) set 3. m[k] k k k O(log size) 4. m.insert(pair<k, T> k) k.first k.first k.second pair first second true pair first k.first second false O(log size) set map 3.15 multiset, multimap <set> <map> multiset multimap multiset multimap set map count erase 0 1 multimap multiset multimap equal_range(k k) iterator pair lower_bound(k) upper_bound(k) k set map set map 3.16 (C++11)unordered_(multi)set, unordered_(multi)map C++11 unordered map set O(log n) unordered_(multi)set unordered_(multi)map <unordered_set> <unordered_ map> set map XIII

14 Hash C++11 unordered (multi)map (multi)set 1. unordered 2. unordered 3. lower_bound upper_bound 4. (multi)map (multi)set unordered log bucket bucket 3.17 bitset bitset <bitset> 0 1 bitset 1 bit bitset bitset bitset n bitset bitset b 1. bitset<n> b(a) a N bitset a unsigned long string C a b a 0 2. b.count() b 1 O(N) 3. b.size() b O(1) 4. b bitset bitset O(N) 5. b[a] a O(1) 6. b.set() 1 O(N) 7. b.reset() 0 O(N) 8. b.flip() 0 1 O(N) 9. b.to_string() b O(N) XIV

15 10. b.to_ulong() unsigned long b O(N) bitset 1/8 count 1/6 1/ (ZJ b298) N 10 4 M 10 6 a, b a b N L Q 10 4 vector 2. (ZJ c123)(uva 514) 1 N stack stack 1 N stack 3. (ZJ a813) N 10 6 i H i a < b a b H a H b a b b a i C i C 1 + C C N stack 4. (ZJ d424)(uva 105)(TIOJ 1202) x +y priority_queue 5. (ZJ b231)(2009 pc) N 1000 N 10 5 priority_queue 6. (TIOJ 1807) m 10 3 n n map, set 7. (ZJ b291) N 1000 N 20 M 100 vector, map, string XV

16 4 <algorithm> C++ <algorithm> <algorithm> 4.1 int dereference dereference vector deque [] operator () () 4.2 less, greater less greater <functional> < T less<t>(t a, T b) bool a<b greater less greater <functional> <functional> less greater <algorithm> <queue> <set> <map> <functional> 4.3 <algorithm> swap min max random_shuffle iter_swap XVI

17 4.4 C++ for_each, find, find_if, find_end, count, count_if, search, search_n, copy, copy_backward, replace, replace_if, fill, fill_n, remove, remove_if, unique, reverse, rotate, partition, stable_partition, min_element, max_element, lexicographical_compare C++11 lambda function inline 4.5 sort, nth_element sort insertion sort quicksort TLE merge sort heapsort C++ sort nth_element introsort introselect introselect k introselect quickselect pivot pivot O(n) O(n 2 ) introselect quickselect median of medians wiki quickselect median of medians nth_element introselect O(n) Median of medians Introsort quicksort heapsort priority_queue insertion sort 1. sort(iter first, iter last, Cmp cmp) [first,last) cmp a b cmp(a,b) iter cmp bool cmp O(Cn log n) C cmp XVII

18 2. stable_sort sort a b a b a b O(n log n) O(n) O(n log 2 n) O(n log n) block sort wikisort 3. nth_element(iter first, iter nth, iter last, Cmp cmp) nth x nth x x sort O(n) O(n log n) lower_bound(iter first, iter last, T t, Cmp cmp) [first, last) a cmp(a, t) a [first, last) Cmp Cmp [first, last) map lower_bound iter O(log n) O(n) iter set map set map 2. upper_bound(iter first, iter last, T t, Cmp cmp) [first, last) a cmp(t, a) a lower_bound 3. equal_range(iter first, iter last, T t, Cmp cmp) pair lower_bound upper_bound lower_bound 4. merge(iter1 first1, iter1 last1, iter2 first2, iter2 last2, iter3 res, Cmp cmp) [first1, last1) [first2, last2) cmp res iter1 iter2 iter3 res 5. set_union(iter1 first1, iter1 last1, iter2 first2, iter2 last2, iter3 res, Cmp cmp) A = [first1, last1) B = [first2, last2) cmp res merge 6. set_intersection set_union 7. set_difference set_union A B 8. set_symmetric_difference set_union A B A B XVIII

19 4.7 (next/prev)_permutation next_permutation prev_permutation n! 1. next_permutation(iter first, iter last, Cmp cmp) [first, last) true false [first, last) cmp iter 2. prev_permutation(iter first, iter last, Cmp cmp) [first, last) true false [first, last) next_permutation (ZJ a233) BJ4 2. (TIOJ 1807) m 10 3 n n vector, sort 3. (TIOJ 1617)(IOI 2000)(Interactive) n nth_element 4. (ZJ d242)(uva 481) 10 5 vector, upper_bound 5 (Dynamic Programming) DP XIX

20 Algorithm 2: Fibonacci without DP 1 function fibo(i) 2 if i = 0 3 return 0 4 else if i = 1 5 return 1 6 else 7 return f(i - 1)+f(i - 2) 8 end if 9 end function Algorithm 3: Fibonacci with DP 1 array dp = {0} 2 function fibo(i) 3 if dp[i]!= 0 4 return dp[i] 5 else if i = 0 6 return 0 7 else if i = 1 8 return dp[1] = 1 9 else 10 return dp[i] = f(i - 1) + f(i - 2) 11 end if 12 end function DP Algorithm 3 n 0 n 1 O(n) Algorithm 3 f(i) f(i 1) + f(i 2) f(i) = f(i 1) + f(i 2) DP XX

21 O(1) Algorithm 3 O(n) O(1) = O(n) Algorithm 2 O(φ n )(φ = ) O(1) DP 5.2 DP DP DP DP O(1) Algorithm 4: Fibonacci with rolling DP 1 function fibo(i) 2 if i = 0 3 return 0 4 else 5 prev_val = 0, now_val = 1 6 for now_index = 1 to i 7 prev_val += now_val 8 swap prev_val and now_val 9 end for 10 return now_val 11 end if 12 end function prev_val now_val now_val prev_val C/C DP judge 1. a 0, a 1,, a n 1 i, j a i + a i a j O(n) O(1) XXI

22 2. Longest Common Sequence, LCS m n O(mn) O(mn) O(min(m, n)) 3. (ZJ d637) 0/1 W N O(NW ) O(W ) 4. O(NW ) O(W ) 5. n O(n 2 2 n ) O(n2 n ) 0 1 DP (ZJ d652) n 50 n 400 W i A B C A C B P = W A W B W C (ZJ d645) O(nmw) n m w DP O(nw) 3. (ZJ d054) 3 L 2 n n 40 n (ZJ a128)(acm ICPC World Finals) x y x, y 10 4 n 15 n 1 n n DP 5. (2016 pb)(no judge) H H H P 1, P 2,, P U P i i H [0,U] H O(U 2 ) XXII

23 DP O(U log U) 7. (2015 pa)(no judge) n n n 22 V i,j 10 6 DP 6 (greedy) greedy greedy 6.1 0/1 1. O(n log n) 2. O(n log n) 3. CP O(n log n) DP greedy greedy greedy 6.2 n 1. O(n log n) 2. O(n log n) 3. O(n log n) XXIII

24 [0,5][4,6][5,10] [0,3][1,2][2,3] greedy greedy 6.3 greedy greedy greedy 1. (No judge) n O(n log n) 2. (Codeforces 665C) edit distance 3. (Codeforces 701A) n 100 n 4. (ZJ b231)(2009 pc) N 1000 N f [a, a + n) f(s) c s a s O(n) (a, a + n) k f(k 1) c s < k [a, k) f(k 1) < c s k [k, a + n) k a + n/2 O(log n) f f(a) c O(M) O(M log n) XXIV

25 lower_bound upper_bound Algorithm 5: Binary Search 1 function binary_search(array[], first, last, val) 2 while first + 1 < last 3 mid = (first + last) / 2 4 if (array[mid - 1] < val) 5 first = mid 6 else 7 last = mid 8 end if 9 end while 10 return first 11 end function 7.2 [a, a + n) f f [a, a + n) [a, a + n) x < y f(x) < f(y) [a, y) f(x) > f(y) (x, a + n) f(x) = f(y) (x, y) x y O(log n) 7.3 P s P (s) = 1 0 P s P s s XXV

26 (TIOJ 1839)(IOI 2013)(Interactive) n 5000 n n 2. (TIOJ 1341)(IOI 2007)(Interactive) 3. (TIOJ 1815)(IOI 2013) T 10 6 A B W i S i X i Y i greedy XXVI

contentGB.PDF

contentGB.PDF v i v xvii xvii xviii xviii xix xx xx xxi xxii xxiii xxiv xxvi xxvi 1 STL 001 1.1 STL 001 1.1.1 STL 003 1.1.2 STL C++ 003 vi STL 1.2 STL 004 1.3 GNU 007 1.4 HP STL 009 1.5 P.J. Plauger STL 010 1.6 Rouge