题意：对于长为n的序列c和长为n - 1的排列p，我们可以按照如下方法得到长为n - 1的序列a，b，a'，b'。
a = min(c, c)，b = max(c, c)
a' = a，b' = b。
现在给定a'和b'，求一个合法的c或者无解。
解：仔细分析性质，发现在a和b中，c除了开头和结尾会出现1次之外，每个数都会出现两次，且相邻。
我们可以把c的开头找出来，然后根据开头确定c，然后确定c...最后到c。
注意到这些数可能有重复的，于是我们要试图在中间插入一段。我一开始想的是链表后来发现很难写...
仔细分析，如果把a'和b'的每个位置当成边，数字当成点，就是求欧拉路。然后就没了......
关于欧拉路：就暴力DFS，把每条边都访问一次。回溯的时候把这条边入栈/把y入栈。
#include <bits/stdc++.h>
const int N = ;
struct Edge {
int nex, v, id, pre;
}edge[N << ]; int tp = ;
int X[N], xx, a[N], b[N], cnt[N], e[N], stk[N], top, deg[N];
bool vis[N];
inline void erase(int x, int i) {
int nex = edge[i].nex, pre = edge[i].pre;
if(e[x] == i && !nex) {
e[x] = ;
}
else if(e[x] == i) {
e[x] = nex;
edge[nex].pre = ;
return;
}
else if(!nex) {
edge[pre].nex = ;
}
else {
edge[nex].pre = pre;
edge[pre].nex = nex;
}
edge[i].nex = edge[i].pre = ;
return;
}
inline void add(int x, int y, int z) {
edge[++tp].v = y;
edge[tp].id = z;
edge[tp].nex = e[x];
edge[e[x]].pre = tp;
e[x] = tp;
return;
}
void DFS(int x) {
for(int i = e[x]; i; i = edge[i].nex) {
erase(x, i);
int y = edge[i].v;
if(vis[edge[i].id]) {
continue;
}
vis[edge[i].id] = ;
DFS(y);
stk[++top] = y;
}
return;
}
int main() {
int n;
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
X[++xx] = a[i];
}
for(int j = ; j < n; j++) {
scanf("%d", &b[j]);
X[++xx] = b[j];
if(b[j] < a[j]) {
puts("-1");
return ;
}
}
std::sort(X + , X + xx + );
xx = std::unique(X + , X + xx + ) - X - ;
for(int i = ; i < n; i++) {
a[i] = std::lower_bound(X + , X + xx + , a[i]) - X;
b[i] = std::lower_bound(X + , X + xx + , b[i]) - X;
add(a[i], b[i], i);
add(b[i], a[i], i);
deg[a[i]]++;
deg[b[i]]++;
}
int s = , pos = ;
for(int i = ; i <= xx; i++) {
if(deg[i] & ) {
s++;
pos = i;
}
}
if(s != && s != ) {
puts("-1");
return ;
}
DFS(pos);
stk[++top] = pos;
if(top != n) {
puts("-1");
return ;
}
for(int i = top; i >= ; i--) {
printf("%d ", X[stk[i]]);
}
return ;
}AC代码
注意复杂度，删边......
#include <bits/stdc++.h>
const int N = ;
struct Edge {
int nex, v, id;
}edge[N << ]; int tp = ;
int X[N], xx, a[N], b[N], cnt[N], e[N], stk[N], top, deg[N];
bool vis[N];
inline void add(int x, int y, int z) {
edge[++tp].v = y;
edge[tp].id = z;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void DFS(int x) {
for(int i = e[x]; i; i = e[x]) {
e[x] = edge[i].nex;
int y = edge[i].v;
if(vis[edge[i].id]) {
continue;
}
vis[edge[i].id] = ;
DFS(y);
stk[++top] = y;
}
return;
}
int main() {
int n;
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
X[++xx] = a[i];
}
for(int j = ; j < n; j++) {
scanf("%d", &b[j]);
X[++xx] = b[j];
if(b[j] < a[j]) {
puts("-1");
return ;
}
}
std::sort(X + , X + xx + );
xx = std::unique(X + , X + xx + ) - X - ;
for(int i = ; i < n; i++) {
a[i] = std::lower_bound(X + , X + xx + , a[i]) - X;
b[i] = std::lower_bound(X + , X + xx + , b[i]) - X;
add(a[i], b[i], i);
add(b[i], a[i], i);
deg[a[i]]++;
deg[b[i]]++;
}
int s = , pos = ;
for(int i = ; i <= xx; i++) {
if(deg[i] & ) {
s++;
pos = i;
}
}
if(s != && s != ) {
puts("-1");
return ;
}
DFS(pos);
stk[++top] = pos;
if(top != n) {
puts("-1");
return ;
}
for(int i = top; i >= ; i--) {
printf("%d ", X[stk[i]]);
}
return ;
}另一种删边方式