Polaris-hzn8

离散化与区间合并 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 ...

欧拉函数

欧拉函数 1.欧拉函数 欧拉函数定义：1~n中与n互质的数的个数，例$φ(6) = 2$ 如果 $N = p1^{α1}p2^{α2}….*pn^{αn}$ 则有公式：$φ(N) = N*(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pn})$； 时间复杂度：$O(n) = \sqrt{n}$ 2.AcWing873.欧拉函数对于每一个数字，分别从定义出发求其欧拉函数： 12345678910111213141516171819202122#include<iostream>using namespace std;int main() { int m; cin >> m; while (m--) { int num; cin >> num; int res = num;//最后结果 //1.分解质因数 for (int i = 2; i <= num / i; ++i) { if (num % i == 0) { /* i为num的一个因子 */ res = res / i * (i - 1);//res = res * (1 - 1/i);公式内容 while (num % i == 0) num /= i; } } //2.说明num有一个大于1的质因数 if (num > 1) res = res / num * (num - 1); cout << res << endl; } return 0;} 注意：在 res = res / num * (num - 1)中, 不能写成 res = res * (num - 1) / num;顺序不可颠倒 3.AcWing874.筛法求欧拉函数如果需要求出1~N中，每一个数字的欧拉函数，这时再使用公式法 ...

快速幂 1.快速幂快速幂的核心：反复平方法 快速幂即快速的求出 $a^kmodp$ 的结果，可以在 $O(logk)$ 的时间复杂度内求出结果，其中满足 $1≤a,p,k≤10^9$， 12345//暴力法O(k)res = 1;for (int i = 1; i <= k; ++i) { res = res * a % p;} 12345678//快速幂O(logk)int res = 1;while (k) { if (k & 1) res = (long long)res * a % p; k >>= 1;//最后一位抹去 a = (long long)a * a % p;}return res; 1.AcWing875.快速幂123456789101112131415161718192021222324#include<iostream>using namespace std;//a^k % pint qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (long long)res * a % p; k >>= 1;//最后一位抹去 a = (long long)a * a % p; } return res;}int main() { int m; scanf("%d", &m); while (m--) { int a, k, p; scanf("%d%d%d", &a, &k, &p); printf("%d\n", qmi(a, k, p)); } return 0;} 2.AcWing876.快速幂求逆元 考察：费马定理与快速幂 1234567891011121314151617181920212223242526#incl ...

扩展欧几里得算法 裴蜀定理：对于任意正整数 $a、b$ ，一定存在非零整数 $x、y$ ，使得 $ax + by = (a, b)$ （最大公约数） 1.AcWing877.扩展欧几里得算法123456789101112131415161718192021222324252627282930313233#include<iostream>using namespace std;// (a, b) = (b, a mod b)// return b ? gcd(b, a % b) : a;int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b);}// ax + by = (a, b)int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, y, x);//递归求 y -= a / b * x; return d;}int main() { int m; scanf("%d", &m); while (m--) { int a, b, x, y; scanf("%d%d", &a, &b); exgcd(a, b, x, y); printf("%d %d\n", x, y); } return 0;} 2.AcWing878.线性同余方程 给定$a、m、b$，求一个整数 $x$ 使得 $ax≡b(mod~m)$ 1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;// (a, b) = (b, a mod ...

只出现一次的数字 原题链接：https://leetcode.cn/problems/WGki4K/description/ 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 1.暴力法1234567891011121314151617class Solution {public: int singleNumber(vector<int> &nums) { vector<int> ans = nums; sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); for (int i = 0; i < ans.size(); ++i) { int count = 0; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == ans[i]) count++; if (count > 1) break; } if (count == 1) return ans[i]; } return -1; }}; 2.哈希法哈希法：哈希映射统计数组中每个元素的出现次数，在统计完成后，遍历哈希映射即可找出只出现一次的元素。 12345678910111213141516class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; unordered_map<int, int> unmap; for (int num : nums) unmap[num]++; pair<i ...

前n个数字二进制中1的个数 原题链接：https://leetcode.cn/problems/w3tCBm/ 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。 1.一般思路12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int x = i; int count = 0; while (x) { if (x % 2 == 1) count++; x /= 2; } ans.push_back(count); } return ans; }}; 2.位运算12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int count = 0; int x = i; while (x != 0) { count++; x = x & (x - 1); } ans.push_back(count); } return ans; }}; 3.动态规划对于所有的数字，只有奇数和偶数两种： 奇数：二进制表示中，奇数一定比前面那个偶数多一 ...