题解：P11089 [ROI 2021 Day 1] 手机游戏

· · 题解

考虑如何确定一个保留方案合法。假设保留的下标序列为 p_1,p_2,...,p_k，则对于任意 i\in[1,k)，位于 [p_i,p_{i+1}-1] 内的所有字符都需要能够删除得只剩 p_i。于是直接考虑对于一个区间 [l,r]，考察它能否被删除到只剩 l。我们可以倒着扫描整个区间，使用一个栈维护目前还未被删除的字符。对于当前进入的一个字符 c，不断弹出栈顶的字符直到栈顶字符不能被 c 删除，然后把 c 压入栈。若最后栈中只有 l 处的一个字符，则该区间合法。

考虑第一个段，不难发现第一个位置的字符是一定会被保留的。枚举最靠后的一个被这个字删除的位置 x，则存在一种合法方案是先处理完 x+1\sim n 的所有字符，然后再利用 1 删除 2\sim x 的所有字符。不难发现这实际上是将一个 1\sim n 的问题递归到了一个 x\sim n 的问题。不妨设 f_i 表示 i\sim n 的答案，也即从 i 开始执行操作得到的最小字典序，提前预处理每个区间是否能被删除得只剩第一个，枚举即可做到 O(n^2)。

考虑去除无效的转移点。对于一个加入栈的元素序列，若取出其后缀进行操作，不难发现这部分元素的压入弹出操作与原先一致。因此可以直接对 [1,n] 执行上述流程，设 S_i 表示被 i 删除的所有位置集合，则所有 S_i 中的转移点都是合法的，同时根据上述结论，我们发现任取后缀的情况下，其他点也不会被 i 删除，故不存在 S_i 以外的有效转移点。不难发现 S 大小的总和是 O(n) 的，于是转移复杂度正确。

具体地，我们设 f_i 表示以 i 作为首个保留的位置时，最小字典序的下一个保留位置；g_i 表示以 i 作为首个保留位置的最小字典序，求 f_i 时，找到所有 j\in S_i，并比较 g_{f_j} 的字典序，选取最小的那一个（这是因为 j 实际上是会被删除的，i 的下一个字符实际上在位置 f_j）接在 i 的字符之后作为 g_i 即可。注意到 g 存在拼合关系，故我们可以使用字符串哈希，并倍增找到两个串首个不同位置的方式，以此在 O(\log n) 的复杂度内比较两个串的字典序，只需将 g 改为倍增数组存储哈希值即可。

最终总复杂度为 O(n\log n)，瓶颈在每个转移处 O(\log n) 比较字典序。代码实现中使用了双哈希。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define double long double
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+5,M=30,S=(1<<8)+5,inf=1e9+7;
const double eps=1e-8;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int m,n,a[N];
bool del[M][M];
struct hash{
    int base,mo,bs[N];
    void init(int x,int y){
        base=x,mo=y;
        bs[0]=1;
        rep(i,1,n)
            bs[i]=bs[i-1]*base%mo;
    }
    int merge(int llen,int lv,int rv){
        return (lv*bs[llen]+rv)%mo;
    }
}H[2];
int f[N][20];
struct node{
    int len,v[2];
    friend node operator+(node x,node y){
        node res;
        res.len=x.len+y.len;
        rep(i,0,1)
            res.v[i]=H[i].merge(x.len,x.v[i],y.v[i]);
        return res;
    }
    friend bool operator==(node x,node y){
        return x.len==y.len&&x.v[0]==y.v[0]&&x.v[1]==y.v[1];
    }
}g[N][20];
int getmin(int x,int y){
    int sx=x,sy=y;
    repp(i,19,0)
        if(g[x][i]==g[y][i])x=f[x][i],y=f[y][i];
    if(x>n)return sx;
    if(y>n)return sy;
    if(a[x]<a[y])return sx;
    else return sy;
}
signed main(){
    read(m),read(n);
    rep(i,1,m){
        string s;
        cin>>s;
        rep(j,1,m)
            del[i][j]=(s[j-1]=='1');
    }
    string s;
    cin>>s;
    rep(i,1,n)
        a[i]=s[i-1]-'a'+1;
    rep(i,0,19)
        g[n+1][i]=(node){0,{0,0}},f[n+1][i]=n+1;
    H[0].init(19491001,620071201),H[1].init(19260817,998244853);
    stack<int>stk;
    repp(i,n,1){
        f[i][0]=i+1;
        while(!stk.empty()&&del[a[i]][a[stk.top()]])
            f[i][0]=getmin(f[i][0],f[stk.top()][0]),stk.pop();
        stk.push(i);
        g[i][0]=(node){1,{a[i],a[i]}};
        rep(j,1,19){
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=n;i=f[i][0])
        printf("%c",a[i]-1+'a');
    return 0;
}