寒假集训笔记

本文主要是介绍寒假集训笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

注意事项(并不完整):
　　(1)i式筛求素数(用bool型数组,大的数int会爆MLE)
　　(2)for(int j = i;j <= n/i;j++) 能除的就不要乘(i*j可能会爆int)
　　(3)快速幂别忘了long long
一、memset (40 -> 6亿)
　　1.int
　　　　0x7f一个很大的数(略小于0x7fffffff)
　　　　0xaf一个很小的数
　　2.double
　　　　127一个很大的数
　　3.16进制:0xff
　　4.无符号整型
　　　　ffffffff一个很大的数
二、最短路(负权回路无最短路)
　　1.Floyd
　　　　最简单的最短路径算法
　　　　可以计算图中任意两点之间的最短路径
　　　　Floyd算法的时间复杂度是n^3
　　　　适合于出现负权边的情况
　　　　代码实现最为简单
　　2.Dijstra
　　　　时间稳定的计算一个点到其他所有点的最短路径算法
　　　　不能用于计算带负权的图,一般使用堆优化
　　3.Bellman ford
　　　　可以处理带负权边的最短路
　　　　但不能处理带负环的最短路(此时不存在最短路)
　　　　因复杂度较高,一般不建议使用
　　4.Spfa
　　　　复杂度O(玄学)
　　　　一般在实测堆优化dijstra算法无法通过时使用
　　　　可能更快也可能更慢,且可以被卡成O(n*m)
　　　　//PS:堆优化存的是节点,不是边;利用邻接链表时别忘取cs[i].to
三、并查集(树型数据结构)
　　1.操作
　　(1)初始化
　　　　for(int i = 1;i <= n;i++) father[i] = i;
　　(2)查询:查找根节点
　　(3)路径压缩

1 (查找并路径压缩)
2 int find(int x){
3 　　if(father[x] != x) father[x] = find(father[x]);
4 　　return father[x];
5 }

　　(4)合并:两个元素所在集合合并为一个集合

1 void unionn(int x,int y){
2 　　x = find(x);
3 　　y = find(y);
4 　　father[y] = x;
5 }

　　2.用某个元素所在树的根节点表示该点所在的集合
　　3.找爹 for(int i = 1;i <= n;i++) if(find(i) == i) sum++;
四、离散化
　　1.map

1 #include<map>
2 map<string,int> mp;
3 string a;
4 cin >> a;
5 mp[a] = 0;
6 mp["Hello"] = 50;//映射
7 mp.find(a);//查找
8 mp.clear()//清空

　　2.STL(例题:程序自动分析)
五、最小生成树
　　1.Prim
　　　　min[v] 表示蓝点v与白点相连的最小边权
　　2.Kruskal(克鲁斯卡尔)
　　　　利用并查集来实现
六、vector

 1 #include <vector>
 2 vector<int> a;
 3 push_back 在数组的最后添加一个数据
 4 pop_back 去掉数组的最后一个数据
 5 at 得到编号位置的数据
 6 begin 得到数组头的指针
 7 end 得到数组的最后一个单元+1的指针
 8 front 得到数组头的引用
 9 back 得到数组的最后一个单元的引用
10 max_size 得到vector最大可以是多大
11 capacity 当前vector分配的大小
12 size 当前使用数据的大小
13 resize 改变当前使用数据的大小,如果它比当前使用的大,者填充默认值
14 reserve 改变当前vecotr所分配空间的大小
15 erase 删除指针指向的数据项
16 clear 清空当前的vector
17 rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
18 rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
19 empty 判断vector是否为空
20 swap 与另一个vector交换数据

七、树状数组
　　(单点修改,区间查询->普通树状数组)
　　(单点查询,区间修改->差分)
　　1. 负数的二进制是反码的补码

　　2.x&(-x) 返回x转二进制后最后一个1的位置

　　3.构造方法

　　　　(1)每个树状数组的元素由2^k个初始数组元素相加而成

　　　　(2)树状数组中某个节点i的父节点的下标为i+lowbit(i)
　　　　(3)树状数组中某个节点i的兄弟(左边的)下标为i-lowbit(i)

1 int lowbit(int x){
2     return x & (-x);
3 }

　　4.单点修改 (时间复杂度O(lgn))
　　　　若要对原数组的某个元素加上一个val值
　　　　应该对涉及到该点的所有树状数组的点进行修改
　　　　也就是沿父节点一路往上,直到区间的最右端

1 void update(int x,int val){
2     while(x <= n){
3         c[x] += val;
4         x += lowbit(x);
5     }
6 }

　　5.询问前缀和 (时间复杂度O(lgn))
　　　　对于询问的区间,从右端点开始
　　　　每次累加,每次移到左边兄弟的树状数组值
　　　　即每次下标减lowbit值

1 int query(int x){
2     int sum = 0;
3     while(x){
4         sum += c[x];
5         x -= lowbit(x);
6     }
7 }

　　6.区间查询

1 int getsum(int x){
2     int s = 0;
3     while(x > 0){
4         s += c[x];
5         x -= lowbit(x);
6     }
7     return s;
8 }

　　7.优化(卡常小技巧)
　　　　(1)非递归函数前加inline,反复调用时可优化读取速度
　　　　(2)快读快输

 1 //快读
 2 inline int read(){
 3     int x = 0,f = 1;
 4     char c = getchar();
 5     while(c > '9'||c < '0'){
 6         if(c == '-') f = -1;
 7         c = getchar();
 8     }
 9     while(c >= '0'&&c <= '9'){
10         x = (x << 3) + (x << 1) + (c ^ 48);
11         c = getchar();
12     }
13     return x*f;
14 }

　　8.差分
　　　　把每个数和它前一个数的差值来建立树状数组
　　　　某位置原本所代表的数,就是从开始到这个位置的区间和
　　　　将区间[l,r]加上x的话
　　　　只需要d[l] += x;d[r+1] -= x;
八、二维树状数组
　　1.规律
　　　　不管是横坐标还是纵坐标
　　　　将他们单独拿出来,他们都符合x += lowbit(x)
　　2.修改

1 void updata(int x,int y,int key){
2     for(int i = x;i <= n;i += lowbit(i)){//注意结束位置,n还是maxn,maxn可能会小于n,不能全部修改
3         for(int j = y;j <= n;j += lowbit(j))
4         c[i][j] += key;
5     }
6 } 

　　3.查询

1 int sum(int x,int y){
2 　　int result = 0;
3 　　for(int i = x;i > 0;i -= lowbit(i)){
4 　　　　for(int j = y;j > 0;j -= lowbit(j))
5 　　　　　　result += c[i][j];
6 　　}
7 　　return result;
8 }

　　4.二维前缀和

1     　　　　　　x1,y2
2 ________________ ____________ x2,y2
3 |　　　　　　　　　 　　　　　　　|
4 |　　　　　　　　　 　　　　　　　|
5 |_______________x1,y1　　　　 |x2,y1
6 |　　　　　　　　　|　　　　　　　|
7 |　　　　　　　　　|　　　　　　　|
8 |　　　　　　　　　| 　　　　　　 |
9 |_______________|____________|

　　矩形内的和:
　　query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
九、异或
　　性质:满足交换律和结合律
　　交换律:A ^ B = B ^ A;
　　结合律:A ^ (B ^ C) = (A ^ B) ^ C;
　　恒等律:X ^ 0 = X;
　　归零律:X ^ X = 0;
　　自反:A ^ B ^ B = A ^ 0 = A;
　　对于任意的X:X ^ (-1) = -X-1;
　　如果A ^ B = C成立,那么A ^ B = C,B ^ C = A;

这篇关于寒假集训笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！