基本数据结构

======

  • STL:stack
  • 定义:stack a;
  • 查询堆顶:a.top();
  • 压入栈顶:a.pop();
  • 查询a中的元素个数:a.size();
  • 清空只能慢慢pop。

例题1

  • 给定一个栈,维护三个操作。 1:将一个数x压入栈中。 2:求栈中数的最大值。 3:弹出栈顶的数。 Q<=1000。 Q<=100000。

例题2

  • 给定一个栈,维护四个操作。 1:将一个数x压入栈中。 2:求栈中数的最大值。 3:弹出栈顶的数。 4:求栈中的栈底开始的最大前缀和。 Q<=1000。 Q<=100000。

例题3

  • 给定一个栈,维护五个操作。 1:将一个数x压入栈中。 2:求栈中数的最大值。 3:弹出栈顶的数。 4:求栈中的栈底开始的最大前缀和。 5:求栈中的栈顶开始的最大前缀和。  总和-栈底开始的最小前缀和 Q<=1000。 Q<=100000。

例题4

  • 给定一个数列,维护五个操作。 1:在光标的后面插入一个数字。 2:删除光标前的最后一个数字。 3:左移光标。 4:右移光标。 5:求光标前的最大前缀和。 Q<=1000。 Q<=100000。
栈的一些其它应用
  • 有n个数排成一列,每次可以选择最前面的数压入栈,或者弹出栈顶的元素。 求不同的出栈序列方案总数。 例如当n=3时共有5个不同的出栈序列方案:123,132,213,231,321.
  • 卡特兰数!

队列

  • queue:
  • 定义:queue a; 插入队尾:a.push(x); 删除队首:a.pop(); 查询队尾:a.back(); 查询队首:a.front(); 查询长度:a.size(); 清空只能慢慢pop。
  • deque:
  • 定义:deque a; 插入队尾:a.push_back(x); 插入队首:a.push_front(x); 删除队首:a.pop_front(); 删除队尾:a.pop_back(); 查询队尾:a.back(); 查询队首:a.front(); 查询长度:a.size(); 清空:a.clear();

例题1

  • 给定一个队列,维护三个操作。 1:将一个数x压入队列中。 2:求队列中数的最大值。 3:弹出队列的数。 Q<=1000。 Q<=100000。

    include <bits/stdc++.h>
    using namespace std;
    int main()
    {
    deque a,b; //a值,b时间戳
    for (i=1; i<=Q; i++)
    {
    cin>>A;
    if (A==1) //每执行A==1 都会使a.size+1
    {
    cntI++;
    cin>>x;
    while (a.back()<=x) a.pop_back(),b.pop_back(); //每执行这个while,都会使a.size减-1
    a.push_back(x);
    b.push_back(cntI);
    }
    if (A==2) cout<<a.front()<<endl;
    if (A==3)
    {
    cntD++;
    if (cntD == b.front()) a.pop_front(),b.pop_front();
    }
    }
    return 0;
    }
    O(Q)

单调队列

  • 在每次进入队伍时,判断当前元素与队尾元素的大小关系,若小于队尾元素,则队尾不可能成为最小值,直接删除即可。 每次查询的答案一定在队首位置。 由于每个元素至多进队列和出队列一次,时间复杂度为O(n)。

例题1

  • 给定一个队列,维护五个操作。 1:将一个数x压入队列中。 2:求队列中数的最大值。 3:弹出队列的数。 4:求队列中的最大前缀和。 5:求队列中的最大后缀和。 = 总和 - 最小前缀和 Q<=1000。 Q<=100000。

例题2——广告印刷

  • 有n个数ai。从中选出一段区间[L,R],使得(R-L+1)*min{a_L,…,a_R}最大。 n<=100000。
  • 思路:枚举最小值a[i],之后向右找最远扩展到哪里,右边最近的且比a[i]小的
  • 对于每个i,都在右边找一个最近且比a[i]小的。 这件事情可以用单调队列解决。
  • 考虑对于第i个数,求出当这个数成为最小值时,往左往右分别最远能到哪里。 用这些来更新答案就可以了。 使用单调队列来实现这一过程。

例题3

  • 给定n*m的01矩阵 找一个面积最大的全0子矩阵。 $n,m\\leq1000$ cpp if (a[i][j]==0) f[i][j] = f[i-1][j] + 1; else f[i][j] = 0;

RMQ问题

  • 给定n个数,有Q次询问,每次询问一段区间的最小值。
  • 倍增。 nlgn 1 线段树。 n lgn 分块。 nsqrtn sqrtn 整体二分。

  • 倍增:记录所有长度为2的幂次的区间的最小值。 n=5 [1,1] [2,2] [3,3] [4,4] [5,5] [1,2] [2,3] [3,4] [4,5] [1,4] [2,5] f[i][j] 表示 [i,i+2^j-1] 这段区间的最小值 [2,5] f[2][2] nlgn项

    f[i][0] = a[i]     f[i][j]表示[i,i+2^j-1]这段区间的最小值
    f[i][j] = min(f[i][j-1],f[i+(1<<j-1)][j-1])
    for (j=1; j<=20; j++)
      for (i=1; i<=n-(1<<j)+1; i++)
         f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1])
    
    [L,R]  先找到一个k,使得2^k <= R-L+1  且 2^(k+1) > R-L+1
    一开始预处理 p[x] 表示当R-L+1=x时k应该是多少
    k=int(log(R-L+1)/log(2))
    k=p[R-L+1];
    min(f[L][k],f[R-(1<<k)+1][k])       开车旅行

  • 我们考虑记录a[x]~a[x+2^k-1]的最小值,令其为f[x][k]。这可以在nlgn的时间内求出。 对于每次询问L~R,令k=log[R-L+1]。有ans=min(f[L][k],f[R-2^k+1][k])。(即进行O(1)询问)

LCA

  • 给定一棵树,求两个点的最近公共祖先。 通过倍增来求LCA。
  • 思路: 1.将两个点深度变成一样。
  1. 一起往上走找最近公共祖先。
  • 事先得先求出每个点的父亲是谁,以及它的深度是多少。
  • dfs
  • fa[i]表示i的父亲,dep[i]表示i的深度 第一步:将x和y走到同一层。 if (dep[x]<dep[y]) swap(x,y); // 保证dep[x]>=dep[y] 意味着 x要向上走dep[x]-dep[y]步。

  • f[i][j] 表示 i向上走2^j步后,能到哪儿 f[i][0]=fa[i]; f[i][j]=f[f[i][j-1]][j-1] for (j=1; j<=20; j++) for (i=1; i<=n; i++) f[i][j]=f[f[i][j-1]][j-1] 通过f数组来加速x向上走这个过程。

  • x向上走dep[x]-dep[y]步。 t=dep[x]-dep[y] 将t二进制分解 10 = 1010 x先向上跳8步,再向上跳2步 for (i=20; i>=0; i--) if (t&(1<<i)) x=f[x][i]; x和y就会到达同一层 让x和y一起往上跳,找它们的最近公共祖先

    for (i=20; i>=0; i--)
      if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i] 
    
    if (x==y) return x; else return f[x][0];

  • 预处理fa,dep

    f[i][0]=fa[i];  f[i][j]=f[f[i][j-1]][j-1]
    for (j=1; j<=20; j++) for (i=1; i<=n; i++) f[i][j]=f[f[i][j-1]][j-1]
    
    t=dep[x]-dep[y] 
    for (i=20; i>=0; i--) if (t&(1<<i)) x=f[x][i];  //这一步结束时有可能x==y
    if (x==y) return x;
    for (i=20; i>=0; i--)
      if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i] 
    return f[x][0];

  • dfs

    void dfs(int x,int y)
    {
      dep[x]=y;
      for (i=son of x) {fa[i]=x; dfs(i,y+1);}
    } 
    dfs(1,1);

链上最大值问题

  • 给定一棵带边权的树,每次询问两个点x,y,求这两个点的路径上最长的边是多少。
  • 思路: f[i][j]从i出发向上走2^j步能走到哪儿 g[i][j]从i出发向上走2^j步的过程中经过的最长边是什么

  • f[i][0]=fa[i],g[i][0]=dis(i,fa[i]); f[i][j]=f[f[i][j-1]][j-1] g[i][j]=max(g[i][j-1],g[f[i][j-1]][j-1]). 求答案的时候,用g数组来更新最大值

链上和问题

  • 给定一棵树,每次询问两个点x,y,求这条路径上边权和是多少。
  • 思路: dis[i] 从根节点出发到i经过的边的长度和 x~y的路径长度 dis[x]+dis[y] – 2*dis[LCA(x,y)]

链上异或问题

  • 给定一棵树,每次询问两个点x,y,求这条路径上边权异或和是多少。
  • 思路: dis[i]表示从1出发到i经过的边的边权亦或和 x~y = dis[x]^dis[y]

Hash

简单Hash

  • 有100个数字,每个数字的大小都是$\\leq10^5$。 问是否存在一对数字的值相等。 要求一个线性做法。

    for (i=1; i<=100; i++)
    {
      cin>>A; f[A]++;
      if (f[A]==2) return true;
    }
    return false;

  • $\\leq10^9$ 呢?

    for (i=1; i<=100; i++)
    {
      cin>>A; A%=12345678; f[A]++;
      if (f[A]==2) return true;
    }
    return false;

重要性质

  • 假如有n个自然数。 要使得这n个数之间在大概率下不冲突(不同的数在模p意义下相等)。 p>=n^2。

一维Hash

void Insert(int x)
{
  int t=x % 19999997;  //a[i]来表示i这个位置存的数是什么
  while (a[t] && a[t]!=x) t=(t+1) % 19999997;
  a[t]=x; b[t]++;  // b[i]表示a[i]这个数字出现了几次
}
int Query(int x)
{
  int t=x % 19999997;
  while (a[t] && a[t]!=x) t=(t+1) % 19999997;
  if (a[t]==x) return b[t]; else return 0;
}
cin>>A; Insert(A);
if (Query(A)==2) return true;

  • 模数开成10倍的元素个数,近似线性

字符串Hash

  • 给定一个字符串,求是否存在两个长度为k的子串完全相同。
  • abcabc k=4
  • 要求$O(|s|)$
  • |s|<=100W 对于每一个数字 先对10^18取模 得到 n-k+1个 10^18级别的数,询问是否存在一对数相同 两次hash 第一次hash -> 很大的26进制数 变成 10^18级别的数 二次 -> 10^18级别的数映射到1000W级别的数组

二维Hash

  • 给定一个n_n的矩阵,求是否存在两个完全相同的k_k的子矩阵。 要求时间复杂度与读入同阶。
Last modification:March 14th, 2020 at 08:42 pm