C++/C算法n0t3
#

«算法»
#

qsort快排(c语言)
#

1.qsort函数原型

1void qsort(void *base, size_t nmemb, size_t size, 
2           int (*compar)(const void *, const void *));

2.具体写法（1）先写比较函数（返回的是整形）

1// 升序排序（从小到大）
2int cmp_asc(const void *a, const void *b) {
3    return (*(int*)a - *(int*)b);
4}
5// 降序排序  （从大到小）
6int cmp_desc(const void *a, const void *b) {
7    return (*(int*)b - *(int*)a);
8}

解释：因为排序的类型可能是int,double等各种，所以用const voida表示可以指向任何类型的指针，然后在return中先将a转化成对应题目类型的指针例如（int），再在前面加* 表示指针所指的具体值（2）再在主函数中调用

1qsort(a,n,sizeof(int),cmp);

a表示要排序的数组的首地址 n表示数组长度 sizeof（int）表示这个数组类型的数据长度 cmp是提前写好的比较函数的名称 3.原理比较函数cmp中，（~~有点难理解~~但很重要！！）若返回负值—>将参数a排在参数b前面若返回0—>参数a，参数b顺序不变若返回正值—>将参数a排在参数b后面依此可以写各种其他不同排序：（待开发）

GCD&LCM
#

最大公约数函数(gcd):

1int gcd(int a,int b){
2    if(b==0){
3        return a;
4    }
5    return gcd(b,a%b);//欧几里得算法,辗转相除法,递归版
6}//以上参数顺序不可以调换！

最小公倍数函数(lcm):

1int lcm(int a,int b){
2    if(a==0 || b==0){
3        return 0;
4    }
5    //return (a*b)/gcd(a,b);为了防止溢出，先除以gcd，再乘：
6    return a/gcd(a,b)*b;//***
7}

两两乘积之和化简
#

eg:一个数组a[n];计算数组中所有不同的两个元素的乘积之和（前后顺序相反的算同一组）

即a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+a(n−2)⋅a(n−1)+a(n−2)⋅an+a(n−1)⋅an

算法思维：

具体代码：

1ll a[n];//ll 表示long long
2ll total_sum = 0;
3ll square_sum = 0;
4for(ll i = 0;i<n;i++){
5    cin>>a[i];
6    total_sum = total_sum+a[i];
7    square_sum = square_sum+a[i]*a[i];
8}
9ll sum = (total_sum*total_sum-square_sum)/2;

一维前缀和
#

1.为何诞生？ Runtime Error：个人是因为，在计算数组的各个子数组，各个元素之和时复杂度太大前缀和算法能够帮助提高效率，处理更大更复杂的数据 2.定义前缀和数组a[n]; 令sum[i] = a1+a2+⋯+ai（其中sum[0] = 0） 3.具体用法计算一维数组的各个前缀和：

1int a[n];//先定义一个大小乱序的数组
2//这里省略数组初始化...
3long long presum[n+1] = {0};//初始化前缀和先都为0,大小为n+1防止越界(一定要开足空间！！)
4for(int i = 1;i<=n;i++){//i从1开始，更符合人类习惯，"前i个的和..."
5    presum[i] = a[i-1]+presum[i-1];//第i个元素+前i-1个
6}

4.结合例题题目（一）：利用前缀和，计算数组的各个子数组中的各个元素之和解法：

1int a[n];
2//这里省略初始化数组，省略前缀和公式
3for(int l = 0;l<n;l++){
4    for(int r = l;r<n;r++){
5        //a[r]是第r+1个元素，a[l]是第l+1个元素***
6        int sum = presum[r+1]-presum[l];//***
7    }
8}

二维前缀和
#

1.定义二维前缀和

一个n*m的二维数组矩阵a【n】【m】；令sum【i】【j】 = $\sum_{i=1}^{n} \sum_{j=1}^{m} \text{a}[i][j]$;

2.具体用法

计算二维数组的各个前缀和

 1//注意！为了后续方便，若要计算二维数组前缀和
 2//初始化赋值时下标从1开始！！***
 3int a[n+5][m+5];
 4for(int i = 1;i<=n;i++){
 5    for(int j = 1;j<=m;j++){
 6        cin>>a[i][j];
 7    }
 8}
 9//计算前缀和
10vector<vector<int>> presum(n+5,vector<int>(m+5,0));
11for(int i = 1;i<=n;i++){
12    for(int j = 1;j<=m;j++){
13        presum[i][j] = a[i][j]+presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1];//*** 
14    }
15}

3.结合例题

题目（一）：一个二维矩阵，计算其各个子矩阵的各个元素之和解法：

 1//先枚举所有子矩阵
 2for(int r1 = 1;r1<=n;r1++){
  for(int r2 = r1;r2<=n;r2++){//r1,r2分别表示上下边
      for(int c1 = 1;c1<=m;c1++){
          for(int c2 = c1;c2<=m;c2++){//c1，c2表示左右边
              //计算子矩阵元素和
              int sum = presum[r2][c2]-presum[r1-1][c2]-presum[r2][c1-1]+presum[r1-1][c1-1];//***
          }    
      }
  }
11}

1//若子矩阵是边长为len的正方形
2//以(i,j)坐标为子矩阵右下角
3for(int i = len;i<n;i++){
4    for(int j = len;j<n;j++){
5        int sum = presum[i][j]-presum[i-len][j]-presum[i][j-len]+presum[i-len][j-len];
6    }
7}

题目（二）：

滑动窗口
#

适用题型：

固定长度的，或长度有限制的区间和等

假设所需求求和的窗口区间长度为len

 1//初始化第一个窗口[0,len-1]的和
 2int window_sum = 0;
 3for(int i = 0;i<len;i++){
 4    window_sum += arr[i];
 5}
 6max_sum = window_sum;
 7//用i表示窗口左边界，逐个移动
 8//每移动一格，window_sum减去左边一个元素，加上右边一个元素哦
 9for(int i = 1;i+len-1<=n-1;i++){//理解限制条件
10    window_sum = window_sum-arr[i-1]+arr[i+len-1];
11    max_sum = (max_sum,window_sum); 
12}

上面为什么是i+len-1<=n-1呢？？？

因为len表示整个窗口的元素数量，

例如i=0，若直接i+len,则最后整个窗口会包含len+1个元素.所以应该是i+len-1<=n-1（这很重要！！！）

eg：

解法：（只是为了~~拓展介绍~~此算法，实际仍是超时哦，还是需要用特殊的前缀和算法）

 1#include <bits/stdc++.h>
 2using namespace std;
 3int main(){
  int n,a,b;
  cin>>n,a,b;
  vector<char> s(n);
  for(int i = 0;i<n;i++){
      cin>>s[i];
  }
  int cnt = 0;//计数，表示满足条件的（l，r）的个数
  for(int l = 0;l<n;l++){//以下展现了滑动窗口思想***
      int cnta = 0;
      int cntb = 0;//在l固定的时候就初始化计数a，b的个数
      for(int r = l;r<n;r++){
      //扩展右边界时更新计数
      //即，r每更新一次，就假设此时的（l，r）为一组，立刻测试本组的cnta，cntb是否满足条件。
      //依此，可以省去第三重for循环（原本是要确定l，r后再遍历的）
          if(s[r]=='a') cnta++;
          else if(s[r]=='b') cntb++;
          if(cnta>=a && cntb<b){//每次都要判断哦
              cnt++;
          }
      }
  }
  cout<<cnt;
  return 0

冒泡排序
#

 1#include <bits/stdc++.h>
 2using namespace std;
 3int a[n];
 4//这里省略对数组a的输入
 5for(int i = 0;i<n-1;i++){//n个数，则进行n-1次交换
 6    for(int j = 0;j<n-1-i;j++){//每一次的交换（因为已经完成了i次交换）
 7        if(a[j]>a[j+1]){//从小到大排序
 8            swap(a[j],a[j+1]);//交换
 9        }
10    }
11}

选择排序
#

核心思想：每次选择最大或最小的元素，将其排在正确位置。

 1using namespace std;
 2int arr[n];
 3for(int i = 0;i<n-1;i++){//n个元素交换n-1次，这次寻找第i小的元素
 4    int minindex = i;//假设当前i就是最小的索引
 5    for(int j = i+1;j<n;j++){//在之后的索引，寻找更小的元素
 6        if(arr[j]<arr[minindex]){
 7            minindex = j;//找到的话改变minindex
 8        }
 9    }
10    if(minindex!=i){//优化一下
11        swap(arr[i],arr[minindex]);//将第i小的元素放在相应位置
12    }
13}

插入排序
#

我认为相对选择排序和冒泡排序，插入排序较难理解嗯.

核心思想：将一个元素按顺序插入到已经排好序的序列中！！

Steps:

你左手一开始是空的（已排序区）。
你用右手从桌上（未排序区）拿起一张牌。
将这张牌与左手中从右向左的牌依次比较，找到它应该插入的位置。
将比它大的牌都向右挪一个位置，然后把它插入到空位。
重复步骤2-4，直到所有牌都拿到左手。

Code:

 1int a[n];
 2for(int i = 1;i<n;i++){//从1开始，默认第一个是排序好的
  int key = a[i];//存储当前需要排序的元素
  int j = i-1;//与其前面的元素一一比较
  while(j>=0 && a[j]>key){//只要j没有超出数组初始下标并且a[j]还是大于key
      a[j+1] = a[j];//向右移动
      j--;//比较下一个元素
  }
  //此时找到第一个小于等于key的元素下标   
  a[j+1] = key;//所以在那个元素的下一个地方插入key元素     
11}

Kadane最大子数组和
#

属于一种动态规划算法

 1int a[n];
 2for(int i = 0;i<n;i++){
 3    cin>>a[i];//初始化数组（包含负数）
 4}
 5int max_endhere = a[0];
 6int max_sum = a[0];
 7for(int i = 1;i<n;i++){
 8    max_endhere = max(a[i],max_endhere+a[i]);//精髓
 9    //即，如果当前值a[i]比前面局部最大值加上当前值还要大
10    //则直接从当前值重新开始计算
11    max_sum = max(max_sum,max_endhere);
12}
13cout<<max_sum;

对于每个位置i，需要决定是继续扩展前面的子数组；

还是从这里重新开始一个新的子数组！

max_endhere表示以元素a[i]结尾的子串中的最大字串和

拓展：环形最大子数组和(最小值法)

写成函数的形式（）嗯

环形数组时，若最大子数组和是跨越首位的情况，用总和减去最小子数组和就是答案

 1int max_sub_sum_circular(int *nums,int nums_size){
  if(nums==NULL || nums_size==0)return 0;
  int maxsum = nums[0];
  int max_endhere = nums[0];
  int minsum = nums[0];
  int min_endhere = nums[0];    
  int total = nums[0];
  for(int i = 1;i<nums_size;i++){
      total += nums[i];
      max_endhere = max(nums[i],max_endhere+nums[i]);
      min_endhere = min(nums[i],min_endhere+nums[i]);
      maxsum = max(maxsum,max_endhere);
      minsum = min(minsum,min_endhere);
  }
  if(maxsum<0){
      return maxsum;//必要的判断！防止数组全是负数时的bug
      //全是负数时，总和-最小和=0，但是数组中子数组和此时不可能为0对吧！
  }
  return max(maxsum,total-minsum);
20}

LIS
#

(LIS指longest increasing subsequencec,即最大上升子序列)

一.最大上升子序列(O(n^2))

 1int a[n];//初始化完一个随意的数字序列
 2int lis[n];//表示以第i个元素作为LIS最后一个元素时，的最长序列长度
 3int max_lis = 1;//全局最长LIS
 4for(int i = 0;i<n;i++){
 5    lis[i] = 1;//长度包含自己 至少为1
 6    for(int j = 0;j<i;j++){//每一个i，在i前逐一寻找
 7        if(a[j]<a[i]){//指如果满足升序
 8            lis[i] = max(lis[i],lis[j]+1);
 9        }
10    }
11    max_lis = max(max_lis,lis[i]);
12}
13cout<<max_lis<<endl;

二.合唱队型（先升序后降序）

策略是：单独求最大升序列和最大降序列

 1int tall[n];//初始化n个同学身高
 2//最大升序
 3int lis[n];
 4for(int i = 0;i<n;i++){
 5    lis[i] = 1;
 6    for(int j = 0;j<i;j++){
 7        if(tall[j]<tall[i]){
 8            lis[i] = max(lis[i],lis[j]+1);
 9        }
10    }
11}
12//最大降序
13int lds[n];//表示第i个作为LDS最前面的元素时，的最大降序列
14for(int i = n-1;i>=0;i--){
15    lds[i] = 1;
16    for(int j = n-1;j>i;j--){
17        if(tall[j]<tall[i]){
18            lds[i] = max(lds[i],lds[j]+1);
19        }
20    }
21}
22//寻找最合适的“峰值”，LIS和LDS可以以此首位相接哦
23int max_len = 2;
24for(int i = 0;i<n;i++){//遍历所有可能的峰值
25    max_len = max(max_len,lis[i]+lds[i]-1);
26}
27cout<<n-max_len<<endl;//输出最少要抽出的人数

三.Dliworth theory：

任意有限偏序集，最大反链的长度==最小正链划分数目

eg：一个随机序列a。最大升序子序列的长度，就等于下面问题的答案哦—–>

Q:将全部元素划分为若干个降序列，最少需要划分为多少个？？

LIS二分优化
#

如果只是求LIS的长度这个方法O(n log n)比较适合

核心是用tail[k]数组维护 LIS长度为k时的结尾最小值(最优结尾值)

 1const int N = 1000005;
 2int n;
 3int a[N];
 4int tail[N];
 5//tail是递增的 因为len越长 最优结尾值一般也需要更大
 6//也正因如此才能用二分查找
 7cin>>n;
 8for(int i = 0;i<n;i++){
 9    cin>>a[i];
10    tail[i] = INT_MAX;//别忘了给tail初始化
11}
12int len = 0;//目前LIS的值
13for(int i = 0;i<n;i++){
14    int x = a[i];
15    int l = 0;int r = len-1;
16    while(l<=r){//在当前LIS范围内二分查找
17        int mid = (l+r)/2;
18        if(tail[mid]<x){//目标是在tail中找到第一个>=x的
19        //如果序列是非严格上升 改为tail[mid]<=x
20            l = mid+1;
21        }else{
22            r = mid-1;
23        }
24    }
25    //二分结束后l就是第一个>=x的位置
26    tail[l] = x;//找到后更新 最后为每一个LIS长度找到相应的最优结尾
27    if(l==len)len++;
28}
29cout<<len<<endl;

二分可以用lower_bound,upper_bound等STL来写:

本质和上面是一样的

1int len = 0;
2for(int i = 0;i<n;i++){
3    int x = a[i];
4    int pos = lower_bound(tail,tail+len,x)-tail;//直接找到第一个>=x的位置 不需要手写二分
5    //注意lower_bound返回的是指针 最后要减去tail 指针相减
6    tail[pos] = x;
7    if(pos==len)len++;
8}
9cout<<len<<endl;

注意此时若不是严格上升的改成upper_bound就好了

最后还有一种更好理解的写法:

 1int a[n];
 2vector<int> tail;//这里为空就好
 3for(int i = 0;i<n;i++){
 4    cin>>a[i];
 5}
 6for(int i = 0;i<n;i++){
 7    int x = a[i];
 8    auto pos = lower_bound(tail.begin(),tail.end(),x);
 9    if(pos==tail.end()){//找不到就追加在已知LIS后面
10        tail.push_back(x);
11    }else{
12        *pos = x;//找到就更新当前长度更优结尾值
13    }
14}
15cout<<tail.size()<<endl;

编辑距离
#

A,B是两个字符串，有三种操作：

1在A中插入一个字符

2删除A中的一个字符

3替换A中的一个字符

将A字符串变成B字符串所需的最小操作次数，就是A，B的编辑距离

基础代码实现：（二维数组版，比较好理解）

 1string a;string b;
 2int lena = a.size();int lenb = b.size();//先确定两者长度
 3vector<vector<int>> dp(lena+1.vector<int>(lenb+1,0));
 4//dp[i][j]表示将a的前i个字符（子字符1）转换为b的前j个字符（子字符2）所需的最少操作次数
 5//最终得到的dp[lena][lenb]就是答案
 6for(int j = 0;j<=lenb;j++){
 7    dp[0][j] = j;//若a为空字符串，就是要插入j次
 8}
 9for(int i = 0;i<=lena;i++){
10    dp[i][0] = i;//若b是空字符串，就需要a删除i次
11}
12for(int i = 1;i<=lena;i++){
13    for(int j = 1;j<=lenb;j++){//遍历所有子情况
14        if(a[i-1]==b[j-1]){//若两个字符串尾部相同
15            dp[i][j] = dp[i-1][j-1];//当前编辑距离就等于前一次的了哦（即分别去掉两个串相同的那个字符）
16        }else{
17            dp[i][j] = min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);//在插入，替换，删除三种操作中取最小的
18        }
19    }
20}
21cout<<dp[lena][lenb]<<endl;

进阶代码（优化）：（一维数组版）

写成函数形式，暂时理解不了就当黑盒先使用吧，最多也只能处理几千字符的文本

 1int EditDistance(string a,string b){
  int lena = a.size();
  int lenb = b.size();
  if(a==b)return 0;
  if(lena>lenb){//确保a是较短的字符，节省空间
      swap(a,b);
      swap(lena,lenb);
  }
 9//dp[j]表示在当前行中，将a的前i个字符转换为b的前j个字符的编辑距离
  vector<int> dp(lenb+1);
11//初始化第0行，表示空字符串转换为b的前j个字符的编辑距离
  for(int j = 0;j<=lenb;j++){
      dp[j] = j;
  }
  for(int i = 1;i<=lena;i++){//表示a的前i个字符
      //prev表示"上一行左边"，即dp[i-1][j-1]
      int prev = dp[0];
      dp[0] = i;//表示i个字符的a转换为0个字符的b的编辑距离
      for(int j = 1;j<=lenb;j++){
          int temp = dp[j];//保存i个字符的a转换为上一个j的distance，类比dp[i-1][j]
          if(a[i-1]==b[j-1]){
              dp[j] =  prev;
          }else{
              dp[j] = min(min(dp[j]+1,dp[j-1]+1),prev+1);//dp[j-1]就类比二维时dp[i][j-1]
          }
          prev = temp;
      }
  }
  return dp[lenb];
30}

二分法查找
#

复杂度：nlog(n)?

标准二分：用于查找有序序列中的某个target，（是一次查询）

 1vector<int> arr;
 2int left = 0;int right = arr.size();
 3while(left<=right){
 4    int mid = (left+right)/2;
 5    if(arr[mid]==target)return mid;//找到就返回位置
 6    if(arr[mid]<target){
 7        left = mid+1;//目标在右边就向右移动左边界
 8    }else{
 9        right = mid-1;//反之向左移动右边界
10    }
11}
12return -1;//没找到就返回-1

一般来说，查找整数值时，可以用

1while(left<=right){
  //...
  if(check(mid)){
   l = mid+1;
   ans = mid;
  }else{
   r = mid-1;
}
9}

但是对于浮点数来说，由于精度问题，一般用

 1for(int i = 0;i<100;i++){//不断迭代，控制精度
  //...
  if(check(mid)){
   l = mid;
   ans = mid;
  }else{
   r = mid;//注意 浮点数的时候不要写
   //mid+1或者mid-1
   //直接写mid就好
  }
11}

与导弹例题结合，直接上例题：（对每个导弹多次查询）

由于题目的导弹数量n可能到达1e5，需要用二分法：

首先求最长不上升子序列：

 1int heights[n];//初始化所有导弹的高度；
 2vector<int> tail1;
 3//tail1[i]表示长度为i+1的不上升子序列的最后一个元素的最大值！
 4//因为若想让整个不上升子序列最长，末尾的元素要尽可能大，这样才可能在后面排更多元素
 5//由tail1的定义可知，tail1本身是严格降序的
 6for(int i = 0;i<n;i++){//对于heights中的每个元素
 7    int left = 0;
 8    int right = tail1.size();
 9    while(left<right){
10        int mid = (left+right)/2;//在tail1中寻找第一个小于heights[i]的元素
11        if(tail1[mid]<heights[i]){
12            //如果找到，那么再往tail1的左边再看看有没有更大的元素小于heights[i]，因为我们需要找的是第一个小于heights[i]的
13            right = mid;
14        }else{
15            //如果没找到，往tail1右边更小的地方找
16            left = mid+1;
17        }
18    }
19    if(left==tail1.size()){//左边界到tail1最小值都仍没找到比heights[i]更小的
20        tail1.push_back(heights[i]);//直接附加在后面
21    }else{//若找到tail1中第一个比heights[i]小的元素
22        tail[left] = heights[i];//为了得到最长不上升子序列，让tail1中每一个元素更大！
23    }
24}
25int max_lis = tail1.size();//得到最长不上升子序列

总结一下上面：

就是遍历heights的所有元素，根据条件，要么直接夹在tail1后面来延长序列，要么替换掉tail1中的元素使其能够在之后延申得更长.

tail1最后的size就是所求序列的长度

再依据Dliworth theory算最长上升子序列

1//把tail[mid]<heights[i]改成tail[mid]>=heights[i]即可

贪心
#

差分
#

差分可以先理解为前缀和的逆过程

前缀和：给定数组a,需我们创建数组presum 其中presum[i]=a[1]+a[2]+..+a[i],用于计算区间和
差分：将给定的数组a视为一个presum,创建一个数组b 使得a[i]=b[1]+b[2]+..+b[i],数组b就是a的差分

定义差分数组：

chafen[i] = a[i]-a[i-1]

应用：

将对一个数组区间修改的操作，转化为对其差分数组两个单点的修改操作

eg：

需要对数组a的区间[l.r]上的每一个元素都加上c

1//进行两个单点操作即可
2chafen[l] = chafen[l]+c;
3chafen[r+1] = chafen[r+1]-c;

注意，修改后要对差分数组求一次前缀和，进行还原，作为新的修改后的数组a

“实时"差分
#

传统差分VS实时差分:

场景	传统差分	“实时"差分
需要全部结果	✅适合	❌浪费(只关心当前结果)
只需当前结果	❌多余	✅完美匹配
需要中途判断	❌不方便	✅实时可用
空间使用	需要结果数组	只需差分数组

适用场景：

需从左到右顺序处理；

当前影响后续；

区间修改；

可能提前结束；

模板:

 1vector<int> diff(n+2);//差分数组空间稍微开大一点
 2int current = 0;//当前累计值(实时值)
 3for(int i = 1;i<=n;i++){//遍历每个位置
 4    current += diff[i];//current作为全局变量，此时就是当前位置的值！
 5    //使用current作为当前位置的值，做相应判断和处理...
 6    //...
 7    diff[l] += val;
 8    diff[r+1] -= val;//进行对应区间修改
 9    if(对当前立即生效){
10        current += val;//由于diff只对将来位置的值产生影响，有时需要给current也+val
11    }
12}

eg:

 1#include<bits/stdc++.h>
 2using namespace std;
 3int main(){
  int t;
  cin>>t;
  while(t--){
      int n,k;
      cin>>n>>k;
      string s;
      cin>>s;
      vector<int> condition(n+1);
      for(int i = 0;i<=n-1;i++){
          condition[i+1] = s[i]-'0';
      }
      vector<int> cf(n+1,0);//差分数组
      int flips = 0;//翻转次数
      bool possible = true;
      for(int i = 1;i<=n;i++){
          flips += cf[i];//此刻flips就是当前灯的对应累计翻转次数
          int current = condition[i]^(flips%2);//初次接触位运算哈
          if(current==1){
              if(i+k-1>n){//注意是i+k-1！！！
                  possible = false;
                  break;
              }
              cf[i]++;//进行区间修改
              if(i+k<=n){
                  cf[i+k]--;
              }
              flips++;//当前结果立即生效
          }
      }
      if(possible){
          cout<<1<<endl;
      }else{
          cout<<0<<endl;
      }
  }
  return 0;
40}

二维数组差分
#

标准模板：

 1#include<bits/stdc++.h>
 2using namespace std;
 3int main(){
  int n,m,q;//n*m的数组，q次操作
  cin>>n>>m>>q;
  //原数组
  vector<vector<long long>> a(n+5,vector<long long>(m+5));
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=m;j++){
          cin>>a[i][j];//初始化原数组
      }
  }
  //差分数组
  vector<vector<long long>> di(n+5,vector<long long>(m+5,0));
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=m;j++){
          di[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];//初始化差分数组
      }
  }
  while(q--){//进行q次操作
      int x1,y1,x2,y2;
      long long k;
      cin>>x1>>y1>>x2>>y2>>k;
      di[x1][y1]+=k;
      di[x2+1][y1]-=k;
      di[x1][y2+1]-=k;
      di[x2+1][y2+1]+=k;
      
  }
  vector<vector<long long>> re(n+5,vector<long long>(m+5,0));//求一次前缀和，还原差分数组
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=m;j++){
          re[i][j] = di[i][j]+re[i-1][j]+re[i][j-1]-re[i-1][j-1];
      }
  }
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=m;j++){
          cout<<re[i][j]<<" ";//输出操作后的新数组
      }
      cout<<endl;
  }
  return 0;
43}

eg：

 1#include<bits/stdc++.h>
 2using namespace std;
 3int main(){
  int n,m;
  cin>>n>>m;
  //int gezi[n+5][n+5] = {0};//这个只会把第一行第一列初始化为0！！！
  vector<vector<int>> gezi(n+5,vector<int>(n+5,0));
  for(int i = 0;i<m;i++){//直接将gezi数组视为其自身的差分数组，进行处理
      int x1,y1,x2,y2;
      cin>>x1>>y1>>x2>>y2;
      gezi[x1][y1]++;//***
      gezi[x1][y2+1]--;//***
      gezi[x2+1][y1]--;//***
      gezi[x2+1][y2+1]++;//二维差分的处理
  }
  vector<vector<int>> presum(n+5,vector<int>(n+5,0));//进行还原，计算差分数组的前缀和
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=n;j++){
          presum[i][j] = gezi[i][j]+presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1];
      }
  }
  for(int i = 1;i<=n;i++){
      for(int j = 1;j<=n;j++){
          cout<<presum[i][j]<<" ";
      }
      cout<<endl;
  }
  return 0;
29}

细节注意二维数组的初始化哦~

由于gezi数组初始化全为0，因此不必定义创建差分数组，其本身就可以视为其自身的差分数组

DFS深度优先搜索
#

(Depth-first search)

回溯算法普通模板：

 1return_type dfs(参数){
  //终止条件
  if(达到终止条件){
      处理结果;
      return 对应结果;
  }
  //遍历所有选择
  for(每个可能的选择){
      //做出选择
      标记状态改变；
      //递归进入下一层
      dfs(新的参数);
      //回溯到之前的状态，来进行其他选择
      恢复状态;
  }
  return 对应结果;
17}

eg：

 1#include<bits/stdc++.h>
 2using namespace std;
 3const int dx[3] = {0,1,-1};
 4const int dy[3] = {1,0,0};//每次可以向上，左，右走一步，此为对应坐标的增加值
 5int dfs(int x,int y,int step,int n,vector<vector<int>>& visited,int offset){//step表示已经走过的步数，若达到n，dfs就结束了
 6//visited前加"&"是因为要在函数内部改变实际的visited的值，要引用一下
  if(step==n){
      return 1;//走到头，记为1种方法
  }
  int total = 0;
  for(int i = 0;i<3;i++){//每次都有三种选择，进行遍历
      int nx = x+dx[i];
      int ny = y+dy[i];//更新进行当前选择后的新坐标
      if(nx<-n || nx>n || ny<0 || ny>n){
          continue;//如果超出边界，跳过并进行下一个选择
      }
      if(visited[nx+offset][ny]){
          continue;//如果新坐标是塌陷的，不能走，跳过并进行下一个选择
      }
      visited[nx+offset][ny] = true;//将能走到的新坐标标记为塌陷，下次不能走了
      total += dfs(nx,ny,step+1,n,visited,offset);//以这个选择为基点，递归累加所有走法
      visited[nx+offset][ny] = false;//回溯到基点前的状态，搜索其他选择是否可行
  }
  return total;
25}
26int main(){
  int n;
  cin>>n;
  int offset = n;//偏移法
  vector<vector<int>> visited(2*n+1,vector<int>(n+1,false));//由于有负数横坐标
//利用offset做一个偏移，即将0+offset视为原点，0视为最左边的点
  visited[0+offset][0] = true;//起始点直接标记为已经走过的状态
  int result = dfs(0,0,0,n,visited,offset);
  cout<<result<<endl;
  return 0;
36}

虽说方格无限大，但是能走的步数是有限的，那么最大方格其实也就确定为有限的了.

快速幂
#

用来计算类似3^100000000000这种东西

把3*3*3*3*3.....*3转变成9*9*9*9..9…..

总之就是把乘法任务两两打包，指数级减少操作次数

核心思想：

能把底数价值翻倍打包就一直先打包（来降低指数次数）

直到指数变为奇数，就将翻倍后的新底数乘上result

 1long long fastpower(long long base,long long exponent){
  //base,exponent分别表示底数和指数
  long long result = 1;
  while(exponent>0){
      if(exponent%2==1){//不能再直接打包了
          result *= base;//若指数是奇数就先单独乘上一个底数
      }
      base = base*base;//把底数两两打包,能打包就一直打包
      exponent = exponent/2;//因此指数也要减半
  }
  return result;
12}

埃式筛(素数)
#

筛到一个素数，那它的倍数就全部都是合数

筛到合数，直接continue跳过进行下一轮

 1const int n = 1000000;//测试数据范围
 2bool st[n+1];//标记每个数，false为素数，true为合数
 3vector<int> primes;//存储所有素数
 4fill(st,st+n+1,false);//初始全为素数
 5for(int i = 2;i<=n;i++){
 6    if(st[i]){
 7        continue;
 8    }
 9    primes.push_back(i);//不是合数就插入素数里了
10    if((long long)i*i>n)continue;//用ll防止溢出
11    for(long long j = (long long)i*i;j<=n;j += i){
12        st[j] = true;//该素数的倍数均为合数
13    }
14}

若追求极致高效，可以只处理奇数，因为偶数除了2都不是素数;

欧拉筛(线性筛)
#

基于埃式筛发现有些合数会被它的不同因子筛去多次
因此还有优化空间
让每个合数只被它最小的因数筛去
达到线性的复杂度

 1vector<int> primes;
 2bool st[N];//false为素数 true为合数
 3fill(st,st+n+1,false);//初始话全部标记素数
 4for(int i = 2;i<=n;i++){
 5    if(st[i])continue;
 6    primes.push_back(i);
 7    for(auto x:primes){//枚举已经筛出的素数
 8        if(i*x>n)break;//超出范围就终止
 9        st[i*x] = true;//素数的倍数标记为合数
10        if(i%x==0)break;//代码核心 保证线性性质
11    }
12}

关于i%x==0:

因为是从小到大枚举所有已经筛出的素数x;

当i%x=0的时候 x就是最小质因子此时break就好了;

区间筛
#

适合找区间[l,r]之间的所有素数
其中l，r很大但区间范围其实并不大

逆康托展开
#

这里用求第m小的排列为例子;

由不重复的数字1-n组成的所有排列中，按字典序从小到大求出第m小的排列:

以1,2,3,4组成的排列为例 (字典序)
1开头的排列–>(4-1)!=6种 |(小)
2开头的排列–>(4-1)!=6种 |
3开头的排列–>(4-1)!=6种 |
4开头的排列–>(4-1)!=6种 |(大)
then，比如求第9小的排列，先转换为0-based=>9-1=8;
8/6=1:该排列在第2组,也就是一个2开头的排列;
8%6=2,该排列在2开头的排列中的第2小
(以此类推递归)

 1#include<bits/stdc++.h>
 2using namespace std;
 3#define ll long long
 4vector<int> get_permutation(int n,int m){
  //预先做一个1-n排列的可用数字
  vector<int> nums;
  for(int i = 1;i<=n;i++){//注意索引是从0开始
      nums.push_back(i);
  }
  ll k = m-1;//因此要转换成0-based
  vector<int> ans;//到时候用来存储结果
  //接下来从第一位开始,确定排列的每一位
  for(int i = n;i>=1;i--){
      //每确定一个数之前,单独确定阶乘结果(如果直接计算所有阶乘会溢出的)
      ll fact = 1;
      bool overflow = false;
      for(int j = 1;j<=i-1;j++){//计算该位的阶乘
          if(fact>k/j){//判断是否"溢出"，等价于fact*j>k
              overflow = true;
              break;
          }
          fact = fact*j;
      }
      if(overflow){
          ans.push_back(nums[0]);//fact>k,则idx=k/fact=0
          nums.erase(nums.begin());//去掉当前数组及其索引
          //确定第一个数字的时候索引和值相等,后续的话,表示的是当下第几小的数
      }else{
          ans.push_back(nums[k/fact]);
          nums.erase(nums.begin()+k/fact);
          k %= fact; //更新k
      }
  }
  return ans;
35}
36int main(){
  ll n,m;
  while(cin>>n>>m){
      vector<int> result = get_permutation(n,m);
      int len = result.size();
      for(int i = 0;i<len;i++){
          cout<<result[i];
          if(i!=len-1){
              cout<<" ";
          }
      }
      cout<<'\n';
  }
  return 0;
50}

计算机一般都是从0开始的,理解不了就记住一般都要转换为0-based

排序+去重
#

方法一:利用set(边读入边处理)

1set<int> b;//先创建一个集合
2for(int i = 0;i<n;i++){
3  int x;cin>>x;
4  b.insert(x);
5}
6vector<int> a(b.begin(),b.end());//这样,a就是一个排序且去重的数组了

方法二:利用unique函数(适合已经有vector的情况)

1sort(a.begin(),a.end());//先排好序
2a.erase(unique(a.begin(),a.end()),a.end());//再利用unique,并结合erase完成去重
3//此时vector<int> a就完成去重和排序了

«语法»
#

位运算
#

优先级最低,建议加括号;
左移:x<<k = x*(2^k);
右移:x>>k = x/(2^k);(向下取整,取不大于结果的最大整数)

异或
#

先将数值转换为二进制
然后对每一位进行异或
相同为0
不同为1
异或符号^是可以直接使用的不需要自己实现

1^1=0
0^0=0
1^0=1

性质:

a^b=b^a;(交换律)
(a^b)^c=a^(b^c);(结合律)
a^b^b=a^(b^b)=a^0=a;(与0异或结果等于本身)

应用:

变量交换

1a=3;b=4;
2a=a^b;
3b=a^b;
4a=a^b;
5cout<<a<<b<<endl;

排除偶次重复

在一个整数数组中只有一个不重复的数字其余均出现偶数次找出不重复的那个数字

1int ans = 0;
2for(int i = 0;i<arr.size();i++){
3    ans ^= arr[i];//偶数次的都会被抵消完 ans保持为0
4    //直到遇到不重复的数字 ans保持那个不重复的数
5}
6return ans;

cin&cout
#

1.输入cin：

混合输入字符串和数字要注意ignore缓冲区：

1int a;
2string str;
3cin>>a;
4cin.ignore.();//清空缓冲区，否则无法正常使用getline
5getline(cin,str);
6//注意，cin中不能使用endl换行符；

2.输出cout:

1int a;
2cin>>a;
3cout<<a;
4int s[n];
5for(int i = 0;i<n;i++){//在需要高性能的环境中
6    //cout<<s[i]<<endl;
7    cout<<s[i]<<'\n';//是循环中更好的换行方式
8}

3.关闭输入输出同步流，提升程序效率

1ios::sync_with_stdio(false);
2cin.tie(0);
3cout.tie(0);

4.输出小数

1cout<<fixed<<setprecision(n)<<double_num<<endl;//保留n位小数

类型转换
#

首先方便起见，初学使用using namespace std;

1//字符串-->数值
2string str = "123";
3int num1 = stoi(str);
4double num2 = stod(str);
5float num3 = stof(str);
6long long num4 = stoll(str);
7//数值-->字符串
8string str1 = to_string(num1);

注意stoi()这种的参数需要是字符串,不能直接转换单个字符哦.

对于单个字符的情况：

1int num = str.back()-'0';//也能完成对最后一个元素的转换

数学函数
#

数学函数	库中对应函数语法
f(x)=lnx	log(x)
f(x)=lgx	log10(x)
f(x)=\|x\|(int,double)	abs(x),fabs(x)
f(x)=向下取整	floor(x)
f(x)=向上取整	ceil(x)
f(x)=$\sqrt(x)$	sqrt(x)
取大	max(a,b)
取小	min(a,b)

注意：三角函数在库中都以弧度制表示，即传入的参数应该是$\pi$ 之类的，而不是180°之类的。

++i&i++的区别
#

注：理解两者的区别对于提高代码效率非常重要！！！

1.++i：

先将i的值加一，再返回i.

2.i++:

先返回i本身的值，再将i加一.

”&“引用
#

引入一个重要的符号：&

在c++中，&除了有取地址的作用外，还可以表示引用！

1//&表示引用的基本含义
2//&引用的本质就是给变量取别名
3int a = 10;
4int &b = a;// b是a的引用（别名）
5b = 20;// 现在a也变成了20
6cout << a;// 输出20

主要用于函数的参数部分：

1//一.要通过函数修改外部变量
2void func(变量类型 &变量名){}//类似*，但更方便
3//二.不修改外部变量且是简单类型，不考虑性能
4void func(变量类型 变量名){}
5//三.不修改外部变量，但数据类型大，性能要求高
6void func(const 变量类型 &变量名){}//能避免拷贝

总之，

问自己：我需要修改这个参数吗？

要修改 → 用 &
不修改 → 继续问：这个参数大吗？
- 大（结构体、字符串、数组）→ 用 const &
- 小（int、double、char）→ 什么都不加

fgets(c语言)
#

struct结构体
#

是一种自定义数据类型

基本结构：将多个不同类型变量组合在一起，形成一个逻辑上的整体

1// 定义结构体
2struct Student {//定义Student是一种数据类型！！
3    string name;// 姓名
4    int age;// 年龄  
5    double score;// 分数
6};//别忘了有分号！！！

然后，可以在主函数中使用Student这个数据类型

例如Student Xiaoming;

那么如何访问一个结构体中的各个成员？

答案是用“.”来访问.

1Student Xiaoming;
2Xiaoming.name = Xiaoming;
3Xiaoming.age = 18;
4Xiaoming.score = 100.0;

当然也可以直接按结构体内的顺序初始化：

1Student a = {Xiaoming,18,100.0};

或指定成员初始化：

1Student a = {.name = Xiaoming,.age = 18,.score = 100.0};

bitset
#

可以看为更省内存的bool数组值为0或1
局限是编译时大小必须是常量可以预先开好足够空间

1bitset<100> b1;//大小为100的bitset 默认值全为0
2b1.set();//将其全部设为1
3b1.reset();//全部设为0
4b1.flip();//0变成1 1变成0
5//括号内加数字i的话 就是对第i位进行相应操作
6b1.count();//返回1的个数
7b1.test(i);//测试第i位是否为1 会检查越界 返回是bool值

fill,memset函数
#

memset一般只用于C风格数组或者结构体,或者通过new的动态数组;
fill可用于STL;
但两者都不能用于bitset;

1fill(起始迭代器，结束迭代器，填充值)；

即不管序列原来每个元素的值是多少，fill函数能够将范围内的所有元素值都一律变为填充值.

1fill(arr.begin(),arr.end(),10);//将arr全部变为10

memset主要用于快速清空或初始化很大的内存空间,比较高效.

1memmset(需要填充的内存块的指针,int ch,要设置的字节数);
2memset(arr,0,sizeof(arr));//数值全变为0
3memset(str,0,sizeof(str));//字符串全变为空!!!
4memset(str,'a',sizeof(str));//字符串全变为字符a
5memset(flags,true,sizeof(flags));//布尔值全变为true
6//注意，对于数值型，只能修改为0或-1！！！！

lower_bound/upper_bound函数
#

使用前记得先将范围序列排序哦

1sort(arr,arr+n);

这两个函数是基于二分的思想写的，可以直接调用

用于查找序列中的值，区间依旧左闭右开哦

lower_bound(arr,arr+n,value);返回第一个大于等于value元素的位置;

upper_bound(arr,arr+n,value);返回第一个大于value元素的位置;

若找不到，都会返回last这个位置（last是序列最后一个元素的再下一个位置）

1int a[n];//初始化省略了
2sort(a,a+n);//记住一定要先排序
3auto left = lower_bound(a,a+n,1);//auto可以自动判断表达式的类型哦，此处即为指针类型了
4auto right = upper_bound(a,a+n,1);
5int cnt = right-left;//统计1在a中出现次数

1auto left = lower_bound(a,a+n,1);
2int index = left-a;//获取第一个元素1的具体索引(指针相减)
3int value = *left;//获取指针所指的值

sort函数(c++)
#

基本形式：

1// 基本形式1：使用默认的升序排序
2sort(first, last);
3//更通用的形式：比较函数：
4sort(first,last,cmp);

first表示要排序的范围的开始位置，end则是结束位置，区间可理解为左闭右开.

基本语法&示例：

 1#include <bits/stdc++.h>
 2using namespace std;
 3int a[n];
 4for(int i = 0;i<n;i++){
 5    cin>>a[i];//初始化一个数组，对数组中的元素进行排序
 6}
 7sort(a,a+n);//升序排列
 8//如果是vector
 9sort(a.begin(),a.end());
10//由于要一直排序到索引为n-1的元素，且左闭右开，因此写结束位置为(n-1)+1--->n！
11return a<b;//升序
12}

降序排序比较器greater<>()

1#include<functional>
2sort(a,a+n,greater<数组值类型>());//这样就会降序排序

部分排序nth_element

1nth_element(a,a+k,a+n);//升序，挑出a中前k小的元素
2nth_element(a,a+k,a+n,greater<>());//降序，挑出a中前k大的元素

比较函数：(与c的qsort原理不同)

bool返回true，sort函数会将参数a排在参数b前面;

反之bool若返回false则会把参数a排在参数b后面;

1bool cmp(int a,int b){
2    return a<b;//升序
3}
4
5bool cmp1(int a,int b){
6    return a>b;//降序
7}

复杂度：n*log(n);

swap(交换函数)
#

基本语法&示例：

 1#include <bits.stdc++.h>//万能头文件
 2using namespace std;//要用swap的话一定要写std库！！
 3
 4int x = 5, y = 10;
 5swap(x, y);//交换基本类型
 6------------------------------
 7string s1 = "Hello", s2 = "World";
 8swap(s1, s2);//交换字符串
 9------------------------------
10int arr[] = {1,2,3,4,5};
11swap(arr[0], arr[4]);// 交换第一个和最后一个元素

getline(c++)
#

只适用于string类型!主要用于读取需要包括空格的文本.

1#include <bits/stdc++.h>
2using namespace std;
3string names;
4getline(cin,names);//基本格式，能读取空格，默认读到换行符为止！！

自定义分隔符（类似scanf的扫描集）

1#include <bits/stdc++.h>
2using namespace std;
3string data;
4getline(cin,data,',');//读到逗号为止

cin.ignore()清空混合输入缓冲区.eg:

1int num;
2string text;
3cin>>num;
4cin.ignora();//必须调用，清除缓冲区的换行符
5getline(cin,text);

set容器(c++)
#

介绍：

set是一个有序的关联容器，包含唯一键(元素不允许重复)的集合

特性：

元素唯一性；自动排序(升序)；不可修改元素(均为const)；查找效率高(logn)

用法：

 1set<变量类型> 变量名；
 2//eg:
 3set<int> myset;
 4myset.insert(1);
 5myset.insert(2);
 6myset.insert(3);
 7myset.insert(1);//因为1已经有了，这个1就无效了
 8//可用于统计集合的实际元素个数
 9int len = myset.size();
10myset.erase(x)//删除值为x的元素
11myset.find(x)//查找是否存在x元素，返回相应迭代器
12cout<<*myset.begin()<<'\n';//输出第一个元素(最小)
13cout<<*myset.rbegin()<<'\n';//输出最后一个元素(最大)

1//利用其自动升序排序的原理，我们可以用set同时完成去重和排序！！！
2set<type> setname(iterator first,iterator last);
3//这个构造函数会遍历[first,last)的所有元素并插入到set中

string(c++)
#

string是一个封装了字符数组的类，自动管理内存。专门存放字符序列. string类型的变量，下标索引也是从0开始。

首先注意string和普通数组a[n]的区别：

空的string最好使用+=或.push_back()来添加元素;

若想如a[n]一样通过for循环用a[i]赋值，则需要先resize()!!!!

特性1：变量之间可以直接相加+，自动管理内存哦！

1string s1 = "Hello";
2string s2 = "World";
3string s3 = s1 + " " + s2;//直接使用+运算符，也可以用于循环不断增加！

特性2：初始化较便利

1string s1 = "Hello";//C风格字符串字面量
2string s2 = 'A';//错误！不能直接存放单个字符
3string s3(1,'A');//正确！创建包含1个字符'A'的字符串
4string s3 = "A";//但可以用字符串字面量
5string s4 = "中文";//可以存放中文字符（在合适的编码下）
6string s5 = "Hello\x20World";//可以包含转义字符
7string s6 = ""; //空字符串

（但注意，（1）string类型也是不能由cin直接输入空格和换行符的！！！需要使用一个getline()哦（2）混合输入时，要在合适位置使用cin.ignore()清空缓冲区）

特性3：运算符重载，可直接比较字典序大小

1string s1 = "hello";
2string s2 = "world";
3if(s1>s2){
4    //.....
5}

特性4：丰富的成员函数(下面不是所有的哦)

 1string str = "Hello World";
 2
 3int len = str.size();//len = 11
 4cout<<str.find("World");//--->6
 5str.push_back('!');//str = "Hello World!",用于添加单个字符
 6str.pop_back();//删除最后一个字符
 7str.append(" world");//功能更强大，可追加多字符
 8str.append(100,'!');//添加100个感叹号哦
 9
10str.front();//访问第一个元素
11str.back();//访问最后一个元素
12str.find_first_of("aeiou");//查找第一个出现的元音字母的索引位置
13str.find_last_of("aeiou");//查找最后一个出现的元音字母的索引位置
14str.empty();//检查字符串是否为空，空返回true，非空false
15cout<<str.substr(提取的起始索引位置，提取字符数量)；//若提取数量不写，则默认提取到末尾哦
16string str1(str);//将str的内容拷贝到新创建的str1
17
18str.clear()//清空
19str.erase(n,m)//删除从索引为n开始，往后共m个字符
20str.erase(str.begin()+1);//删除单个字符
21str.erase(str.begin()+2,str.begin()+5)//删除一个范围
22
23reverse(str.begin(),str.end());//反转字符串
24str.replace(起始索引，需替换长度，"新内容")；//新字符串长度可不同
25
26str.reserve(n)//不改变字符串大小，只分配内存容量
27str.resize(n)//分配空间的同时也改变字符串大小

注意： .end()和.begin()是一对：

表示指向最后一个元素的下一个位置，和指向第一个元素

.front()和.back()是一对：

表示第一个和最后一个元素，可直接引用

map(c++)
#

对插入的键值对自动按键升序排序

 1#include<map>
 2map<键类型,值类型> 变量名;
 3//添加键值对
 4map<int,string> student;
 5student[1] = "jaychou";
 6student.insert({2,"neyo"});
 7//查找访问
 8//find():若查找发现有这个键，it就是指向该元素的迭代器
 9//如果没找到,it会指向.end()
10auto it = student.find(键);
11if(it!=student.end()){
12    cout<<it->second;//输出对应值
13}
14//删除元素
15//erase()会将这整个键值对都删掉
16student.erase(键);

利用迭代器遍历map中的键值对: 因为不一定知道起始的键也不知道键之间的间隔也不知道末尾的键

1for(auto it = m.begin(),it!=m.end(),it++){
2    cout<<it->first<<" "<<it->second;//不是成对的值,而是单个值的时候,需要用*it
3}
4//这里it是迭代器 要用->来表示具体的键和值
5for(const auto& item:m){//总之就是for(const auto& it:container)来遍历
6    cout<<item.first<<" "<<item.second;
7}
8//这里item是一个值,用.来表示具体的键和值

值要用. 迭代器要用->

补充：对于频率统计的问题,map和unordered_map都可以直接m[键]++,都会自动初始化该键的值为0;

unordered_map
#

一.语法：

unordered_map<键类型，值类型> 变量名;

eg:

 1//基本初始化
 2unordered_map<int,string> student_id;// 学号→姓名
 3unordered_map<string,double> product_price;//产品名→价格
 4unordered_map<ll,ll> freq;// 数值→出现次数
 5//插入键值对
 6scores["Alice"] = 100;//Alice为键，100为其对应的值
 7scores.insert({"Bob",60});//插入一个键值对
 8//访问元素
 9cout<<scores["Alice"];//输出的是100
10cout<<scores["David"];//自动创建{"David":0}并输出0

1//函数
2if(scores.count("Alice")){
3    //键存在
4}
5scores.erase("Alice");//删除键为Alice的元素

二.特性：

1.无序性。

相对map来说，map是有序的键值对，但访问速度没有哈希表快速。元素的存储顺序与插入顺序无关，遍历时顺序也不确定。

2.自动初始化。

eg：

1unordered_map<int,int> m;
2cout<<m[5];//输出0,同时自动创建{5:0}

即，即使哈希表的一些键值对还没有被初始化时，此时若直接输出或者访问某个键，会自动创建键值对，并初始化键的值为0。

三.用法：

1.统计频率等

pair(c++)
#

作用：可以把两个值打包成一个对象（一个变量名，类似成为一个组合），两个值可以是不同的数据类型

1pair<类型1，类型2> 变量名；

用法：

 1//方式1:先声明后赋值
 2pair<string,int> p1;
 3p1.first = "Bob";//这里first，second是pair专用的访问元素方法
 4p1.second = 80;
 5// 方式2:声明时直接初始化
 6pair<string,int> p2("Cathy", 88);
 7//方式3:表达一系列pair对，例如n个学生的姓名以及对应成绩
 8vector<pair<string,int>> student(n);
 9for(int i = 0;i<n;i++){
10    cin>>student[i].first>>student[i].second;//对其进行输入
11}
12//方式4:初始化pair序列
13vector<pair<int,int>> biggest(m,{0,0});//表示有m个{0，0}对序列

priority_queue
#

一种能够随时插入新数据，并且随时知道最大值或者最小值，并且随时删除当下最大值或最小值的容器(优先队列)

大顶堆(默认):priority_queue<int> pq;(获取,删除最大值)
小顶堆:priority_queue<int,vector<int>,greater<int>> pq;(获取,删除最小值)

常用方法:

1int value = pq.top();//获取最大/小值
2pq.pop();//删除最大/小值
3pq.push(x);//插入新的值x

stack栈
#

像一个只有一个开口的管道，只能从顶部存入或者取出东西, 先进后出

1#include <stack>
2stack<int> s;
3//新添加的元素始终在栈顶
4s.push(1);//[1]
5s.push(2);//[1,2]
6s.push(3);//[1,2,3]
7int x = s.top();//x=3
8//只能从栈顶逐个删除元素
9s.pop();//[1,2]

queue队列
#

像一个有上下开口的管道, 先存入的元素会先出来 先进先出

1queue<int> q;
2q.push(1);//[1]
3q.push(2);//[1,2]
4q.push(3);//[1,2,3]
5int x = q.front();//x=1
6int y = q.back();//y=3
7//弹出最先插入的元素
8q.pop();//[2,3]

«细节问题»
#

字符串需主动添加’\0’(NULL)的情况
#

(1)使用循环对逐个字符赋值，构造字符串时：

1char dest[10];
2for(int i=0; i<3; i++) {
3    dest[i] = source[i];
4}
5dest[3] = '\0';  // 必须手动添加****

(2)手动逐个字符赋值，构造字符串时：

1char str[10];
2str[0] = 'H';
3str[1] = 'i';
4str[2] = '\0';  // 必须手动添加****

(3)使用非字符串函数操作时：

1char str[10];
2memcpy(str, "Hello", 5);  // 只复制5个字符，不包括\0
3str[5] = '\0';  // 必须手动添加****

二维数组的初始化
#

目标：初始化a[n][n]的每个元素都为0

错误示例：

1int a[n][n] = {0};//这样只会让第一行第一列为0

正确示例：

1int a[n][n];
2for(int i = 0;i<n;i++){
3    for(int j = 0;j<n;j++){
4        a[i][j] = 0;    
5    }
6}

1//或者使用vector
2vector<vector<int>> a(n,vector<int>(n,0));

栈溢出
#

在oj或者算法竞赛上，数组在合适情况下就开在全局，或者使用vector;防止发生栈溢出(但实际开发中一般不推荐使用)

1const int MAXN = 200005; 
2long long len[MAXN];//开在全局 
3int main(){
4    //... 
5    int n; 
6    cin>>n; 
7    vector<long long> len1(n);//或者使用vector 
8}   

vector
#

1vector<int> graph[N];//写图论题的时候,这样写表示N个vector<int>
2vector<vector<int>> graph(N);//上面的写法更好

vector<>是一种数据结构，用[]就表示vector<>这种类型的数组; 用()就表示vector的一种构造元素个数的函数

C++/C算法n0t3#

«算法»#

qsort快排(c语言)#

GCD&LCM#

两两乘积之和化简#

一维前缀和#

二维前缀和#

滑动窗口#

冒泡排序#

选择排序#

插入排序#

Kadane最大子数组和#

LIS#

LIS二分优化#

编辑距离#

二分法查找#

贪心#

差分#

“实时"差分#

二维数组差分#

DFS深度优先搜索#

快速幂#

埃式筛(素数)#

欧拉筛(线性筛)#

区间筛#

逆康托展开#

排序+去重#

«语法»#

位运算#

异或#

cin&cout#

类型转换#

数学函数#

++i&i++的区别#

”&“引用#

fgets(c语言)#

struct结构体#

bitset#

fill,memset函数#

lower_bound/upper_bound函数#

sort函数(c++)#

swap(交换函数)#

getline(c++)#

set容器(c++)#

string(c++)#

map(c++)#

unordered_map#

pair(c++)#

priority_queue#

stack栈#

queue队列#

«细节问题»#

字符串需主动添加’\0’(NULL)的情况#

二维数组的初始化#

栈溢出#

vector#