Parallelist

浅い夢だから 胸をはなれない

Quiz 0107 Summary

发布于 2021-01-08 | 分类于 字符串哈希 、 计数 dp 、 线段树 | 12分钟 | 2293字数 | 浏览量：

T1 word

Description

你有一个由小写字母组成的长度为 nn 的字符串。每一步你要找到它的子串中最短的重复块（一个重复块由一个字符串与自身连接而成）。如果有多于一个，你必须选择最左边的那个。你要将那个形如 XX(X - 某个字符串)的重复块替换成 X，即删除其中的一个 X。重复以上步骤直到字符串中不存在重复块。
输出最终的字符串。
n≤5×104n\leq 5\times 10^4

Solution

判断串中任意位置的重复块除了哈希貌似也没有别的方法。SAM 啊 exkmp 啊 ACAM 啊都束手无策。
但是找所有的重复块有一个经典的 trick ：枚举可能的重复串长度 len ，在原字符串中每隔 len 插标，比较相邻两个标的 lcp+lcs 与 len 的大小，即可判断此处是否存在长度为 len 的重复串。求相邻两个标的 lcp 和 lcs 都可以哈希+二分。
并且这个 trick 有个优势：每次找到的重复串一定是目前长度最小且起始位置最靠左的。
恰好适合这道题目呢🤞。
但是每次修改完要删除啊，这一删除哈希数组就得重构了。
大丈夫です ！每次找到 len 长度下的所有重复块并一起重构。这样至多重构 n\sqrt{n} 次。
复杂度 O(nlog⁡2nln⁡n+nn)\mathcal{O}(n\log_2{n}\ln{n}+n\sqrt{n}) 。

Code

int LCP(int p1,int p2){
    int l=1,r=Maxpre,ret=0;
    while(r>=l){
        int mid=l+r>>1;
        if(geth(p1-mid+1,p1)==geth(p2-mid+1,p2)) ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret;
}
int LCS(int p1,int p2){
    int l=1,r=p2-p1,ret=0;
    while(r>=l){
        int mid=l+r>>1;
        if(geth(p1,p1+mid-1)==geth(p2,p2+mid-1)) ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret;
}
int main(){

    scanf("%s",s+1);
    int n=strlen(s+1);
    p[0]=1;
    for(int i=1;i<=n;++i)
        p[i]=p[i-1]*B,w[i]=1ull*B*(w[i-1]+s[i]-'a'+1);
    for(int len=1;len<=n/2;++len){
        bool flag=0;
        int j=len,k=len<<1;Maxpre=len;
        while(k<=n){
            int lcp=LCP(j,k),lcs=LCS(j,k);
            if(lcp+lcs>len){
                for(int i=j-lcp+1;i<=j-lcp+len;++i)
                    del[i]=len;
                flag=true;Maxpre=lcp; // 注意 Maxpre 。要避免这次的 lcs 影响到下次的 lcp 。
            }
            else Maxpre=len;
            j+=len,k+=len;
        }
        if(!flag) continue;
        int cnt=0;
        for(int i=1;i<=n;++i)
            if(del[i]^len) 
                s[++cnt]=s[i],w[cnt]=1ull*B*(w[cnt-1]+s[i]-'a'+1);
        n=cnt;
    }
    for(int i=1;i<=n;++i)
        putchar(s[i]);
    return 0;
}

T2 dream

Description

给定一个长度为 nn 的仅含小写字母的字符串。有 mm 次操作，每次形如 l rl\ r ，要求将 s[l:r] 变为字典序最小的回文串（若无解则忽略）。输出最后的字符串。
n≤5×104n\leq 5\times 10^4

Solution

考虑将 s[l:r] 变为回文串的过程：枚举每个字符，假设有 dd 个，那么就会在左/右指针处分别插入 d2\frac{d}{2} 个，然后左/右指针均向中间靠拢 d2\frac{d}{2} ；如果 dd 是奇数，特判后直接放在中间即可。
优化空间在于加速“插入”的过程，而这个本质上就是区间覆盖，故可以考虑线段树维护。
复杂度 O(26nlog⁡2n)\mathcal{O}(26n\log_2{n}) 。

Code

struct node{
    int a[26];
    node(){memset(a,0,sizeof a);}
    node operator +(const node &b)const{
        node ret;
        for(int i=0;i<26;++i)
            ret.a[i]=b.a[i]+a[i];
        return ret;
    }
}t[N<<2];
namespace SEG{
#define mid (l+r>>1)
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
    int tag[N<<2];
    void pushup(int p){
        t[p]=t[p<<1]+t[p<<1|1];
    }
    void setval(int p,int l,int r,int v){
        t[p]=node();
        t[p].a[v]=(r-l+1);
        tag[p]=v;
    }
    void pushdn(int p,int l,int r,int v){
        setval(ls,v),setval(rs,v);tag[p]=-1;
    }
    void build(int p=1,int l=1,int r=n){
        tag[p]=-1;
        if(l==r) return ++t[p].a[s[l]-'a'],void();
        build(ls);build(rs);
        pushup(p);
    }
    void modify(int p,int l,int r,int nl,int nr,int v){
        if(l>=nl&&r<=nr) return setval(p,l,r,v),void();
        if(~tag[p]) pushdn(p,l,r,tag[p]);
        if(mid>=nl) modify(ls,nl,nr,v);
        if(mid< nr) modify(rs,nl,nr,v);
        pushup(p);
    }
    node query(int p,int l,int r,int nl,int nr){
        if(l>=nl&&r<=nr) return t[p];
        if(~tag[p]) pushdn(p,l,r,tag[p]);
        if(mid>=nr) return query(ls,nl,nr);
        else if(mid<nl) return query(rs,nl,nr);
        else return query(ls,nl,mid)+query(rs,mid+1,nr); 
    }
    void print(int p=1,int l=1,int r=n){
        if(l==r){
            for(int i=0;i<26;++i)
                if(t[p].a[i]) {putchar(char(i+'a'));break;}
            return;
        }
        if(~tag[p]) pushdn(p,l,r,tag[p]);
        print(ls),print(rs);
    }
}
using namespace SEG;
int main(){

    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    build();
    for(int i=1,l,r;i<=m;++i){
        scanf("%d%d",&l,&r);
        node sta=query(1,1,n,l,r);
        int L=l,R=r,times=(r-l+1)&1;
        for(int j=0;j<26;++j)
            times-=(sta.a[j]&1);
        if(times) continue;
        for(int j=0;j<26;++j){
            int d=sta.a[j]/2;
            if(d) modify(1,1,n,L,L+d-1,j);
            if(d) modify(1,1,n,R-d+1,R,j);
            L+=d,R-=d;
            if(sta.a[j]&1)
                modify(1,1,n,mid,mid,j);
        }
    }
    print();
    return 0;
}

T3 word

Description

有一个长度为 nn 的由小写字符组成的字符串。定义极大连续相同的子序列为 energy 。将给定的字符串重新排列，求有多少种不同的排列方式使得它和原字符串有相同数量的 energy 。对 106+310^6+3 取模。
保证 energy 的数量 mm 不多于 100 。
n≤105n\leq 10^5

Solution

关键切入点当然是 energy 的数量限制啦。
设 f[i][j] 表示考虑前 ii 种字符，已经组成了 jj 个 energy 的方案数；cnt[i] 表示第 ii 种字符的个数；sum[i] 表示 cnt 的前缀和。
插入第 i+1i+1 种字符时，新增的 energy 的来源有两处——直接插入产生的 energy 和分隔开原有的 energy 产生的 energy 。设 jj 表示原有的 energy ，kk 表示当前直接插入的 energy ，ll 表示因分隔而产生的 energy 。可得到转移方程式为

fi+1[j+k+l]=fi[j]×(cnti+1−1k−1)×(sumi−jl)×(j+1k−l)f_{i+1}[j+k+l]=f_{i}[j]\times \binom{\text{cnt}_{i+1}-1}{k-1}\times\binom{\text{sum}_i-j}{l}\times\binom{j+1}{k-l}

考虑转移方程式的意义。(cnti+1−1k−1)\binom{\text{cnt}_{i+1}-1}{k-1} 表示第 i+1i+1 种字符组成 kk 个 energy 的方案数，然后是个经典隔板法；考虑插入的具体情况：最开头以及 jj 个 energy 的末尾插入时都不会造成分隔，这部分的方案数为 (j+1k−l)\binom{j+1}{k-l} ，其余的位置插入时会造成因分隔而产生的 energy ，这部分的方案数为 (sumi−jl)\binom{\text{sum}_i-j}{l} 。
复杂度 O(n+26m3)\mathcal{O}(n+26m^3) 。

Code

const int N=1e5+5,M=1e2+5,Mod=1e6+3;
using namespace std;
char s[N];
int f[M],g[M],sum[26],cnt[26],c[N][M];
inline int Plus(int a,int b){return a+b>=Mod?a+b-Mod:a+b;}
int main(){

    scanf("%s",s+1);
    int n=strlen(s+1),tot=0;
    for(int i=1;i<=n;++i)
        tot+=(s[i]!=s[i-1]);
    for(int i=1;i<=n;++i)
        ++cnt[s[i]-'a'];
    sum[0]=cnt[0];
    for(int i=1;i<26;++i)
        sum[i]=sum[i-1]+cnt[i];
    c[0][0]=c[1][0]=1;
    for(int i=1;i<=n;++i,c[i][0]=1)
    for(int j=1;j<=i&&j<=tot;++j)
        c[i][j]=Plus(c[i-1][j-1],c[i-1][j]);
    f[bool(sum[0])]=1;
    for(int i=1;i<26;++i){
        if(!cnt[i]) continue;
        memset(g,0,sizeof g);
        for(int j=0;j<=tot&&j<=sum[i-1];++j)
        for(int k=1;j+k<=tot&&k<=cnt[i];++k)
        for(int l=0;j+k+l<=tot&&l<=k;++l){
            int now=1ll*f[j]*c[j+1][k-l]%Mod*c[cnt[i]-1][k-1]%Mod*c[sum[i-1]-j][l]%Mod;
            g[j+k+l]=Plus(g[j+k+l],now);
        }
        for(int j=0;j<=tot;++j) f[j]=g[j];
    }
    printf("%d\n",f[tot]);
    return 0;
}

Analysis

T1 失误在于完全不记得 trick 了。做题量要增加。

T2 失误在于未想清楚贸然动手。觉得维护序列用 splay 再好不过了，而且似乎只需要在每个节点找到当前位置在最终回文串中是什么字母，再打个标记就行了。不要浅尝辄止啊 QAQ 😭 这个标记真的可以下传吗？！用数据结构维护时不仅要知道打懒标记，更要想清楚懒标记能不能下传，怎么下传。

T3 考试的时候完全没想，考后也没有思路。从字符和极大连续相同字符串入手设置状态的思想很妙。枚举的时候要学会枚举段的概念，而不要局限于点。点到段只需要一个隔板法，而段可以省去超级多的讨论，用起来很实用。

# 字符串哈希 # 计数 dp # 线段树
Luogu4299 首都 上一篇
CF700E Cool Slogans 下一篇
0%