自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:14:53，当前版本为作者最后更新于2023-08-09 00:02:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P5841 题解

Problem Link

题目大意

给定 $n$ 个由小写字母组成的两两不同的非空字符串 $S_1,S_2,\cdots , S_n$，对于一个 $1$ 到 $n$ 的排列 $P=(p_1,p_2,\cdots,p_n)$，定义 $P$ 的价值 $W(P)= \sum_{i=2}^n (\text{lcp}(S_{p_i-1},S_{p_i}))^2$，设能够产生最大价值的排列为 $P^*_G$。

此外，还有 $q$ 个附加任务。对于第 $i$ 个任务，给定两个 $1$ 到 $n$ 之间的不同的整数 $X_i$ 和 $Y_i$。对于排列 $P$，若 $P$ 在满足 $W(P) = W(P^*_G)$ 的前提条件之下，同时满足第 $X_i$ 个字符串 $S_{X_i}$ 恰好排在第 $Y_i$ 个字符串 $S_{Y_i}$ 之前， 即 $\text{pos}(S_{X_i}) + 1 = \text{pos}(S_{Y_i})$，其中 $\text{pos}(S_i)$ 表示字符串 $S_i$ 在排列中的位置，则排列 $P$ 还将获得 $2^i$ 的奖励。所有任务的奖励之和称之为总任务奖励。

我们设能够使得总任务奖励最大的排列为 $P^*_B$。

试求：

1. $W(P^*_G)$，即可能产生的最大价值；
2. $P^*_B$，在保证最大价值前提下，可以使总任务奖励最大的排列。

数据范围：$Q\le 10^5,L=\sum |S_i|\le 2\times 10^5$。

思路分析

为了防止产生前后缀关系，我们给每个 $S_i$ 后面加上一个空字符，然后建 Trie，此时 $S_i$ 的结尾都是不同的叶子，可以证明 $P^*_G$ 一定是 Trie 的某个 dfs 序。

然后看附加任务，显然倒序满足最优，对于每个任务，可以看做钦定某两个点在 dfs 序中相邻。

观察发现每条限制对每个节点 $u$ 的儿子的搜索顺序只有三种影响：钦定某个 $v$ 为第一个或最后一个被搜的，或让某一对 $v,w$ 连续顺次搜索。

显然用链表维护每个点儿子的搜索次序即可，更新时简单分讨一下，由于每个节点儿子数是 $\mathcal O(|\Sigma|)$ 的，因此可以暴力合并链表。

此时瓶颈在处理路径上的每一个点，考虑优化：注意到 Trie 树上有很多出度为 $1$ 的点，把这些点都删掉显然不影响答案。

观察简化 Trie 树的最大深度，容易发现使最大深度从 $i$ 变成 $i+1$ 至少需要额外插入一个长度为 $i+1$ 的字符串，因此新 Trie 树的最大深度是 $\mathcal O(\sqrt L)$ 的。

时间复杂度 $\mathcal O(Q\sqrt L+L\times |\Sigma|^2)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
string str[MAXN];
int tot=1,edp[MAXN],tr[MAXN][27],deg[MAXN],bel[MAXN],pi[MAXN];
vector <int> G[MAXN];
int dep[MAXN],kfa[MAXN][20],fa[MAXN];
inline void init(int u,int Fa) {
	fa[u]=kfa[u][0]=Fa,dep[u]=dep[Fa]+1;
	for(int k=1;k<20;++k) kfa[u][k]=kfa[kfa[u][k-1]][k-1];
	for(int v:G[u]) init(v,u);
}
int st[MAXN],ed[MAXN]; //first and last son
int suf[MAXN],pre[MAXN],hd[MAXN],tl[MAXN],siz[MAXN]; //list<>
int lu[MAXN],lv[MAXN];
vector <int> ord;
inline void dfs(int u) {
	if(bel[u]) ord.push_back(bel[u]);
	vector <int> sons;
	for(int v:G[u]) if(hd[v]==v) sons.push_back(v);
	auto q=[&](int v) {
		if(hd[v]==st[u]) return -1;
		if(tl[v]==ed[u]) return 1;
		return 0;
	};
	sort(sons.begin(),sons.end(),[&](int x,int y) {
		return q(x)==q(y)?x<y:q(x)<q(y);
	});
	for(int v:sons) for(int i=hd[v];i;i=suf[i]) dfs(i);
}
signed main() {
	freopen("reorder.in","r",stdin);
	freopen("reorder.out","w",stdout);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	ll sum=0;
	for(int i=1;i<=n;++i) {
		cin>>str[i],str[i].push_back('z'+1);
		int p=1;
		for(int j=0;j<(int)str[i].length();++j) {
			int c=str[i][j]-'a';
			if(!tr[p][c]) {
				++deg[p],tr[p][c]=++tot;
				if(deg[p]>=2) sum+=j*j;
			}
			p=tr[p][c];
		}
		edp[i]=p,bel[p]=i;
	}
	cout<<sum<<"\n";
	for(int i=tot;i>1;--i) {
		if(deg[i]==1) {
			for(int c=0;c<=26;++c) if(tr[i][c]) pi[i]=pi[tr[i][c]];
		} else {
			pi[i]=i;
			for(int c=0;c<=26;++c) if(tr[i][c]) G[i].push_back(pi[tr[i][c]]);
		}
	}
	for(int c=0;c<=26;++c) if(tr[1][c]) G[1].push_back(pi[tr[1][c]]);
	init(1,0);
	vector <int> lim;
	for(int i=1;i<=m;++i) cin>>lu[i]>>lv[i];
	for(int i=1;i<=tot;++i) hd[i]=tl[i]=i,siz[i]=1,pre[i]=suf[i]=st[i]=ed[i]=0;
	for(int i=m;i>=1;--i) {
		int u=edp[lu[i]],v=edp[lv[i]],x=u,y=v;
		if(dep[x]>dep[y]) {
			for(int k=19;~k;--k) if(dep[kfa[x][k]]>=dep[y]) x=kfa[x][k];
		} else {
			for(int k=19;~k;--k) if(dep[kfa[y][k]]>=dep[x]) y=kfa[y][k];
		}
		for(int k=19;~k;--k) if(kfa[x][k]^kfa[y][k]) x=kfa[x][k],y=kfa[y][k];
		int z=fa[x];
		bool ok=true;
		for(int p=u;fa[p]!=z;p=fa[p]) {
			if(ed[fa[p]]&&ed[fa[p]]!=p) ok=false;
			if(suf[p]) ok=false;
			if(st[fa[p]]==hd[p]&&siz[p]<deg[fa[p]]) ok=false;
		}
		for(int p=v;fa[p]!=z;p=fa[p]) {
			if(st[fa[p]]&&st[fa[p]]!=p) ok=false;
			if(pre[p]) ok=false;
			if(ed[fa[p]]==tl[p]&&siz[p]<deg[fa[p]]) ok=false;
		}	
		if(suf[x]!=y) {
			if(x==ed[z]||y==st[z]) ok=false;
			if(hd[x]==hd[y]) ok=false;
			if(suf[x]||pre[y]) ok=false;;
			if(hd[x]==st[z]&&tl[y]==ed[z]&&siz[x]+siz[y]<deg[z]) ok=false;
		}
		if(ok) {
			lim.push_back(i);
			for(int p=u;fa[p]!=z;p=fa[p]) ed[fa[p]]=p;
			for(int p=v;fa[p]!=z;p=fa[p]) st[fa[p]]=p;
			if(suf[x]!=y) {
				int nowh=hd[x],nowt=tl[y],nows=siz[x]+siz[y];
				suf[x]=y,pre[y]=x;
				for(int i=nowh;i;i=suf[i]) hd[i]=nowh,tl[i]=nowt,siz[i]=nows;
			}
		}
	}
	reverse(lim.begin(),lim.end());
	cout<<lim.size()<<" ";
	for(int i:lim) cout<<i<<" "; cout<<"\n";
	dfs(1);
	for(int i:ord) cout<<i<<" "; cout<<"\n";
	return 0;
}