Codeforces Contest 1152 E Neko and Flashback —— 欧拉路径

This way

题意：

给你一个长度为n的数组，名为a，现在分为两个长度为n-1的数组：
第一个数组b的第i位是$min(a_i,a_{i+1})$
第二个数组c的第i位是$max(a_i,a_{i+1})$
有一个p：1到n-1的某种排列，现在你知道$b^{\prime },c^{\prime }$，他们分别是b和c对应过来的，让你求出a

题解：

假设现在a数组中1,2，3的位置的数分别是a,b,c，那么有以下4种情况：
第一种：
a>b&&b>c
那么考虑b，c数组的两个位置1,2：
b：b,c
c：a,b
第二种：
a>b&&b<c：
b：b,b
c:a,c
第三种：
a<b&&b>c
b:a,c
c:b,b
第四种：
a<b&&b<c:
b：a,b
c:b,c
我们是不是可以发现无论什么情况，b都会连续出现两次啊，那么就相当于假设我现在知道了一个数，那么下一个位置中至少有一个数与它相等，就相当于我们要找到a->b->b->c->c->…->z这样的一个串？
这看起来就是一个欧拉路径，然后我们只需要将所有数存在一个map里面，并且将他的所有可以连起来的数存到multiset中，最后dfs找一下即可，判掉一些特殊情况。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
map<int,multiset<int> >mp;
int a[N],b[N];
vector<int>ans;
void dfs(int x)
{
while(!mp[x].empty())
{
int ne=*mp[x].begin();
mp[x].erase(mp[x].begin());
mp[ne].erase(mp[ne].find(x));
dfs(ne);
}
ans.push_back(x);
}
int main()
{
int n,fir=0,odd=0;
scanf("%d",&n);
for(int i=1;i<n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d",&b[i]),mp[a[i]].insert(b[i]),mp[b[i]].insert(a[i]);
if(a[i]>b[i])
odd=3;
}
for(map<int,multiset<int> >::iterator it=mp.begin();it!=mp.end();it++)
{
if(((int)it->second.size())%2)
odd++,fir=fir?fir:it->first;
if(odd>2)
break;
}
if(odd==1||odd>2)
return 0*printf("-1n");
dfs(fir?fir:mp.begin()->first);
if(ans.size()<n)
return 0*printf("-1n");
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i],i==n?'n':' ');
return 0;
}

最后

以上就是执着自行车为你收集整理的Codeforces Contest 1152 E Neko and Flashback —— 欧拉路径的全部内容，希望文章能够帮你解决Codeforces Contest 1152 E Neko and Flashback —— 欧拉路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。