Codeforces Round #529 (Div. 3) D. Circular Dance

传送门

题意：

　　有 n 个孩子编号为 1~n ，绕着圣诞树 dance；

　　编号为 i 的孩子可以记住a_i1,a_i2两个小孩，a_i1,a_i2是 i 在顺时针方向的相邻的两个小孩，但a_i1,a_i2不一定是按顺时针方向排列的；

　　给出每个孩子相邻两个孩子的信息，让你还原这个序列。

题解：

　　可以以任一孩子作为第一个孩子，假设以编号 1 为第一个，编号1有两个相邻的孩子信息 a,b

　　如果 b 在 a 的顺时针方向，那么第二个孩子就是 a，反之为 b。

　　确定了前两个孩子后

　　i 从 1 开始遍历，第 i 个孩子的两个相邻的孩子a,b已经确定一个在 i+1 位置了，那么剩下的那个肯定在 i+2 位置，遍历到 n-2 却id确定最终序列。

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define mem(a,b) memset(a,b,sizeof(a))

 const int maxn=2e5+;

 int n;

 struct Node

 {

     int a,b;//i的顺时针方向相邻的两个孩子

     Node(int _a=,int _b=):a(_a),b(_b){}

 }nex[maxn];

 bool vis[maxn];

 int q[maxn];

 void Solve()

 {

     mem(vis,false);

     q[]=;

     int x=nex[].a,y=nex[].b;

     q[]=(nex[x].a == y || nex[x].b == y ? x:y);//确定第二个位置的孩子的编号

     vis[q[]]=true,vis[q[]]=true;

     for(int i=;i <= n-;++i)

     {

         x=nex[q[i]].a;

         y=nex[q[i]].b;

         q[i+]=(!vis[x] ? x:y);

         vis[q[i+]]=true;

     }

     for(int i=;i <= n;++i)

         printf("%d ",q[i]);

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i <= n;++i)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         nex[i]=Node(a,b);

     }

     Solve();

     return ;

 }

根据大神代码改编的简介代码%%%%%

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn=2e5+;

 int n;

 int a[maxn];

 int b[maxn];

 bool vis[maxn];

 int Find(int nex1,int nex2)

 {

     return !vis[nex1] && (a[nex1] == nex2 || b[nex1] == nex2) ? :;

 }

 void Solve()

 {

     int x=;

     for(int i=;i <= n;++i)

     {

         printf("%d ",x);

         vis[x]=true;

         int nex[]={a[x],b[x]};

         x=nex[Find(nex[],nex[])];

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i <= n;++i)

         scanf("%d%d",a+i,b+i);

     Solve();

     return ;

 }

改编自大神代码

巴特西

Codeforces Round #529 (Div. 3) D. Circular Dance

最新文章

热门文章