寒假集训笔记

2022/1/26 23:09:59

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

注意事项(并不完整):
  (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. 负数的二进制是反码的补码

  原码 补码 反码
1 0000 0001 0000 0001

0000 0001

-1 1000 0001 1111 1110 1111 1111

 

 

 

 

 

  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;



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


扫一扫关注最新编程教程