|
题目
参考
题意
给定长度为n的数组a和整数k，0<=k<=n。根据以下规则计算数组b
对于1<=i<=n，令x=a[i]
如果x<=k，令b[x]为最后一个元素a[j] (1<=j<i) ，使得a[j]>k，如果不存在该a[j]，则令b[x]=n+1；
如果x>k，令b[x]为最后一个元素a[j] (1<=j<i)，使得a[j]<=k，如果不存在该a[j]，则令b[x]=0。
现在已知b数组，求k和a数组。如果有多个a满足题意，输出任意一个。
思路
k的计算
- 对于i<=k，有b[i]>i;
- 对于i>k，有b[i]<i
根据上述，我们找到最大的下标i，使得b[i]>i，则k为该i
建图G
对于每个1<=i=n，建有向边b[i]到i。
对于该图，我们定义点集0到k为A，点k+1到n+1为点集B。
那么每个有向边要么从A到B，要么从B到A。
性质1：顶点0和顶点n+!有且仅有一个是孤立点。
证明：
首先，顶点0和顶点n+1不能全是孤立点，因为根据定义，b[a1]，要么为0，要么为n+1。
假设点0和点n+1全不是孤立点。那么存在下标x和y使得b[x]=0，b[y]=n+1，且有1<=y<=k<x<=n，找到点i，j使得a[i]=x,a[j]=y
因此，点0和点n+1有且仅有一个是孤立点。
性质2：图G不含环，即图G是一个DAG
证明：图不存在包含0和n+1的环，因为不存在b[i]->i，i的取值为1到n。因此，我们只需要考虑1到n的点。
对于图G的每条边(u,v),1<=u,v<=n，它的含义为，在a数组中，u出现在v的前面。因为a是一个排列，所有点都出现且仅出现一次。有环时，说明存在u，v,使得u在v的前面，同时v在u的前面。这显然不可能。
因此，根据性质1和性质2，图G是一个以0或n+1为根的树。
性质3：对于图G上的每个点u，最多有一个孩子节点v，其叶子节点非空。
证明：假设u存在两个叶子节点非空的孩子节点v1,v2。令w1,w2分别为v1和v2的孩子节点。
定义a’[x]为x的下标，使得a[i]=x。根据这个定义，我们有a’[u]<a’[v]，对于树上的每条边(u,v)。不失一般性，我们假设a’[v1]<a’[v2]
那么，我们有a’[v2]<a’[w1]，否则a’[v2]>a’[w1]，那么w1是b[v2]的候选点，u则不再是v2的父亲节点。
因此，a’[v2]<a’[w1]，这意味着v2是b[w1]的候选点，这使得v1不是w1的父亲节点。
综上，矛盾，得证。
BFS求a
根据上述性质，我们按bfs序，遍历树G，并让叶子节点优先遍历。
如果同一层级存在多个叶子节点，则按任意顺序遍历。
通过以上方式，就可以得到我们想要的a。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pcc pair<char, char>
#define inf 0x3f3f3f3f
const int maxn = 200010;
int n;
void solve() {
scanf("%d", &n);
vector<int> b(n + 1);
vector<vector<int> > v(n + 2);
int k = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
if (b[i] > i) {
k = i;
}
v[b[i]].push_back(i);
}
int rt = v[0].size() ? 0 : n + 1;
vector<int> q = {rt};
for (int i = 0; i < q.size(); ++i) {
int u = q[i];
sort(v[u].begin(), v[u].end(), [&](int a, int b) {
return v[a].size() < v[b].size();
});
for (auto x: v[u]) {
q.push_back(x);
}
}
if (q.size() != n + 1) {
printf("-1");
return;
}
printf("%d\n", k);
for (int i = 1; i < n; ++i) {
printf("%d ", q[i]);
}
printf("%d\n", q[n]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
}
|