Oak_limy 的 博客

题意

给你一个长度为 $n$ 的排列 $a$，但你不知道这个排列具体长什么样，再给出 $n-1$ 个子排列，每个排列的元素为 $[a_l,a_l+1,\dots,a_r]$，$r$ 代表从 $2$ ~ $n$ 的数字，这 $n-1$ 个排列中每个数必将出现一次，现在让你倒推回去，输出一种可能方案的 $a$。题目保证肯定有一种可行方案。

首先要了解几个重要的性质：

• 如果一个数出现在所有子排列中出现两次及以上，则这个数肯定不是原排列里的最后一个数
• 如果有一个数出现次数只有一次，则它可能是最后一个也可能是第一个数

知道这么多差不多就可以做这道题了（在这个解法中好像没怎么体现出

思路

我们考虑从前往后构造原排列
如果知道了第一位的数，那么就可以通过枚举求出第二位置的，以此类推。

const ll MAXN=210;
ll t,n;
ll a[MAXN][MAXN],pos[MAXN],ans[MAXN];
bool ok(){
	for(int now=2;now<=n;now++){//从第二位开始枚举
		for(int i=1;i<n;i++){//枚举子排序
			ll r=a[i][0],x=-1;//r为当前子排序的k
			for(int k=1;k<=a[i][0];k++){
				ll b=a[i][k];//当前子排序的数
				if(!pos[b])x=b;
				else if(pos[b]>=now-a[i][0]+1)r--;//要在当前子排序中
			}
			if(r==1&&x!=-1){//r-1个数都用掉了
				ans[now]=x;
				pos[x]=now;
				break;
			}
		}
		if(ans[now]==0)return false;
	}
	return true;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<n;i++){
			cin>>a[i][0];//输进来的k
			for(int j=1;j<=a[i][0];j++)cin>>a[i][j];
		}
		for(int i=1;i<=n;i++){//第一位1~n枚举
			for(int j=1;j<=n;j++){
				pos[j]=0;ans[j]=0;//初始化
			}
			ans[1]=i;//枚举的第一位，所以第一位设i
			pos[i]=1;//i的位置为1
			if(ok())break;//可行方案
		}
		for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
		cout<<endl;
	}
}

参考：

1

2