Posts

第一章 基础算法 包括排序，二分，高精度，前缀和与差分，位运算，离散化，区间合并 消除同步 ios::sync_with_stdio(false);//让cin和标准输入输出不同步，提高cin的读取速度，不能再使用scanf和printf了。 scanf/getchar和cin不要一起用，printf/puts/putchar和cout不要一起用。 可以使用freopen 还可以加上 cin.tie(0) 来解除c++运行库层面的对数据传输的绑定。 排序 1. 快速排序 基于分治。 确定一个分界点，比如（以1开始）,取q[1]，q[(1+r)/2] ,q[r]， 随机为x 调整区间，小于等于x的在左边，大于等于x的在右边。等于x的可以在左边也可以在右边，也可以在边界上，不稳定。 递归处理左右两段。 方法一: 开两个额外的数组,a[]，b[] 扫描q数组，如果q[i] ≤ x，存入a，如果q[i]>x，存入b。 然后将a数组的数存入q，b数组的数存入q。 方法二： i和j指针，i指向初始，j指向末尾。然后i向右走，直到遇到一个大于x的数。j向左走，直到遇到一个小于等于x的数。然后交换，直到 j ≤ i. 模板： 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 #include <iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[(l+r) >> 1], i = l - 1, j = 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]); } //j可能比i小，也可能等于i。 quick_sort(q, l, j); //也可以换成 l, i -1 quick_sort(q, j + 1, r); //换成 i, r //后来说明不能换成i，因为也是会出现死循环问题。 //遇到这种情况，就考虑0,1。 //用j的话，x不能取右边界，（j可以取q[l]、q[(l+r)/2]） //j不能取 q[r]、q[(l+r+1)/2] //用i的话，x不能取左边界。 (i可以取q[r]、q[(l+r+1)/2]) //i不能取 q[l]、q[(l+r)/2] } //当下面换成i,r时，不能取x=q[l]，因为会出现死循环的问题。比如排序1，2 //i最终为0，j也是0，这样使用quick_sort()会死循环。 //同理，如果取j+1,r，不能取右边界。 int main(){ 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; } 排序的话，可以使用 #include<algorithm> sort(q, q+n); 2.归并排序 类似快排，也是分治。 ...

链表与邻接表：树与图的存储 栈与队列：单调队列、单调栈 kmp Trie 并查集 堆 Hash表 链表与邻接表：树与图的存储 用数组来模拟这些结构，不适用struct和STL。目的是为了提高效率 1 2 3 4 5 6 7 struct Node { int val; Node * next; }; Node * p = new Node(); 面试题较多，但是new一个节点是比较慢的，做题不需要。 用数组模拟单链表 最常用的邻接表，存储图和树。它们都是用邻接表存储的。 以上是用数组e[N]和数组ne[N]来模拟单链表，如果是不存在，那么取-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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #include<iostream> using namespace std; const int N = 1e5 + 10; // head 表示头结点的下标 // e[i]是节点i的值 // ne[i] 是节点i的next指针 // idx是一个指针，指向当前用到的点。 int head, e[N], ne[N], idx; void init() { head = -1; idx = 0; } //将x插入到头结点 void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx, idx ++; } //将x插入到下标是k的点的后面 void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++; } //删除k后面的节点 void remove(int k) { ne[k] = ne[ne[k]]; } int main() { int m; cin >> m; init(); while ( m --) { int k, x; char op; cin >> op; if (op == 'H') { cin >> x; add_to_head(x); } else if( op == 'D') { cin >> k; if (k == 0) head = ne[head]; else remove(k - 1); }else { cin >> k >> x; add(k - 1, x); } } for (int i = head; i != -1; i = ne[i]) cout << e[i] << " "; return 0; } 用数组模拟双链表 用来优化某些问题。 ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i = a; i< n; i++) #define per(i,a,n) for(int i=n-1; i>=a; i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sz(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int, int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod = 1000000007; int rnd(int x) { return mrand() % x;} ll mulmod(ll a, ll b) {ll res=0;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res+=a%mod;a+=a%mod;}return res;} ll powmod(ll a, ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res*=a%mod;a*=a%mod;}return res;} ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}