自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 23:04:09，当前版本为作者最后更新于2024-11-07 22:18:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑如何确定一个保留方案合法。假设保留的下标序列为 $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;
}