第一讲基础算法
快速排序
void q_sort(int a[], int l, int r) { if (l >= r) return ; int i = l - 1, j = r + 1, x = a[l + r >> 1]; while (i < j) { do i++; while (a[i] < x); do j--; while (a[j] > x); if (i < j) swap(a[i], a[j]); } q_sort(a, l, j); q_sort(a, j + 1, r); } void q_sort(int a[], int l, int r) { if (l >= r) return ; int x = a[r], i = l - 1, j = r + 1; while (i < j) { do i++; while (a[i] < x); do j--; while (a[j] > x); if (i < j) swap(a[i], a[j]); } q_sort(a, l, i - 1); q_sort(a, i, r); }
并归排序
const int N = 1e5 + 10; int a[N], temp[N]; void merge_sort(int a[], int l, int r) { if (l >= r) return ; int mid = l + r >> 1; merge_sort(a, l, mid); merge_sort(a, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (i = 1, j = 0; i <= r; i++, j++) a[i] = tmp[j]; }
二分
转存失败重新上传取消
模板1：
while (l < r) { int mid = l + r >> 1; if (a[mid] >= x) r = mid; else l = mid + 1; }
模板2：
while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] <= x) l = mid; else r = mid - 1; }
#include<iostream> using namespace std; int main() { double x; scanf("%lf",&x); double l = -100, r = 100; while (r - l > 1e-7) { double mid = (l + r) / 2; if (mid * mid * mid > x) r = mid; else l = mid } printf("%.6lf\n",l); return 0; }
789.数的范围
#include<iostream> using namespace std; const int N = 1e5 + 10; int a[N]; int main() { int m ,n; scanf("%d%d", &n ,&m); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); while ( m--) { int x; scanf("%d", &x); int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (a[mid] >= x) r = mid; else l = mid + 1; } if (x != a[l]) cout << "-1 -1" << endl; else { cout << l << ' '; l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] <= x) l = mid; else r = mid - 1; } cout << l << endl; } } return 0; }
790.数的三次方根
#include<iostream> using namespace std; int main() { double n; scanf("%lf", &n); double l = -100, r = 100; while (r - l > 1e-7) { double mid = (l + r) / 2; if (mid * mid * mid > n) r = mid; else l = mid; } printf("%.6lf", l); return 0; }
高精度加法
vector<int> add(vector<int> &A, vector<int> &B) { vector<int> C; int t = 0; for (int i = 0; i < A.size() || i < B.size(); i++) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(1); return C; }
791、高精度加法
#include<iostream> #include<vector> using namespace std; vector<int> add(vector<int> &A, vector<int> &B) { vector<int> C; if (A.size() < B.size()) swap(A, B); int t = 0; for (int i = 0; i < A.size(); i++) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } int main() { string a, b; cin >> a >> b; vector<int> 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 = add(A, B); for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; return 0; }
高精度减法
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; }
793、高精度乘法
#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; } if (t) C.push_back(t); while (C.back() == 0 && C.size() > 1) C.pop_back(); return C; } int main() { string a; int b; cin >> a >> b; vector<int>A, C; for (int i = a.size() -1; i >= 0; i -- ) A.push_back(a[i] - '0'); C = mul(A,b); for (int i = C.size() - 1; i >= 0; i --) cout << C[i]; return 0; }
高精度除法
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.back() == 0 && C.size() > 1) C.pop_back(); return C; }
794.高精度除法
#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.back() == 0 && C.size() > 1) C.pop_back(); return C; } int main() { string a; int b; cin >> a >> b; vector<int>A, C; for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); int r; C = div(A, b, r); for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; cout << endl << r << endl; return 0; }795前缀和 #include<iostream> using namespace std; const int N = 1e5 + 10; int n, m; int a[N], s[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); s[0] = 1; for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i]; } while (m -- ) { int l , r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); } return 0; }
前缀额和差分
796.前缀和
#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m; int a[N], s[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); s[0] = 1; for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i]; } while (m -- ) { int l , r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); } return 0; }
796.子矩阵的和
#include<iostream> using namespace std; const int N = 1010; int n, m, q; int a[N][N], s[N][N]; int main() { scanf("%d%d%d",&n,&m,&q); for (int i = 1 ; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d",&a[i][j]); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) s[i][j] = s[i- 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; while (q -- ) { int x1, y1, x2, y2; scanf("%d%d%d%d",&x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1 - 1][y2] -s[x2][y1 -1] + s[x1 - 1][y1 - 1]); } return 0; }
797.差分
#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m; int a[N], b[N]; void insert(int l, int r, int c) { b[l] += c; b[r + 1] -= c; } int main() { scanf("%d%d", &n ,&m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); insert(i, i, a[i]); //b[i] = a[i] - a[i - 1]; } int l, r, c; while (m -- ) { scanf("%d%d%d", &l, &r, &c); insert(l ,r, c); } for (int i = 1; i <= n; i++) { b[i] += b[i - 1]; printf("%d ",b[i]); } return 0; }
798.差分矩阵
#include<iostream> using namespace std; const int N = 1010; int a[N][N], b[N][N]; int n, m, q; void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); insert(i, j, i, j, a[i][j]); } } // for (int i = 1; i <= n; i++) // for (int j = 1; j <= m; j++) // insert(i, j, i, j, a[i][j]); int x1, y1, x2, y2, c; while (q--) { scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); insert(x1, y1, x2, y2, c); } // for (int i = 1; i <= n; i++) // for (int j = 1; j <= m; j++) // b[i][j] += b[i - 1][j] + b[i][j -1] - b[i - 1][j - 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { b[i][j] += b[i - 1][j] + b[i][j -1] - b[i - 1][j - 1]; printf("%d ", b[i][j]); } printf("\n"); } return 0; }
双指针算法
799.最长连续不重复子序列
#include<iostream> using namespace std; const int N = 100010; int a[N], b[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int res = 0; for (int i = 0, j = 0; i < n; i++) { b[a[i]]++; while (b[a[i]] > 1) { b[a[j]]--; j++; } res = max(res, i - j + 1); } cout << res; return 0; }
800.数组元素的目标和
#include<iostream> using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int n, m, x; int main() { scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < m; i++) scanf("%d", &b[i]); int j = m - 1; for (int i = 0; i < n; i++) { while (j >= 0 && a[i] + b[j] > x) j--; if (a[i] + b[j] == x) printf("%d %d" ,i ,j); } return 0; } 2816.判断子序列 #include<iostream> using namespace std; const int N = 1e5 + 10; int n ,m; int a[N], b[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < m; i++) scanf("%d", &b[i]); int i = 0, j = 0; while (i < n && j < m) { if (a[i] == b[j]) i++; j++; } if (i == n) puts("Yes"); else puts("No"); return 0; }
位运算
801.二进制中一的个数
#include<iostream> using namespace std; int main() { int n; scanf("%d", &n); while (n--) { int x, res = 0; scanf("%d", &x); for (int i = x; i; i -= i & -i) res++; cout << res << ' '; } return 0; }
离散化
vector<int> alls; //存储所有待离散化的值 sort(alls.bedin(), alls.end()); // 将所有值排序 alls.earse(unique(alls.begin(), alls.end()), alls.end()); //去掉重复元素 //二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于 x 的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; //映射到 1， 2， 3， ...n }
802.区间和
https://www.acwing.com/activity/content/problem/content/836/
unique在stl中的使用
https://blog.csdn.net/qq_36561697/article/details/82356053
#include <iostream> #include <vector> #include<algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; vector<int> alls; vector<PII> add, query; int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i++) { int l ,r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } // 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 处理插入 for (auto item : add) a[find(item.first)] += item.second; // 预处理前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; // 处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }
803.区间合并
https://www.acwing.com/activity/content/problem/content/837/
void merge(vector<PII> &segs){ vector<PII> res; // 左端点排序 sort(segs.begin(), segs.end()); // 左右端点初始化，-无穷 int start = -2e9, end = -2e9; for(auto seg: segs){ if(end < seg.first){ // 初始的[-无穷，-无穷]区间要跳过，不能装入 if(start != -2e9) res.push_back({start, end}); start = seg.first, end = seg.second; } else end = max(end, seg.second); } // 有两个作用，1.是防止n为0，把[-无穷，-无穷]压入；2.是压入最后一个（也就是当前）的区间，若n>=1，if可以不要 if (start != -2e9) res.push_back({start, end}); //覆盖segs segs = res; }
第二讲数据结构
单链表
826.单链表
双链表
827.双链表
栈
828.模拟栈
3302.表达式求值
队列
829.模拟队列
单调栈
830.单调栈
单调队列
154.滑动窗口
KMP
831.KMP字符串
835.Tire字符串统计
143.最大异或对
并查集
并查集
1、将两个集合和合并
2、询问两个集合是否在一个集合当中
belong[x] = a
if (belong[x] == belong[y]) o(1)
基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个结点存储它的父节点，p[x]表示x的父节点
问题1：如何判断树根：if(p[x] == x)
问题2：如何求x的集合编号：while (p[x] != x) x = p[x];
问题3：如何合并两个集合：p[x] 是 x的 集合编号，py是y的集合号。p[x] = y
find(x) 和 find(p[x])有啥区别？不都是返回祖宗节点么？
p[x]是x的父节点，满足p[x]==x的是根节点，find(p[x])相当于找父节点的父节点，逐层往上找
确实都是返回祖宗结点，没区别
find(x)会进入死循环
836.合并集合
https://www.acwing.com/activity/content/problem/content/885/
#include <iostream> using namespace std; const int N = 1e5 + 10; int n, m; int p[N]; int find (int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) p[i] = i; while (m -- ) { int a, b; char op[2]; scanf("%s%d%d", op, &a, &b); if (op[0] == 'M') p[find(a)] = find(b); else { if (find(a) != find(b)) puts("No"); else puts("Yes"); } } return 0; }
837.连通块中的点数量
https://www.acwing.com/activity/content/problem/content/886/
#include<iostream> using namespace std; const int N = 1e5 + 10; int n, m; int p[N], cnt[N]; int find (int x) { if (x != p[x]) p[x]=find(p[x]); return p[x]; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <=n; i++) { p[i] = i; cnt[i] = 1; } while (m -- ) { char op[3]; int a, b; scanf("%s", op); if (op[0] == 'C') { scanf("%d%d", &a, &b); if (find(a) == find(b)) continue; cnt[find(b)] += cnt[find(a)]; p[find(a)] = find(b); } else if (op[1] == '1') { scanf("%d%d", &a, &b); if (find(a) == find(b)) puts("Yes"); else puts("No"); } else if (op[1] == '2') { scanf("%d", &a); printf("%d\n", cnt[find(a)]); } } return 0; }
