知识汇总-基础数据结构

单调栈,单调队列,双端队列,邻接表,Hash,kmp,trie

单调栈

  • 借助单调性处理问题的思想在于及时排除不可能的选项,保证策略集合的高度有效性和秩序性,从而为我们做出的决策提供更多的条件和可能方法。例题:直方图的最大矩形面积
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
        a[n+1]=tot=0;//避免扫描结束后栈中有剩余矩阵
    int ans=0;
    rep(i,1,n+1){
    if(h[tot]<a[i]) h[++tot]=a[i],w[tot]=1;
    else {
    int width=0;
    while(h[tot]>a[i]){
    width+=w[tot];
    ans=max(ans,width*h[tot]);
    tot--;
    }
    h[++tot]=a[i],w[tot]=width+1;
    }
    }
    return ans;
    }

单调队列

  • 同单调栈一样,也是在决策集合中及时排除一定不是最优解的选择,是优化动态规划的一个重要手段。例题:最大子序列和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,m;
int sum[N];
int l=1,r=1,que[N];
int main(){
int t;
scanf("%d%d",&n,&m);
rep(i,1,n) {
scanf("%d",&t);
sum[i]=sum[i-1]+t;
}
int ans=0;
for(int i=1;i<=n;i++){
while(l<=r && que[l] < i-m) l++;
ans=max(ans,sum[i]-sum[que[l]]);
while(l<=r && sum[que[r]]>=sum[i])r--;
que[++r]=i;
}
printf("%d\n",ans);
return 0;
}

双端队列

1
2
3
4
5
6
7
#include<deque>
front/back------队头/队尾元素,O(1)
push_back(x)----从队尾入队,O(1)
push_front(x)---从队头入队,O(1)
pop_front()-----从队头出队,O(1)
pop_back()------从队尾出队,O(1)
clear()---------清空队列,O(n)

邻接表

  • 这里的邻接表实现类似于链式前向星
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int head[N],Next[N];
    bool add(int i){
    int num=Hash(i);
    if(head[num]==0) {
    head[num]=i;
    return 0;
    }
    for(int j=head[num];j;j=Next[j]){
    if(check(i,j)) return 1;
    if(Next[j]==0) {
    Next[j]=i;
    break;
    }
    }
    return 0;
    }

Hash

Hash表:以哈希值为索引的邻接表

字符串Hash:

  • 用一个固定值P,把字符串看作P进制数,并分配一个大于0的数值,代表每种字符。取一固定值M,求出该P进制数对M的余数,作为该字符的哈希值。
  • 一般来说,取P=131或P=13331,此时Hash值冲突概率极低,令M=2e64,即直接用unsigned long long存储这个哈希值,在计算时不需要处理算术溢出问题,溢出相当于对M取模。这样可以避免抵消的mod运算。
  • 如果我们已知字符串S的Hash值为H(S),那么在S后添加一个字符c构成的新字符串S+c的Hash值就是H(S+c)=(H(S)*P+value[c]) mod M。其中乘P相当于P进制下的左移运算。
  • 如果已知S的Hash值为H(S),S+T的Hash值是H(S+T),那么字符串T的Hash值H(T)=(H(S+T)-H(S)*P^length(T)) mod M。相当于通过P进制下在S后补0的方式,把S左移到与S+T左端对其,然后二者相减就得到了H(T)
  • 例题:兔子与兔子

    二维矩阵哈希:

    • 例题:矩阵
    • 求出整个矩阵中所有axb大小的矩阵的哈希值,然后O(1)询问
    • 先对每一行单独求出前缀字符串哈希值.
    • 假如num为当前(j-1)b的矩阵的哈希值,那么在这个矩阵里面再加入第j行后的矩阵的哈希值为num=num*q^b+hash[j](l~r);
    • 如果加入这一行后矩阵高度大于了a,就需要使其变为减掉当前第一行后的哈希值,num-=hash[f[j-a]](l~r)*q[a*b],即减去将当前第一行的哈希值左移a*b位.
    • unordered_set(哈希set)可在平均O(1)的时间下完成查询。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      #pragma GCC optimize(3)
      #include<bits/stdc++.h>
      #include<unordered_set>
      #define INIT(a,b) memset(a,b,sizeof(a))
      #define ll long long
      #define ull unsigned long long
      #define rep(i,a,b) for(int i=a;i<=b;++i)
      #define repd(i,a,b) for(int i=a;i>=b;--i)
      #define S(d) scanf("%d",&d)
      #define SLL(d) scanf("%lld",&d)
      #define P(d) printf("%d\n",d)
      #define PLL(d) printf("%lld\n",d)
      using namespace std;
      const int inf=0x3f3f3f3f;
      const int N=1e3+7;
      const int M=2e6+7;
      const int mod=1e9+7;
      const int p=131;
      ull f[N][N],q[N*N+10];
      char s[N];
      ull get(ull h[],int l,int r){
      return h[r]-h[l-1]*q[r-l+1];
      }
      int main(){
      int m,n,a,b;
      q[0]=1;
      rep(i,1,N*N) q[i]=q[i-1]*p;
      scanf("%d%d%d%d",&m,&n,&a,&b);
      rep(i,1,m){
      scanf("%s",s+1);
      rep(j,1,n) f[i][j]=f[i][j-1]*p+s[j]-'0';
      }
      unordered_set<ull> S;
      rep(i,b,n){
      ull num=0;
      int l=i-b+1,r=i;
      rep(j,1,m){
      num=num*q[b]+get(f[j],l,r);
      if(j>a) num-=get(f[j-a],l,r)*q[a*b];
      if(j>=a) S.insert(num);
      }
      }
      int q;S(q);
      while(q--){
      ull num=0;
      rep(i,1,a){
      scanf("%s",s+1);
      rep(j,1,b) num=num*p+s[j]-'0';
      }
      if(S.count(num)) puts("1");
      else puts("0");
      }
      return 0;
      }

字符串

KMP

next[i]=max{j},j < i且A[i-j+1~i]=A[1~j]。特别的,没有这样的j存在时,next[i]=0;

循环节/循环元

  • 根据定义,S[i-next[i]+1~i]与S[1~next[i]]是相同的,并且不存在更大的next值满足这个条件。通过这一点我们可以得知,i-next[i]为前i个字符的循环节,当i%(i-next[i])==0时,S[1~i-next[i]]它就是一个前i个字符的最小循环元。如:abcab—abc是整个字符串的循环节,ababab—ab是整个字符串的循环元。
  • 进一步的,如果i-next[next[i]]能整除i,那么S[1~next[next[i]]]就是S[1~i]的次小循环元,依次类推,我们可以找到S[1~i]所有可能的循环元。
  • 例如:给定一个字符串L,已知这个字符串是由某个字符串S重复R次而得到的,求R的最大值。
    • 找L的最小循环元即可。

最小表示法

一个字符串S[1~n],如果不断把最后一个字符放到开头,最终会得到n个字符串,称这n个字符串循环同构,其中字典序最小的一个,称为字符串S的最小表示法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n=strlen(s+1);
for(int i=1;i<=n;i++) s[n+1]=s[i];
int i=1,j=2,k;
while(i<=n && j<=n){
for(k=0;k<n&&s[i+k]==s[j+k];k++);
if(k==n)break;
if(s[i+k]>s[j+k]){
i=i+k+1;
if(i==j) j++;
}else{
j=j+k+1;
if(i==j) j++;
}
}
ans=min(i,j);

Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//N至少为 字符种类数*字符串长度
int trie[N][27],ed[N],tot=1;
char s[N];
void Insert(char *str){
int len=strlen(str),p=1;
for(int i=0;i<len;i++){
int ch=str[i]-'a';
if(trie[p][ch]==0) trie[p][ch]=++tot;
p=trie[p][ch];
}
ed[p]++;
}
int query(char *str){
int len=strlen(str),p=1,ans=0;
for(int i=0;i<len;i++){
p=trie[p][str[i]-'a'];
if(p==0) return ans;
ans+=ed[p];
}
return ans;
}
Donate comment here