CF1152E Neko and Flashback 题解【欧拉路】【构造】
点击量:116
这种找可行解的问题套路还是比较多的。
Description
A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $[3,1,2]$ is a permutation of length $3$.
When Neko was five, he thought of an array $a$ of $n$ positive integers and a permutation $p$ of length $n-1$. Then, he performed the following:
- Constructed an array $b$ of length $n-1$, where $b_i=\min(a_i,a_{i+1})$.
- Constructed an array $c$ of length $n-1$, where $c_i=\max(a_i,a_{i+1})$.
- Constructed an array $b′$ of length $n-1$, where $b′_i=b_{p_i}$.
- Constructed an array $c′$ of length $n-1$, where $c′_i=c_{p_i}$.
For example, if the array $a$ was $[3,4,6,5,7]$ and permutation $p$ was $[2,4,1,3]$, then Neko would have constructed the following arrays:
- $b=[3,4,5,5]$
- $c=[4,6,6,7]$
- $b′=[4,5,3,5]$
- $c′=[6,7,4,6]$
Then, he wrote two arrays $b′$ and $c′$ on a piece of paper and forgot about it. 14 years later, when he was cleaning up his room, he discovered this old piece of paper with two arrays $b′$ and $c′$ written on it. However he can’t remember the array $a$ and permutation $p$ he used.
In case Neko made a mistake and there is no array $a$ and permutation $p$ resulting in such $b′$ and $c′$, print $-1$. Otherwise, help him recover any possible array $a$.
Input
The first line contains an integer $n(2\le n\le 10^5)$ — the number of elements in array $a$.
The second line contains $n-1$ integers $b′_1,b′_2,\dots,b′_{n−1}(1\le b′_i\le 10^9)$.
The third line contains $n-1$ integers $c′_1,c′_2,\dots,c′_{n−1}(1\le c′_i\le 10^9)$.
Output
If Neko made a mistake and there is no array aa and a permutation $p$ leading to the $b′$ and $c′$, print $-1$. Otherwise, print $n$ positive integers $a_i (1\le a_i\le 10^9)$, denoting the elements of the array $a$.
If there are multiple possible solutions, print any of them.
Examples
input
5 4 5 3 5 6 7 4 6
output
3 4 6 5 7
input
3 2 4 3 2
output
-1
input
8 2 3 1 1 2 4 3 3 4 4 2 5 5 4
output
3 4 5 2 1 4 3 2
Note
The first example is explained is the problem statement.
In the third example, for $a=[3,4,5,2,1,4,3,2]$, a possible permutation $p$ is $[7,1,5,4,3,2,6]$. In that case, Neko would have constructed the following arrays:
- $b=[3,4,2,1,1,3,2]$
- $c=[4,5,5,2,4,4,3]$
- $b′=[2,3,1,1,2,4,3]$
- $c′=[3,4,4,2,5,5,4]$
题解:
对于 $b_i=\min(a_i,a_{i+1})$ 和 $c_i=\max(a_i,a_{i+1})$ 这两个函数,取值一定在 $a_i$ 和 $a_{i+1}$ 这两个值中。
当 $a_i= a_{i+1}$ 时,$b_i=c_i=a_i$;当 $a_i\ne a_{i+1}$ 时,$b_i=a_i,c_i=a_{i+1}$ 或 $b_i=a_{i+1},c=a_i$。
我们对它们进行匹配,在 $b_i$ 和 $c_i$ 之间连有向边。如果 $b_i\to c_i$,说明 $b_i=a_i,c_i=a_{i+1}$,否则将 $b_i$ 和 $c_i$ 换过来。
根据取值,在 $b_i,c_i$ 与 $b_{i+1},c_{i+1}$ 中一定有一对相同元素,所以在序列的相邻位置会有联系。因此 $b_i,c_i,b_{i+1},c_{i+1}$ 实际上是 3 个点,它们由两条边相连。
每给出一对 $b_i,c_i$,我们就知道了一条这样的边。对于 $n$ 对这样的信息,我们就需要 $n$ 个点,$n-1$ 条边来把它们串成一个序列,并且数字的重复出现互不影响。
这就很容易联想到欧拉路了,在 $b_i$ 和 $c_i$ 之间连一条无向边。在求欧拉路的过程中需要用到类似当前弧优化的操作,可以把欧拉路做到 $O(n)$。
加上离散化的复杂度,这道题可以在 $O(n\log n)$ 的时间复杂度内完成。
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=getchar();
}
return x;
}
struct edge
{
int n,nxt;
bool used;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
used=0;
}
edge(){}
}e[200100];
int head[100100],ecnt=-1;
void add(int from,int to)
{
e[++ecnt]=edge(to,head[from]);
head[from]=ecnt;
e[++ecnt]=edge(from,head[to]);
head[to]=ecnt;
}
int b[100100],c[100100],r[200100],d[100100];
int stk[200100],tp=0,cnt=0;
void dfs(int x)
{
int i=head[x];
while(~i)
{
++cnt;
head[x]=e[i].nxt;
if(!e[i].used)
{
e[i].used=1;
e[i^1].used=1;
dfs(e[i].n);
}
i=head[x];
}
stk[++tp]=x;
}
int main()
{
memset(head,-1,sizeof(head));
int n=read();
for(int i=1;i<n;++i)
{
b[i]=read();
r[i]=b[i];
}
for(int i=1;i<n;++i)
{
c[i]=read();
if(c[i]<b[i])
{
puts("-1");
return 0;
}
r[n+i-1]=c[i];
}
sort(r+1,r+2*n-1);
int m=unique(r+1,r+2*n-1)-r-1;
for(int i=1;i<n;++i)
{
b[i]=lower_bound(r+1,r+m+1,b[i])-r;
c[i]=lower_bound(r+1,r+m+1,c[i])-r;
add(b[i],c[i]);
++d[b[i]];
++d[c[i]];
}
int s=1,flag=0;
for(int i=1;i<=m;++i)
if(d[i]&1)
{
++flag;
s=i;
}
if(flag>2)
{
puts("-1");
return 0;
}
dfs(s);
if(tp!=n)
puts("-1");
else
for(int i=1;i<=tp;++i)
printf("%d ",r[stk[i]]);
return 0;
}
说点什么