Freedom Coding

位运算二进制第k位上的数字是几 n >> k & 1 获取n的二进制表示 #include <bits/stdc++.h>using namespace std;int main(){ int a = 10; for(int i = 3;i >= 0;i--) { cout << (a >> i & 1) << endl; } return 0;} lowbit函数的引入 lowbit函数主要是用来获取最后一个1，即以后的位数 比如n = 10100， lowbit(n) -> 100 实现方式 前提条件：~x + 1等价于 -x 我们是通过x & (~x + 1) 来实现(等价于x & -x) 比如x 为 10001000去反后的结果为01110111 ，这个时候再加上一相当于对最后一个0及以后进行去反 -> 01111000 最后去&操作，x最后一个1后面位值都 ...

前缀和什么是前缀和 前缀和数组a[i]代表的是从数组下标1 - i 的和，我们可以通过ai的含义从而推出某一段区间内的sum 一维前缀和假如我们想要得到i 到j范围内的和 我们已知a数组，我们可以求出S数组 S[I]数组代表的是从1 - i a数组的和 公式为s[j] - s[i - 1] #include <bits/stdc++.h>using namespace std;const int N = 100010;int a[N],s[N];int main(){ int n,m; cin >> n >> m; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i]; while(m--) { int l,r; cin >> l >> r; cout << s ...

区间合并区间合并主要需要考虑三种情况 两个区间没有交集 两个区间有交集 思路 我们可以使用st和ed用来控制每一次最大区间的左右端点 根据贪心的策略，我们可以先通过left的值进行排序 考虑多种情况，如果发现上一次的ed比这一次的st小的话，说明这是一种全新的区间 否则的话，合并两个区间ed取两个右端点的最大值 #include <bits/stdc++.h>using namespace std;const int N = 2e9;typedef pair<int,int> PII;vector<PII> v,ans;int a,b;int main(){ int n; cin >> n; while(n--) { cin >> a >> b; v.push_back({a,b}); } sort(v.begin(),v.end()); int st = -2e9, ed = -2e9; f ...

双指针 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。 在数组的区间问题上，暴力算法的时间复杂度往往是 O(n2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。 双指针模版 for(int i = 0,j = 0;i < n;i++) { while(i < j && check(i,j)) j++; // 每一道题目的具体逻辑} 双指针经典案例 题目：首先保证输入的字符串每一个单词之间以一个空格隔开，最终我们需要将每一个单词切割出来 思路 我们可以定义两个指针，i指针用来指向每一个单词的头，j指针用来向后移动，最终打印i,j之间的字符，更新起点位置 代码 #include <bits/stdc++.h>using namespace ...

图 图的存储我们可以想象成哈希中的拉链法，也是同样的道理，在每一个点上延伸出一条链表，从该点出发可到达并且距离为1的点 初始化临界表 h[N]用来对每一个点的头结点进行存储 ne[N]用来指向链表中的下一个结点 e[N]用来存值 每一结点在没有指向的时候，我们将该结点的头结点初始化为-1 存储模版 void add(int a,int b) { e[idx] = b; //e[b的编号] = b的值(b在图中的位置) ne[idx] = h[a]; //将b这个结点连接到a这条链上 h[a] = idx++; //将a链表的头结点设置为新插入的b的idx} 树和图的深度优先遍历 void dfs(int u) { st[u] = 1; //代表u这个点已经遍历过了 for(int i = h[u];i != -1;i = ne[i]) { //遍历u链表的同时，遍历链表上元素下的元素 int j = e[i]; if(!st[j]) dfs(j); }& ...

refuse STL

x ?==> p[x]

拓扑序列概念 拓扑序列遵循一个规则，在遍历图的时候必须保证一条有向边的起点排在终点的前面 举一个例子 提供的有向边为：1 -> 2 | 2 -> 3 | 1 -> 3满足条件 而1 - > 2 | 2 -> 3 | 3 -> 1就不满足条件 如何实现拓扑序列？ 找到所有入度为0的点，将其放入到队列中 将这些点从队列中弹出，并且将这些点所指向的终点的点入度减1 最后判断这些点是否入度为0，如果为0重新放入到队列中，循环这三种情况 Step1：找到入度为0的点 for(int i = 1;i <= n;i++) { if(!in(i)) q.push(i);} Step2：使该点指向的终点入度减1 while(q.size()) { int fr = q.front(); q.pop(); for(int i = h[fr];~i;i = ne[i]) { int j = ne[i]; in[j]--; }} Step3：检查入度为0，重新放入队列 w ...

排序 排序顾名思义，我们可以通过排序对数组进行有序化排列，进一步实现更多排序后的功能 排序中最常用的两种方式分别为 快速排序 归并排序 快速排序 快速排序主要使用的算法为分治，将一串数据分而治之，最终变成一小段数据进行处理 这里我们主要使用双指针的思想实现 最终实现的目的 在排序的过程中，我们需要定义一个标准值x，将小于x的放在头指针的左边，大于x的放在尾指针的右边 比较过程分析首先定义一个x，作为比较的条件 我们定义一个头指针，初始位置为l，尾指针，初始位置为r，我们去判断arr[l] < x如果成立让 l不停的递增，如果突然不成立了，我们接着判断arr[r] > x，同理如果不成立了，我们需要判断指针是否交叉，如果没有的话，将arr[l]和arr[r]进行交换操作，最终l >= r return返回 #include <iostream>using namespace std;const int N = 100010;int q[N];void quick_sort(int q[], int l, int r){ if (l & ...

数学知识数论主要分为两种数学方法求解 质数 约数 质数的定义 质数是从2开始的自然数，这个数只能有两个约数分别是自己和1，质数又被称为素数 试除判断质数暴力判断质数 bool pd(int x) { if(x < 2) return false; for(int i = 2;i < x;i++) { if(x % i == 0) return false; } return true;} 很明显时间复杂度为O(n)还是很高的 优化：我们发现构成非质数的两个数往往都是成对存在的，即x = d * d，这个时候我们只需要判断小的那一部分是否满足条件即可，即i <= n / i 注意 不推荐使用sqrt(x)或者是i * i <= n，sqrt每一次循环都要执行一回，时间复杂度比较高，后面哪种容易溢出，使i * i变成负数 bool pd(int x) { if(x < 2) return false; for(int i = 2;i <= n / i;i++) { ...