一、快速排序 1.快速排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <iostream> using namespace std;const int N = 100010 ;int q[N];void quick_sort (int q[], int l, int r) { if (l >= r) return ; int i = l - 1 , j = r + 1 , x = q[l + r >> 1 ]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap (q[i], q[j]); } quick_sort (q, l, j); quick_sort (q, j + 1 , r); } int main () { int n; scanf ("%d" , &n); for (int i = 0 ; i < n; i ++ ) scanf ("%d" , &q[i]); quick_sort (q, 0 , n - 1 ); for (int i = 0 ; i < n; i ++ ) printf ("%d " , q[i]); return 0 ; }
2.第K大的数字 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> using namespace std;const int N = 100010 ;int q[N];int quick_sort (int q[], int l, int r, int k) { if (l >= r) return q[l]; int i = l - 1 , j = r + 1 , x = q[l + r >> 1 ]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap (q[i], q[j]); } if (j - l + 1 >= k) return quick_sort (q, l, j, k); else return quick_sort (q, j + 1 , r, k - (j - l + 1 )); } int main () { int n, k; scanf ("%d%d" , &n, &k); for (int i = 0 ; i < n; i ++ ) scanf ("%d" , &q[i]); cout << quick_sort (q, 0 , n - 1 , k) << endl; return 0 ; }
二、归并排序 1.归并排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <iostream> using namespace std;const int N = 1e5 + 10 ;int a[N], tmp[N];void merge_sort (int q[], int l, int r) { if (l >= r) return ; int mid = l + r >> 1 ; merge_sort (q, l, mid), merge_sort (q, mid + 1 , r); int k = 0 , i = l, j = mid + 1 ; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0 ; i <= r; i ++, j ++ ) q[i] = tmp[j]; } int main () { int n; scanf ("%d" , &n); for (int i = 0 ; i < n; i ++ ) scanf ("%d" , &a[i]); merge_sort (a, 0 , n - 1 ); for (int i = 0 ; i < n; i ++ ) printf ("%d " , a[i]); return 0 ; }
2.逆序对的数量 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <iostream> using namespace std;typedef long long LL;const int N = 1e5 + 10 ;int a[N], tmp[N];LL merge_sort (int q[], int l, int r) { if (l >= r) return 0 ; int mid = l + r >> 1 ; LL res = merge_sort (q, l, mid) + merge_sort (q, mid + 1 , r); int k = 0 , i = l, j = mid + 1 ; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else { res += mid - i + 1 ; tmp[k ++ ] = q[j ++ ]; } while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0 ; i <= r; i ++, j ++ ) q[i] = tmp[j]; return res; } int main () { int n; scanf ("%d" , &n); for (int i = 0 ; i < n; i ++ ) scanf ("%d" , &a[i]); cout << merge_sort (a, 0 , n - 1 ) << endl; return 0 ; }
三、二分 关于check的写法,要注意是大于还是小于
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 bool check (int x) {} int bsearch_1 (int l, int r) { while (l < r) { int mid = l + r >> 1 ; if (check (mid)) r = mid; else l = mid + 1 ; } return l; } int bsearch_2 (int l, int r) { while (l < r) { int mid = l + r + 1 >> 1 ; if (check (mid)) l = mid; else r = mid - 1 ; } return l; }
一种更清晰的方法
1 2 3 4 5 6 7 8 9 10 int bserach (int a[],int l,int r) { while (l<=r){ int mid=l+r>>1 ; if (a[mid]<x) l=mid+1 ; else if (a[mid]>x) high=mid-1 ; else return mid; } return -1 ; }
四、高精度计算 1.A+B 要点:利用数组储存大数字的每一位,“小端法”
按位模拟加和,满X进1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vector <int > add (vector<int > &A,vecrtor <int > &B){ if (A.size ()<B.size ()) return add (B,A); vector<int > C; int t=0 ; for (int i=0 ;i<A.size ();i++){ t+=A[i]; if (i<B.size ()) t+=B[i]; C.push_back (t % base); t/=base; } if (t) C.push_back (t); return C; }
2.A-B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <iostream> #include <vector> using namespace std;bool cmp (vector<int > &A, vector<int > &B) { if (A.size () != B.size ()) return A.size () > B.size (); for (int i = A.size () - 1 ; i >= 0 ; i -- ) if (A[i] != B[i]) return A[i] > B[i]; return true ; } vector<int > sub (vector<int > &A, vector<int > &B) { vector<int > C; for (int i = 0 , t = 0 ; i < A.size (); i ++ ) { t = A[i] - t; if (i < B.size ()) t -= B[i]; C.push_back ((t + 10 ) % 10 ); if (t < 0 ) t = 1 ; else t = 0 ; } while (C.size () > 1 && C.back () == 0 ) C.pop_back (); return C; } int main () { string a, b; vector<int > A, B; cin >> a >> b; for (int i = a.size () - 1 ; i >= 0 ; i -- ) A.push_back (a[i] - '0' ); for (int i = b.size () - 1 ; i >= 0 ; i -- ) B.push_back (b[i] - '0' ); vector<int > C; if (cmp (A, B)) C = sub (A, B); else { C = sub (B, A); cout << '-' ; } for (int i = C.size () - 1 ; i >= 0 ; i -- ) cout << C[i]; cout << endl; return 0 ; }
3.A*B(高精度乘低精度) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <vector> using namespace std;vector<int > mul (vector<int > &A, int b) { vector<int > C; int t = 0 ; for (int i = 0 ; i < A.size () || t; i ++ ) { if (i < A.size ()) t += A[i] * b; C.push_back (t % 10 ); t /= 10 ; } while (C.size () > 1 && C.back () == 0 ) C.pop_back (); return C; } int main () { string a; int b; cin >> a >> b; vector<int > A; for (int i = a.size () - 1 ; i >= 0 ; i -- ) A.push_back (a[i] - '0' ); auto C = mul (A, b); for (int i = C.size () - 1 ; i >= 0 ; i -- ) printf ("%d" , C[i]); return 0 ; }
4.A/B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <vector> #include <algorithm> using namespace std;vector<int > div (vector<int > &A, int b, int &r) { vector<int > C; r = 0 ; for (int i = A.size () - 1 ; i >= 0 ; i -- ) { r = r * 10 + A[i]; C.push_back (r / b); r %= b; } reverse (C.begin (), C.end ()); while (C.size () > 1 && C.back () == 0 ) C.pop_back (); return C; } int main () { string a; vector<int > A; int B; cin >> a >> B; for (int i = a.size () - 1 ; i >= 0 ; i -- ) A.push_back (a[i] - '0' ); int r; auto C = div (A, B, r); for (int i = C.size () - 1 ; i >= 0 ; i -- ) cout << C[i]; cout << endl << r << endl; return 0 ; }
五、字典树(trie树) 835. Trie字符串统计 - AcWing题库