algorithm_know

2.16

算法竞赛常用STL万字总结

降低时间复杂度的方法（降低运行时间防止超时）

使用平方根去约束数的循环范围

应用场景：完全数，质数

前缀和

得到某一段数组 [l,r] 的和，常规循环计算的复杂度为 O(n) ，使用前缀和就可以直接使用 S(r) - S(l-1) ，复杂度为O(1)

差分

树状数组

1. O(log)的时间复杂度去实现单点修改和区间查询
2. 数组下标一定要从1开始
3. 一个数的二进制表示中末尾有几个0就在第几层

2.17

位运算

求 n 的二进制表示的第 k+1 位（计数从1开始）数字：n >> k & 1
n & 1 判断第1位的数字

二进制中1的个数

for(int i=0;i<n;i++){
    int res = 0;
    while(a[i]){
        if((a[i] & 1) == 1) res++;
        a[i] = a[i] >> 1;
    }
    cout << res << " ";
}

返回 n 的最后一位1所对应的值：lowbit(n) = n & -n = n & (n^(n-1))
假设一个数的二进制最低位的1在从右往左数的第k位，那么它的lowbit值就是2^(k-1)
树状数组C[x] = [x-lowbit(n) , x] 原数组中这段区间的和

3.25

n次方幂

//负数要先转换成正数去计算n次方根
    if(n < 0){
        flag = true; 
        n = -n;
    }
    double res = pow(n,(double)1/3); //使用求n次幂函数，来求n次方根

3.26

线段数组

tips

1. 线段树是一棵平衡二叉树。母结点代表整个区间的和，越往下区间越小
2. 每个节点p的左右子节点的编号分别为 2p 和 2p+1
3. 节点p存储区间[l,r]的和，设 mid = floor(l+r/2) ; 左节点存储[l,mid]的和， 左节点存储[mid+1,r]的和

建立线段数组

struct {
    int l,r;
    int sum;
}tr[N*4];

//u位节点编号，l和r为区间左右端点
void build(int u, int l, int r){
    if(l == r) return tr[u] = {l,r,w[l]}; //抵达叶子节点，为其赋值
    int mid = (l+r) / 2;  //向下取整
    build(2*u, l, mid); //向左子树递归
    build(2*u+1, mid+1, r); //向右子树递归
    tr[u].sum = tr[2*u].sum + tr[2*u+1].sum //递归完左右子树后向上回溯
}

区间查询

把区间内的叶子节点相加

单点修改

第k小数

int t, n, k;
scanf("%d", &t);
while (t--) {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        list[i] = read();
    }

    // 将第k小的数放在 k-1 位置，左边的数都比它小，右边的数都比它大，但都是无序的
    nth_element(list, list + k - 1, list + n);
    // 由于数据量太大，下面两种方法会超时
    // 快速排序
    // sort(list, list + n);
    // 将第k小的数放在 k-1 位置，左边的数都比它小，而且是有序的，右边的数都比它大，但右边是无序的
    // partial_sort(list, list + k - 1, list + n);
    printf("%d\n", list[k - 1]);
}

二分查找

首先，binary_search()函数，作用：对一个不降序列进行二分查找，如果所查找的值在序列中出现了，返回true，没有出现，返回false。

然后，lower_bound()函数，作用：对一个不降序列进行二分查找，返回第一个大于等于所查找的值的元素下标，注意返回的是指针变量！！！

最后，upper_bound()函数，作用：对一个不降序列进行二分查找，返回第一个大于所查找的值的元素下标，注意返回的是指针变量！！！

无穷大和无穷小

指定一个数为无穷大或无穷小：INT_MIX INT_MAX
要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))
要把一段内存全部置为无穷小，我们只需要memset(a,0xc0,sizeof(a))

map

map[key] = value

查找map中某个key是否存在/具体位置

mp.count(key)
查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
mp.find(key)
返回键为key的映射的迭代器 $O(logN) $ 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end()

set

set里面的元素不重复 且 有序

如何将字符串转换成数字

String str=“2019”;
char s[]=str.toCharArray();
int x=0;
for(int i=0;i<s.length;i++){
x=x*10+str[i]-‘0’;
}

结构体数组排序

当数组是从1开始赋值时，sort函数也要加1

for(int i=1;i<=n;i++){
		cin >> a[i].t >> a[i].d >> a[i].l;
	}
	sort(a+1,a+n+1,cmp); //由于数组是从1开始赋值的，因此排序函数也要加1 

#include<iostream>
#include<algorithm>
using namespace std;

struct Student {
    char name[11];
    int solve;
    int time;
}p[10000];

//按照题数，再罚时间，再名字（名字按字典序排列）
bool cmp(const Student& a, const Student& b)
{
    if (a.solve != b.solve)
     { 
        if (a.solve > b.solve)
            return true;
        else
            return false;
    }
    else if (a.time != b.time)
           return a.time < b.time;
    else
          return (strcmp(a.name, b.name) < 0);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
      cin>>p[i].name>>p[i].solve>>p[i].time;
    sort(p,p+n,cmp);//在主函数中调用，结构体排序；
    for(int i=0;i<n;i++)
      cout<<p[i].name;
    return 0;
}

max_element+min_element

返回最大最小值的下标所对应的地址

//函数都是返回地址，需要加*取值
int indx = max_element(a, a + n) - a;
int mx = *max_element(a, a + n);
int mn = *min_element(a, a + n);