CF1255C League of Leesins


题意简述:

给定一个长度为$n$的排列 并将连续的三个作为一组 如$[1,2,3,4,5]$就有三组$[1,2,3],[2,3,4],[2,4,5]$现在我们可以把每组内的数顺序交换 也可以把组交换 现在给出$n-2$个经过交换后的组 让你求出任意合法的长度为$n$的排列

数据范围:

$5\leq n\leq 10^5$

样例:

input
5
4 3 2
2 3 5
4 1 2
output
1 4 2 3 5 

题解:

这道题只是单纯的改变组内顺序 所以整体的性质并没有变 我们发现开头和结尾都只会存在在一个组中 而第二个和倒数第二个数会存在在两个组中 而其他数都会存在在三个组中 所以我们可以确定开头两个然后直接dfs递推出整个序列即可
当然这道题我现场没写出来 因为我想的比较复杂所以实现起来有点困难 参考了大佬的代码以后 有一些值得学习的地方 首先把每个点建一个vector然后把每个组作为一个node存进去然后判断开始 因为三个值会打乱顺序 所以我们知道两个值想要知道第三个值 我们可以用异或操作 node中存a b c 然后我们知道x y是其中两个元素

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]$直接找另一个可能会找到前面的然后死循环 判断是否包含节点我们也可以直接在结构体里写方法

bool ex(int t){
    if(a==t||b==t||c==t) return true;
    return false;
}

AC代码:

#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;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
AtCoder Beginner Contest 146 AtCoder Beginner Contest 146
AtCoder Beginner Contest 146全题解 A. Can’t Wait for Holiday签到题没啥好说的 int main() { string s; cin>>s; if(s=="SUN
2019-11-27
下一篇 
CF1262D1 Optimal Subsequences (Easy Version) CF1262D1 Optimal Subsequences (Easy Version)
题意简述:给定一个长度为$n$的序列 给定$m$次询问$k$和$pos$表示:长度为$k$的总值和最大的子序列里的第$pos$位的值是几(假如有多个子序列满足要求字典序最小的一个) 题解:这道题我比赛时候做了easy版 所以还是想糊一下e
2019-11-25
  目录