acwing

二分模板 1.二分模板二分的本质并不是单调性，而是一种边界。 定义某种性质，使得右半边的部分全部满足该种性质，而左半边的部分全部都不满足该种性质。而二分可以寻找性质的边界。 12345678910111213141516171819//区间[low, high]被划分成[low, mid - 1]和[mid, high]时使用:while (low < high) { int mid = low + high + 1 >> 1; if (check(mid)) low = mid; else high = mid - 1;}//区间[low, high]被划分成[low, mid]和[mid + 1, high]时使用:while (low < high) { int mid = low + high >> 1; if (check(mid)) high = mid;//check判断mid是否满足性质 else low = mid + 1;}//小数二分const double eps = 1e-6;//eps表示精度 取决于题目对精度的要求while (high - low > 1e-8) { double mid = (low + high) / 2; if (check(mid)) low = mid; else high = mid;} 1.AcWing789.数的范围 123456789101112131415161718192021222324252627282930313233343536373839#include<iostream>using namespace std;const int MAX = 1e6 + 10;int n, m, arr[MAX];//整数二分模板//思路：对数组进行二分 分别查找某个数字出现范围的起始坐标与终止坐标int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", ...

大整数运算 1.AcWing791.高精度加法12345678910111213//大整数加法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;} 2.AcWing792.高精度减法12345678910111213141516171819202122232425262728293031//大整数减法vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; int t = 0; for (int i = 0; i < A.size(); ++i) {//A.size() > B.size() 故可以省略简写if条件 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;}bool cmp(vector<int> ...

前缀和与差分 1.AcWing795.一维前缀和1234567891011121314int n, m;int arr[MAX], prefix[MAX];int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]); for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + arr[i];//前缀和数组初始化 while (m--) { int low, high; scanf("%d %d", &low, &high); printf("%d\n", prefix[high] - prefix[low - 1]); } return 0;} 2.AcWing796.二维前缀和1234567891011121314151617int n, m, q;int arr[MAX][MAX], prefix[MAX][MAX];nt main() { scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &arr[i][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + arr[i][j];//前缀初始化 while (q--) { int x1, y1, x2, y2; ...

双指针算法 1.算法模板1234for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++; /*具体问题逻辑*/} 常见双指针问题： 对于一个序列，用两个指针维护一段区间 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 2.双指针练习（1）AcWIng799.最长连续不重复子序列方法1：暴力法1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;const int MAX = 100010;int n;int a[MAX], mark[MAX];bool check(int low, int high) { for (int i = low + 1; i <= high; ++i) { for (int j = low; j < i; ++j) { if (a[i] == a[j]) return false; } } return true;}int main() { int res = 0; cin >> n; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { if (check(j, i)) res = max(res, i - j + 1); } } cout << res << endl; return 0;} 方法2：双指针法仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了： 比如 j = 0，i ...

二进制中1的个数 AcWing801.二进制中1的个数 求n的第k位数字: n >> k & 1 返回n的最后一位1：lowbit(n) = n & -n 1234567891011121314151617181920#include<iostream>using namespace std;int lowbit(int x) { return x & -x;}int main() { int n; scanf("%d", &n); while (n--) { int x; int res = 0; scanf("%d", &x); while (x) { x -= lowbit(x);//每次减去x的最后一位1 res++; } printf("%d", res); } return 0;}

离散化与区间合并 1.离散化模板离散化问题的性质，整个值域的跨度很大，但是数据非常的稀疏。 123456789101112131415//将所有值排序 并去掉重复元素vector<int> nums;sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid = low + high >> 1; if (nums[mid] >= x) high = mid; else low = mid + 1; } return high + 1;//映射到1, 2, ...n} 2.AcWing802.区间和1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef pair<int, int> PAIR;const int MAX = 300010;int n, m;int a[MAX];int prefix[MAX];vector<int> nums;//离散化数据存储容器vector<PAIR> add, query;//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid ...

链表 1.单链表数组实现的链表可以做指针实现的链表的所有事情，且数组实现的链表更快（静态链表），动态链表new操作太慢。 用数组模拟单链表，使用单链表构建一个邻接表（n个链表），用邻接表（最短路问题、最小生成树、最大流）进行存储图和树， 123int head;//头结点的next指针int data[MAX], next[MAX];//结点数据data、下一个结点的下标nextint currt;//当前可用点的下标 2.双链表用数组模拟双链表，双链表可用于优化某些问题， 12int dataa[MAX], left[MAX], right[MAX];//结点数据dataa、下一个结点的下标nexttint currt;//当前可用点的下标 3.AcWing826.单链表12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>using namespace std;const int MAX = 100010;int head;//头结点的next指针int dataa[MAX], nextt[MAX];//结点数据dataa、下一个结点的下标nexttint currt;//当前可用点的下标void link_list_init() { head = -1; currt = 0;}void link_list_head_insert(int x) { dataa[currt] = x; nextt[currt] = head; head = currt; currt++;}void link_list_insert(int idx, int x) { dataa[currt] = x; nextt[currt] = nextt[idx]; nextt[idx] = currt; currt++;}void link_list_delete(int idx) { nextt[idx] = nextt[ne ...

栈 1.AcWing828.模拟栈123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>using namespace std;const int MAX = 100010;typedef struct { int data[MAX]; int top;} Stack;Stack stack1;void stack_push(Stack &stack, int x) { stack.data[stack.top] = x; stack.top++;}int stack_pop(Stack &stack) { int ret = stack.data[stack.top]; stack.top--; return ret;}int stack_top(Stack &stack) { return stack.data[stack.top - 1];}bool stack_empty(Stack &stack) { if (stack.top > 0) return false; return true;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int m; cin >> m; string opt; int x; int top; while (m--) { cin >> opt; if (opt == "push") { cin >> x; stack_push(stack1, x); } else if (opt == "pop") { stack_pop(stack1); } else if (opt == "empty") &# ...

队列 1.AcWing829.模拟队列12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<iostream>using namespace std;const int MAX = 100010;typedef struct { int head; int tail; int data[MAX];} Queue;Queue queue1;void queue_push(Queue &queue, int x) { queue.data[queue.tail] = x; queue.tail++;}int queue_pop(Queue &queue) { int ret = queue.data[queue.head]; queue.head++; return ret;}int queue_head(Queue &queue) { return queue.data[queue.head];}bool queue_empty(Queue &queue) { if (queue.head < queue.tail) return false; return true;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int m; cin >> m; string opt; int x; int data; while (m--) { cin >> opt; if (opt == "push") { cin >> x; queue_push(queue1, x); } else if (opt == "pop") { queue_pop(queue1); } e ...

欧拉函数