基础课

其他

• scanf会读空格与回车，cin会跳过空格回车,使用scanf时可以将要读入的元素初始化为字符串，可以过滤空格或者回车，比如

  

• puts(s)等价于printf("%s\n", s);

按顺序刷

• 快速排序

  void quick_sort(int q[], int l, int r)
  {
      if (l >= r) return;
  
      int i = l - 1, j = r + 1, x = q[l + r >> 1];//这里之所以需要l - 1与 r + 1，在
      while (i < j)								//while循环中会先++i与--j
      {
          //do i ++ ; while (q[i] < x);
          //do j -- ; while (q[j] > x);
          while (q[ ++ i] < x);
  		while (q[ -- j] > x);
          if (i < j) swap(q[i], q[j]);
      }
      quick_sort(q, l, j), quick_sort(q, j + 1, r);
  }
  //注意这里分界点数x并不会是在i与j相等的位置，也就说是以x所在的位置为pivot，而不是x本身
  //比如1 6 2 3 4 5 7 8 9
  //第一次划分结果为 1 4 2 3 6 5 7 8 9
  //这时，i与j相交于第五个位置，对于在第五个位置左边的数皆小于等于原本第五个位置的数（也就是4），右边皆大于等于原本第五个位置的数
  //这里与常规的教科书（比如算法4）上的快速排序不一样，教科书上的快速排序是会每次排好一个数，而这里的快速排序，是每次划分好两个区间，直到区间只有一个数时，那么排序完成。
  //快速排序非常的dirty
  //把这个模板背下来，也可以自己写，碰到错误样例，对着修改即可
  
  void quick_sort(int q[], int l, int r)
  {
      if (l >= r) return;
  
      int i = l - 1, j = r + 1, x = q[l];
      while (i < j)								
      {
          //do i ++ ; while (q[i] < x);
          //do j -- ; while (q[j] > x);
          while (q[ ++ i] < x);
  		while (q[ -- j] > x);
          if (i < j) swap(q[i], q[j]);
      }
      quick_sort(q, l, j), quick_sort(q, j + 1, r);
  }
  //当取quick_sort(q, l, j)与quick_sort(q, j + 1, r)时，不能够取x = q[r],序列 1 2便是反例
  //同理，当取quick_sort(q, l, i - 1)与quick_sort(q, i, r)时，不能够取x = q[l],
  

• 归并排序

  void merge_sort(int q[], int l, int r)
  {
      if (l >= r) return;
  
      int mid = l + r >> 1;
      merge_sort(q, l, mid);
      merge_sort(q, mid + 1, r);
  
      int k = 0, i = l, j = mid + 1;
      while (i <= mid && j <= r)
          if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
          else tmp[k ++ ] = q[j ++ ];
  
      while (i <= mid) tmp[k ++ ] = q[i ++ ];
      while (j <= r) tmp[k ++ ] = q[j ++ ];
  
      for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
  }
  
  

• 整数二分

  bool check(int x) {/* ... */} // 检查x是否满足某种性质
  
  // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  int bsearch_1(int l, int r)
  {
      while (l < r)
      {
          int mid = l + r >> 1;
          if (check(mid)) r = mid;    // check()判断mid是否满足性质
          else l = mid + 1;
      }
      return l;
  }
  // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  int bsearch_2(int l, int r)
  {
      while (l < r)
      {
          int mid = l + r + 1 >> 1;
          if (check(mid)) l = mid;
          else r = mid - 1;
      }
      return l;
  }
  //这里mid = l + r + 1 >> 1,如果写成mid = l + r >> 1时，当l = r - 1时，mid = l，如果check(mid)返回true,这时候会死循环,[1, 2]就是例子
  

• 浮点二分

  bool check(double x) {/* ... */} // 检查x是否满足某种性质
  
  double bsearch_3(double l, double r)
  {
      const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
      while (r - l > eps)
      {
          double mid = (l + r) / 2;
          if (check(mid)) r = mid;
          else l = mid;
      }
      return l;
  }
  //对于精度要求n位小数，那么eps写成e-(n + 2)。譬如n = 6，那么eps = 1e-8
  

• 高精度

  A + B, A - B, A * b, A / b, 一般大整数如A的位数小于10^6,而小整数如b数值一般小于10^9

  A * B，或者 A / B基本不考

  加法

  // C = A + B, A >= 0, B >= 0
  vector<int> add(vector<int> &A, vector<int> &B)
  {
      if (A.size() < B.size()) return add(B, A);
  
      vector<int> C;
      int t = 0;
      for (int i = 0; i < A.size(); i ++ )
      {
          t += A[i];
          if (i < B.size()) t += B[i];
          C.push_back(t % 10);
          t /= 10;
      }
  
      if (t) C.push_back(t);
      return C;
  }
  
  

  减法

  // C = A - B, 满足A >= B, A >= 0, B >= 0
  vector<int> sub(vector<int> &A, vector<int> &B)
  {
      vector<int> C;
      for (int i = 0, t = 0; i < A.size(); i ++ )
      {
          t = A[i] - t;
          if (i < B.size()) t -= B[i];
          C.push_back((t + 10) % 10);
          if (t < 0) t = 1;
          else t = 0;
      }
  
      while (C.size() > 1 && C.back() == 0) C.pop_back();
      return C;
  }
  //C.push_back((t + 10) % 10);这里是两种情况的合体，当t>0时，t是负数，向高位借1，当t<0时，加10取余10不变。
  

  乘法

  // C = A * b, A >= 0, b >= 0
  vector<int> mul(vector<int> &A, int b)
  {
      vector<int> C;
  
      int t = 0;
      for (int i = 0; i < A.size() || t; i ++ )
      {
          if (i < A.size()) t += A[i] * b;
          C.push_back(t % 10);
          t /= 10;
      }
  
      while (C.size() > 1 && C.back() == 0) C.pop_back();
  
      return C;
  }
  
  

  除法

  // A / b = C ... r, A >= 0, b > 0
  vector<int> div(vector<int> &A, int b, int &r)
  {
      vector<int> C;
      r = 0;
      for (int i = A.size() - 1; i >= 0; i -- )
      {
          r = r * 10 + A[i];
          C.push_back(r / b);
          r %= b;
      }
      reverse(C.begin(), C.end());
      while (C.size() > 1 && C.back() == 0) C.pop_back();
      return C;
  }
  

  ios::sync_with_stdio(false)关闭cin与标准输入输出的同步，但是就不能使用scanf了

• 一维前缀和

  S[i] = a[1] + a[2] + ... a[i]
  a[l] + ... + a[r] = S[r] - S[l - 1]
  

• 二维前缀和

  S[i, j] = 第i行j列格子左上部分所有元素的和
  以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
  S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
  

• 一维差分

  给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
  

• 二维差分(二维差分需要想象成前缀和的逆运算，如果细究差分数组的元素是什么，会歇斯底里的)

  给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
  S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
  

• 双指针

  

  for (int i = 0, j = 0; i < n; i ++ )
  {
      while (j < i && check(i, j)) j ++ ;
  
      // 具体问题的逻辑
  }
  常见问题分类：
      (1) 对于一个序列，用两个指针维护一段区间
      (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
  

• 位运算

  求n的第k位数字: n >> k & 1
  返回n的最后一位1：lowbit(n) = n & -n
  lowbit依据负数的补码是其正数补码取反加一
  

• 离散化

  vector<int> alls; // 存储所有待离散化的值
  sort(alls.begin(), alls.end()); // 将所有值排序
  alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
  
  // 二分求出x对应的离散化的值
  int find(int x) // 找到第一个大于等于x的位置
  {
      int l = 0, r = alls.size() - 1;
      while (l < r)
      {
          int mid = l + r >> 1;
          if (alls[mid] >= x) r = mid;
          else l = mid + 1;
      }
      return r + 1; // 映射到1, 2, ...n,此处的映射从1开始，是因为要计算前缀和
  }
  
  

• 区间合并

  // 将所有存在交集的区间合并
  void merge(vector<PII> &segs)
  {
      vector<PII> res;
  
      sort(segs.begin(), segs.end());
  
      int st = -2e9, ed = -2e9;
      for (auto seg : segs)
          if (ed < seg.first)
          {
              if (st != -2e9) res.push_back({st, ed});
              st = seg.first, ed = seg.second;
          }
          else ed = max(ed, seg.second);
  
      if (st != -2e9) res.push_back({st, ed});
  
      segs = res;
  }
  
  

• 链表与邻接表(y总的静态链表需要使用idx记录插入顺序，表示第n次插入的节点，是与题目相关的，acwing上的链表题与“第n次插入的节点相关”，还有一种使用struct的静态链表表示方法)

  笔试一般不用动态链表，太慢了

  // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
  int head, e[N], ne[N], idx;
  
  // 初始化
  void init()
  {
      head = -1;
      idx = 0;
  }
  
  // 在链表头插入一个数a
  void insert(int a)
  {
      e[idx] = a, ne[idx] = head, head = idx ++ ;
  }
  
  // 将头结点删除，需要保证头结点存在
  void remove()
  {
      head = ne[head];
  }
  

• 双链表

  // e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
  int e[N], l[N], r[N], idx;
  
  // 初始化
  void init()
  {
      //0是左端点，1是右端点
      r[0] = 1, l[1] = 0;
      idx = 2;
  }
  
  // 在节点a的右边插入一个数x
  void insert(int a, int x)
  {
      e[idx] = x;
      l[idx] = a, r[idx] = r[a];
      l[r[a]] = idx, r[a] = idx ++ ;//注意一定要先改变l[r[a]],再改变r[a]
  }
  
  // 删除节点a
  void remove(int a)
  {
      l[r[a]] = l[a];
      r[l[a]] = r[a];
  }
  
  

• 栈

  // tt表示栈顶
  int stk[N], tt = 0;
  
  // 向栈顶插入一个数
  stk[ ++ tt] = x;
  
  // 从栈顶弹出一个数
  tt -- ;
  
  // 栈顶的值
  stk[tt];
  
  // 判断栈是否为空
  if (tt > 0)
  {
  
  }
  //这里浪费了一个位置，但是判空的时候比较优雅
  

• 队列

  • 普通队列

  // hh 表示队头，tt表示队尾
  int q[N], hh = 0, tt = -1;
  
  // 向队尾插入一个数
  q[ ++ tt] = x;
  
  // 从队头弹出一个数
  hh ++ ;
  
  // 队头的值
  q[hh];
  
  // 判断队列是否为空
  if (hh <= tt)
  {
  
  }
  

  • 循环队列（需要使用1个元素位，来判断队空）

    // hh 表示队头，tt表示队尾的后一个位置
    int q[N], hh = 0, tt = 0;
    
    // 向队尾插入一个数
    q[tt ++ ] = x;
    if (tt == N) tt = 0;
    
    // 从队头弹出一个数
    hh ++ ;
    if (hh == N) hh = 0;
    
    // 队头的值
    q[hh];
    
    // 判断队列是否为空
    if (hh != tt)
    {
    
    }
    

• 单调栈

  常见模型：找出每个数左边离它最近的比它大/小的数
  int tt = 0;
  for (int i = 1; i <= n; i ++ )
  {
      while (tt && check(stk[tt], i)) tt -- ;
      stk[ ++ tt] = i;
  }
  

• 单调队列

  常见模型：找出滑动窗口中的最大值/最小值
  int hh = 0, tt = -1;
  for (int i = 0; i < n; i ++ )
  {
      while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
      while (hh <= tt && check(q[tt], i)) tt -- ;
      q[ ++ tt] = i;
  }
  

• kmp算法

  kmp算法的本质是通过利用字符串的前后缀来达到减少模式串匹配主字符串的次数的目的，如下图，aba的最长的相同元素的前后缀为a，而abab的最长的相同元素的前后缀为ab，这里还需要注意一点aba并不是abab的前缀，所以就不会出现aaaa是aaaa的前缀以导致难以理解的想法