已经没有什么好害怕的了

发表于 |
字数统计: 815 | 阅读时长 ≈ 4
  • Code Level: ※
  • Thinking Level: ※※

Description

给定了一个长度为n的括号串，求经过每一个位置的合法子串的个数

Solution A

  • 差分
    因为一个合法串的贡献是使其所包含的串的ans得到含该串的方案数
    所以差分即可
    注意： 差分的增量和减量因为具有传递性（类似于递推），所以分开计算

Code A

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=1000005;
const ll mod=1e9+7;
int til,n,sta[nn],l[nn],r[nn],lg[nn],rr[nn],f[nn],tot=0;char s[nn];
int main(){
    scanf("%d",&til);
    while(til--){
        scanf("%s",s+1); n=strlen(s+1); tot=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='(') sta[++tot]=i;
            else if(tot){
                l[i+1]=sta[tot];
                r[sta[tot--]]=i+1;
            }
        }
        ll ans=0;
        for(int i=n+1;i>0;i--) rr[l[i]]+=++rr[i];
        for(int i=1;i<=n+1;i++) lg[r[i]]+=--lg[i];
        for(int i=1;i<=n;i++) f[i]=f[i-1]+rr[i]+lg[i],ans+=(i*f[i])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

Solution B

  • 树形结构

注意，合法的括号序列是满足树形结构的
即，包含与被包含组成了父子关系
对于同层合法子串，如果是紧挨着，即可组成不同的方案数
所以

Code B

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
const int nn=1000005;
int til,n,cnt=0,floo=0,lp[nn],out[nn],ano[nn],hav[nn],l[nn],r[nn],rp[nn];ll ans[nn];
char s[nn];
int main(){
    scanf("%d",&til);
    while(til--){
        scanf("%s",s+1); n=strlen(s+1);
        cnt=floo=0;
        memset(lp,0,sizeof(lp)); memset(rp,0,sizeof(rp)); memset(ano,0,sizeof(ano));
        memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(hav,0,sizeof(hav));
        for(int i=n;i>0;i--){
            if(s[i]==')'){ cnt++; floo++; rp[floo]=i; }
            else if(cnt>0){
                cnt--; hav[floo]++;
                r[rp[floo]]=hav[floo];
                if(s[i-1]=='(') hav[floo]=0;
                floo--;
            }
            else floo=cnt=0;
        }
        
        memset(hav,0,sizeof(hav)); floo=cnt=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='('){ out[i]=lp[floo]; floo++; cnt++; lp[floo]=i; }
            else if(cnt>0){
                cnt--; ano[lp[floo]]=i; hav[floo]++;
                l[lp[floo]]=hav[floo];
                if(s[i+1]==')') hav[floo]=0; floo--;
            }
            else floo=cnt=0;
        }
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++) if(s[i]=='('){
            ans[i]=ans[ano[i]]=ans[out[i]]+(1ll*l[i]*r[ano[i]]); 
            if(ans[i]==0) continue ;
            //printf("%d %d %d %d %d\n",ans[i],i,l[i],ano[i],r[ano[i]]);
            ans[n+1]+=(ans[i]*ano[i])%mod;
            ans[n+1]+=(ans[i]*i)%mod;
        }
        printf("%lld\n",ans[n+1]);
    }
    return 0;
}

总结

  • 差分

    差分确实考的时候没有想到
    突然感觉十分简单的样子
    但这种较为复杂的差分确实让我GG
    对于差分，重点在于贡献是连续的，如本题中，一个合法的括号序列给出的贡献是针对其内的括号序列（即其树形结构的子树）
    因此，连续贡献（且具有离线性），可以差分处理

  • 树形结构

    说实在做的时候没有想到它还有个名字
    这种做法思路清奇，先考虑序列特性，即合法序列是被包围的
    再来是考虑它是如何给出贡献的，即其和左右合法序列共同组成（被称作同层），和父亲序列给的贡献增量
    玄啊