CF76C Mutation题解

· · 题解

Link

发现应该枚举删除哪些字母，那么如何快速求出某一个删除方案的代价？

考虑拆贡献。对于一个位置 r ，能与其产生代价的左边相邻点 l 的个数为 \mathrm{O(k)} 级别。

因为不能存在两个 l 对应的字母相同。（因为这里如果需要靠前的 l 与 r 相邻就需要把靠后的 l 删掉，但两者只能同时存在或同时被删除）

对于这个性质，可以用高维前缀和来预处理代价。所有包含在 (l,r) 的字母都应被删除，还要保证 l 和 r 没被删除。容斥一下即可。

高维前缀和的原理是另一种处理前缀和的方式。二位前缀和一般采用容斥的方法来递推，但高维前缀和的维数太多，容斥就寄了。另一种方式是一位一位推，可以看代码。

值得注意的，两种方案不同当且仅当字符串不同，所以需要离散化。

code

const int N=2e5+5,M=24;

char s[N];

int v[M][M];

int frm[N][M];

int f[(1<<M)+5];

int w[M];

signed main(){
    int n=read(),m=read(),T=read();
    scanf("%s",s+1);
    for(int i=1;i<=m;i++)
        w[i]=read();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            v[i][j]=read();
    for(int i=1;i<=n;i++){
        int nw=s[i]-'A'+1;
        for(int j=1;j<=m;j++)
            frm[i][j]=frm[i-1][j];
        pir tmp[M];
        for(int j=1;j<=m;j++)
            tmp[j]={-frm[i][j],j};
        sort(tmp+1,tmp+1+m);
        int S=0;
        for(int j=1;j<=m&&tmp[j].fi!=0;j++){
            f[S]+=v[tmp[j].se][nw];//中间被删掉
            f[S|(1<<(nw-1))]-=v[tmp[j].se][nw];//不能包含右端点
            f[S|(1<<(tmp[j].se-1))]-=v[tmp[j].se][nw];//不能包含左端点
            f[S|(1<<(nw-1))|(1<<(tmp[j].se-1))]+=v[tmp[j].se][nw];//同时包含被减了两次，加回来
            S|=(1<<(tmp[j].se-1));
            if(tmp[j].se==nw)//不加也行
                break;
        }
        frm[i][nw]=i;
    }
    int all=(1<<m)-1;
    for(int i=1;i<=m;i++)//先枚举维再枚举数字，一维一维推，不重。
        for(int k=0;k<=all;k++)
            if(k&(1<<(i-1)))
                f[k]+=f[k^(1<<(i-1))];
    int ans=0;
    for(int k=0;k<all;k++){
        int sum=0;
        for(int l=k;l;l^=lowbit(l))
            sum+=w[__lg(lowbit(l))+1];//其实这个代价可以看作是删除方案包含了这一个字符，可以直接一起与前面的容斥处理
        ans+=f[k]+sum<=T;
    }print(ans),pc('\n');
    return 0;
}