「Algorithm」01 基础算法

第一章 基础算法 包括排序,二分,高精度,前缀和与差分,位运算,离散化,区间合并 消除同步 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....

November 9, 2021

「Algorithm」02 Data Structure

链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 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 !...

October 12, 2021