给定一个长度为$n$的排列 并将连续的三个作为一组 如$[1,2,3,4,5]$就有三组$[1,2,3],[2,3,4],[2,4,5]$现在我们可以把每组内的数顺序交换 也可以把组交换 现在给出$n-2$个经过交换后的组 让你求出任意合法的长度为$n$的排列
$5\leq n\leq 10^5$
5
4 3 2
2 3 5
4 1 2
1 4 2 3 5
这道题只是单纯的改变组内顺序 所以整体的性质并没有变 我们发现开头和结尾都只会存在在一个组中 而第二个和倒数第二个数会存在在两个组中 而其他数都会存在在三个组中 所以我们可以确定开头两个然后直接dfs递推出整个序列即可
当然这道题我现场没写出来 因为我想的比较复杂所以实现起来有点困难 参考了大佬的代码以后 有一些值得学习的地方 首先把每个点建一个vector然后把每个组作为一个node存进去然后判断开始 因为三个值会打乱顺序 所以我们知道两个值想要知道第三个值 我们可以用异或操作 node中存a b c 然后我们知道x y是其中两个元素
1
2
3
4
5
6
|
struct node{
int a,b,c;
int calc_ans(int x,int y){
return a^b^c^x^y;
}
}
|
利用异或的性质我们就可以找到另一个数
另外在dfs的时候我们我们存上一个节点和当前节点 然后在当前节点vector的node里找有没有包含上一个节点的 假如包含的话那就符合要求 我们就可以求出第三个点然后继续递推 注意这里需要判重 因为$[2,3,4],[3,4,5]$都有$[3,4]$直接找另一个可能会找到前面的然后死循环 判断是否包含节点我们也可以直接在结构体里写方法
1
2
3
4
|
bool ex(int t){
if(a==t||b==t||c==t) return true;
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
x=0; int ch=getchar(),f=0;
while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int maxn=200050;
int n;
struct node{
int a,b,c;
bool ex(int t)
{
if(a==t||b==t||c==t) return true;
return false;
}
int calc_ans(int x,int y)
{
return a^b^c^x^y;
}
}q[maxn];
vector<node> t[maxn];
vector<int> ans;
int vis[maxn];
void calc(int last,int u)
{
ans.push_back(u);
vis[u]=1;
for(int i=0;i<t[u].size();i++)
{
node temp=t[u][i];
if(temp.ex(last))
{
int pp=temp.calc_ans(last,u);
if(vis[pp]) continue;
calc(u,pp);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<n-1;i++)
{
int a,b,c;
read(a),read(b),read(c);
q[i]={a,b,c};
t[a].push_back(q[i]);
t[b].push_back(q[i]);
t[c].push_back(q[i]);
}
int s,e,p1,p2;
s=e=p1=p2=0;
for(int i=1;i<=n;i++)
{
if(t[i].size()==1)
{
if(s==0) s=i;
else e=i;
}
else if(t[i].size()==2)
{
if(p1==0) p1=i;
else p2=i;
}
}
ans.push_back(s);
vis[s]=1;
if(t[s][0].ex(p1))
{
calc(s,p1);
}
else calc(s,p2);
for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
puts("");
return 0;
}
|