【2020 黑龙江省赛 E】Everybody Lost Somebody 题解

题目大意

  给定一个 $SA$ 数组和一个 $height$ 数组，其中 $height$ 数组的一些位置被抹掉了（用 $-1$ 表示），要求还原一个字典序最小的字符串，保证一定有解。

  $n \leq 5000$

$$\\$$ $$\\$$ $$\\$$

题解

  先观察一下，给定 $SA$ 数组和 $height$ 数组，我们能够判断一些位置的大小关系。具体来说：

1. 对于 $2 \le i \le n$，有 $s[SA_{i-1}] \le s[SA_i]$，更进一步，若 $rank_{SA_{i-1}+1}>rank_{SA_i+1}$，则必须有 $s[SA_{i-1}] < s[SA_i]$；
2. 对于 $2 \le i \le n$，对于 $0 \le j < height_i$，有 $s[SA_{i-1}+j] = s[SA_i+j]$，且若 $SA_{i-1}+height_i \le n$ 的话还会有 $s[SA_{i-1}+height_i] < s[SA_i+height_i]$。

  因此想法就是搞出一个大小关系拓扑图，按拓扑序确定每个字母。
  然后又发现，$SA_1,\cdots,SA_n$ 就是一个天然的拓扑序，直接以这个顺序一个一个确定就行了。显然，按这个顺序贪心放并满足所有限制的话，得到的字符串就是字典序最小的。

  首先，根据上面的两条规则，先把确切的小于关系和等于关系记下来，小于关系连一条边，等于关系用并查集合并。
  $s[SA_1]$ 直接赋值为 $a$ 没问题，然后 $s[SA_2],\cdots,s[SA_n]$ 依次确定，目标是每次处理完 $s[SA_i]$ 之后，只与 $s[SA_1],\cdots,s[SA_i]$ 有关的限制被全部满足。对于 $s[SA_i]$，它就等于 $\max(s[SA_{i-1}],s[小于关系里连向 i 的]+1)$，然后再去更新 $s[SA_1],\cdots,s[SA_{i-1}]$ 中跟它有等于关系的位置（这只会把字符往大的改，因此 $s[SA_1],\cdots,s[SA_{i-1}]$ 的限制仍然满足）。就做完了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=5005;

int n;
int SA[maxn],Rank[maxn],height[maxn];

int eql[maxn];
vector<int> larger[maxn];
int geteql(int x) {return eql[x]==x ?x :eql[x]=geteql(eql[x]) ;}

int T;
char ans[maxn];
int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&SA[i]), Rank[SA[i]]=i;
	fo(i,2,n) scanf("%d",&height[i]);
	Rank[0]=Rank[n+1]=0;
	
	fo(i,1,n) eql[i]=i;
	
	fo(i,2,n) if (height[i]>-1)
	{
		int x=SA[i-1], y=SA[i];
		fo(j,1,height[i]) eql[geteql(x+j-1)]=geteql(y+j-1);
		if (x+height[i]<=n) larger[y+height[i]].push_back(x+height[i]);
	} else
	{
		int x=SA[i-1]+1, y=SA[i]+1;
		if (Rank[x]>Rank[y]) larger[SA[i]].push_back(SA[i-1]);
	}
	
	ans[SA[1]]='a';
	fo(i,2,n)
	{
		ans[SA[i]]=ans[SA[i-1]];
		for(int x:larger[SA[i]])
			if (ans[x]+1>ans[SA[i]]) ans[SA[i]]=ans[x]+1;
		fo(j,1,n-1) if (geteql(SA[j])==geteql(SA[i])) ans[SA[j]]=ans[SA[i]];
	}
	
	fo(i,1,n) putchar(ans[i]);
	puts("");
}