题解 P5659 【树上的数【民间数据】】

Mihari · 2019-11-21 20:39:40 · 题解

Day1 T3 树上的数

题目

点这里

考场经历+思考

这道题的输入感觉很恶心。 大概思路就是用 O(n!\times n) 的复杂度，全排列删边顺序，再用 n 来计算。 处理了输入很久，但是还是没有调出来。 然后，花费了差不多 1h 但是还是没有什么结果。 但是却把 T2 的 100pts 全部丢掉了... 代码就不贴了。

正解

同理，edge_2、edge_3、edge_4、edge_5 一定是依次删除的，那么可得 mark[p1]=mark[p2]=mark[p3]=1

而点 i ，要保证的是 edge_6 在 edge_5 之前删除，为什么？

因为当 x 到 i 点之后，如果 edge_6 还存在，那么 x 就会跑到 p_4 那里去。

由此推出，mark[i]=2

这是 x 往右走的情况，x 往左的情况可自行推导 要看代码我也不拦你，推荐自己推一下，很简单

而最后，我们判定一个方法是否可行，只需要判断它和前面的边的标记是否冲突即可。

#include<cstdio>
#include<utility>
using namespace std;

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
// #define FILEOI

typedef pair<int,int> pii;

#define cg (c=getchar())
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
inline int qread(){
    int x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=-1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);putchar(x%10^48);
}

const int MAXN=2000;

struct edge{
    int to,nxt;
    edge(){}
    edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
    ++in[u],++in[v];//更改点的入度
    e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
    e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;

    maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
    t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}

int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案

inline void init(){
    qread(N);

    //清空图
    ecnt=0,tcnt=0,maxin=0;
    rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;

    //输入
    rep(i,1,N)a[qread()]=i;
    rep(i,1,N-1)add_edge(qread(),qread());
    /*
    rep(i,1,N)writc(a[i],' ');
    putchar('\n');
    */
}

int pre[MAXN+5];
inline void buildSet(){rep(i,1,N)pre[i]=i;}
int findSet(const int u){return u==pre[u]?u:pre[u]=findSet(pre[u]);}
inline void unionSet(const int u,const int v){return (void)(pre[findSet(u)]=findSet(v));}

bool vis[MAXN+5];
int tmp[MAXN+5],pt[MAXN+5];

inline void work(){//处理菊花图
    buildSet();
    rep(i,1,N)tmp[a[i]]=i,vis[i]=0;
    rep(i,1,N-1){
        rep(j,1,N)if(!vis[j]&&findSet(tmp[i])!=findSet(j)){
            vis[j]=true,pt[tmp[i]]=j;
            unionSet(tmp[i],j);
            break;
        }
    }
    rep(i,1,N-1)writc(pt[tmp[i]],' ');
    rep(i,1,N)if(!vis[i]){
        writc(i,'\n');
        break;
    }
}

int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
    rep(i,1,N)vis[i]=0;
    dfs(1);
    rep(i,1,N-1)writc(ans[i],' ');
    writc(ans[N],'\n');
}
inline void chk(){
    rep(i,1,N)mir[a[i]]=i;
    rep(i,1,N){
        if(mir[i]<ans[i]){
            rep(j,1,N)ans[j]=mir[j];
            break;
        }
        if(mir[i]>ans[i])break;
    }
    return;
}
void dfs(const int p){
    if(p==N)return chk();
    rep(i,1,N-1)if(!vis[i]){
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
        dfs(p+1);
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
    }
}

int lt[MAXN+5],lcnt;
short int mark[MAXN+5];//标记 : 0-无标记 ; 1-左先右后 ; 2-左后右先
inline void getlist(const int u,const int pre){
    lt[pt[u]=++lcnt]=u;
    for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
        getlist(v,u);
}
inline bool chkl(const int p1,const int p2){
    if(mark[pt[p1]]==1)return false;

    rep(i,pt[p1]+1,pt[p2]-1)if(mark[i]==2)return false;

    if(mark[pt[p2]]==1)return false;

    return true;
}
inline void getMarkl(const int p1,const int p2){//当 pt[p1]<=pt[p2] 时
    if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=2;

    rep(i,pt[p1]+1,pt[p2]-1)mark[i]=1;

    if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=2;
}
inline bool chkr(const int p1,const int p2){//当 pt[p1]>pt[p2] 时
    if(mark[pt[p1]]==2)return false;

    fep(i,pt[p1]-1,pt[p2]+1)if(mark[i]==1)return false;

    if(mark[pt[p2]]==2)return false;

    return true;
}
inline void getMarkr(const int p1,const int p2){
    if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=1;

    fep(i,pt[p1]-1,pt[p2]+1)mark[i]=2;

    if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=1;
}
inline void workList(){//解决单链
    lcnt=0;
    rep(i,1,N)if(in[i]==1){//压到数组上面
        getlist(i,0);
        break;
    }
    /*
    printf("this is the list:");
    rep(i,1,N)writc(lt[i],' ');
    putchar('\n');
    printf("this is pt arr:");
    rep(i,1,N)writc(pt[i],' ');
    putchar('\n');
    */

    rep(i,1,N)vis[i]=false,mir[a[i]]=i,mark[i]=0;

    rep(i,1,N)rep(j,1,N)if(!vis[j]&&pt[j]!=pt[mir[i]]){
        //目标位置不能和本来的位置重合并且目标位置还没有被其他优先级更高的数占有
        // printf("Now the number is %d, the goal position is %d\n",i,j);
        int p1=mir[i],p2=j;bool flg=false;
        if(pt[p1]<=pt[p2]){//如果这个数是往左边走
            if(chkl(p1,p2))
                getMarkl(p1,p2),flg=true;
        }
        else{//反之
            if(chkr(p1,p2))
                getMarkr(p1,p2),flg=true;
        }
        if(flg){//记录答案
            ans[i]=j,vis[j]=true;
            break;
        }
    }
    rep(i,1,N-1)writc(ans[i],' ');//输出答案
    writc(ans[N],'\n');
}

int T;

signed main(){
#ifdef FILEOI
    freopen("rdata.out","r",stdin);
    freopen("file.out","w",stdout);
#endif
    qread(T);
    while(T--){
        init();
        if(N<=10)getDfs();
        else if(maxin==N-1)work();
        else if(maxin==2)workList();
        else puts("gugugu~~~");
    }
    return 0;
}

方法 4 : 100pts

目前尚待讨论...

将它们排成一排之后，发现它有点像链表。

考虑用链表维护删除边的先后关系。

但是这里有个问题：如果一个点删除边的顺序不一定是连续的怎么办？

对于这种情况，我们只需要把它们看成有许多个链表，但是它们没有接在一起即可。

那么，我们怎么寻找一条合法路径？

我们把这个方法的寻径算法分成几个部分：

• 对于起飞点（即数字一开始所在的点）
• 对于中转点
• 对于结束点

部分 1:对于起飞点

对于一个起飞点 u，我们考虑寻找一条起飞边，并且这条起飞边是一定存在。

那么，这条起飞边需要满足什么条件？

首先，这条起飞边前面不能有什么其他的东西。

即对于点 u 的删边顺序所连成的链表集中，这条边必须是其中某一条链的起点。

而且，我们分析，如果这是一条起飞边，那么它一定是所有 u 的边中最先删除的那条边（如果不知道为什么，参考本题链的处理方法）

还有一种特殊情况，留到后面结束点之后分析。

部分 2:对于中转点

如果这是一个中转点，考虑枚举一条边 e' 在 e (我们之前删除的那条边)

而这个中转点必须满足什么条件呢?

毕竟 e' 是接在 e 之后的，那么一定要保证 e' 之前没有其他的边。

而且，点 e' 与点 e 还没有连在一起，即它们分别所在不同的链上（因为我们本来就是要将他们连在一起）。

并且，e' 是在 e 之后，但是如果 e' 是一条起飞边，即这条边必须是最先删除的，那么 e' 就是不符合的。

还有一种特殊情况，留到后面结束点之后分析。

部分 3:对于降落点

如果点 u 是一个降落点，那么我们的边 e 必须是最后删除的（如果不知道为什么，参考本题链的处理方式）

即，对于一个点 u ，我们目前还并未指定 u 的某一条边必须是结束边。

但是还有一种情况，这种情况与前面的两个部分都有关。

如果这条结束边 e 是与前面的起飞边在同一条链上，即它们先后顺序已确定，那么我们必须要保证这个删边顺序组成的链中，长度刚好为 u 的边数。

为什么？因为我们最后，必须保证每条边都被删去。

而上面这种情况，即是我们将最开头所删除的边，与最末尾所删除的边连接在一起而形成一个完整的、已无法再次修改的长链，而如果有剩余的边没有被删去，它们就没有机会再插入到这个链之中，也就是说找不到任何一个机会去删除这条边，与题意不符。

生动地说，我们不能让这个完整的链出现提前自闭的情况。

知道这个之后，我们再反过来补充 部分 1 与 部分 2 。

部分 1 补充

因为我们已经指定起飞边 e ，而我们要将边 e' 接到 e 之后。

但是如果 e' 已经与降落边，即末删边相连，那么我们也要防止提前自闭的情况。

所以我们也要特判一下，链长度必须与 u 的边数一样。

部分 2 补充

如果我们的边 e 已经连接到起始边，而 e' 已经连接到末删边。

那如果我们要将 e 与 e' 连起来删，也就是将两个完整链连接起来，这也是防止提前自闭的情况。

总的时间复杂度 O(N^2) ，常数我就不知道了，但是能过...

代码如下（自带注释）

#include<cstdio>
#include<vector>
using namespace std;

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
// #define FILEOI

#define cg (c=getchar())
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
inline int qread(){
    int x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=-1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);putchar(x%10^48);
}

const int MAXN=2000;

struct edge{
    int to,nxt;
    edge(){}
    edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,siz[MAXN+5];
inline void add_edge(const int u,const int v){
    ++siz[u],++siz[v];
    e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
    e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}

int N,minp;
int pt[MAXN+5];
int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];
//这条边的 前驱,后继
int rt[MAXN+5][MAXN+5][2];
//点 u 的某一条边的 前根节点、后根节点
int len[MAXN+5][MAXN+5];
//这条边 所在链 的链表长度

inline void init(){
    qread(N);
    ecnt=0;
    rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;
    rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;

    int u,v;
    rep(i,1,N-1){
        qread(u,v);
        add_edge(u,v);
        pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;
        rt[u][v][0]=rt[u][v][1]=v;
        rt[v][u][0]=rt[v][u][1]=u;
        len[u][v]=len[v][u]=1;
    }
}

void findPath(const int u,const int p){//当前节点、前一个节点
    int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
    //a:来的边的前根 ; b:来的边的后根
    if(p==N+1){//这是起点
        for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞
            v=e[i].to;
            ta=rt[u][v][0],tb=rt[u][v][1];
            if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))
            //条件一:如果这条边已经有一个起点且不是自己
            //条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来
                continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起
            findPath(v,u);//否则可行
        }
    }
    else{
        if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面
            if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:
            //如果这个点的末删边还没有被指定(必须满足)
            //并且:
            //1.如果这条链接上开头，那么如果必须满足所有的边都在这条链上
            //2.如果没有接上开头，那么长度随意
                minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点

            for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边，与其尾相连
                v=e[i].to;
                ta=rt[u][v][0],tb=rt[u][v][1];
                if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况
                //如果这两条边已经在同一条链上
                //或者这个边不是一个起始边, 即枚举边的前面还有东西
                //或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边
                    continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上

                if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])
                //如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头
                //那么它们组合起来必须等于所有边的数量之和
                //否则, 这就是 提前自闭 的情况
                    continue;

                findPath(v,u);//如果以上都不满足, 那么这条边是合法的
            }
        }
        else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边
    }
}

inline void merge(const int u,const int a,const int b){
//函数条件:以 a 所在的链表为前链表
//并且满足 a 是前链表尾, b 是后链表头
    int ta=rt[u][a][0],tb=rt[u][b][1];
    nxt[u][a]=b;
    pre[u][b]=a;
    for(int i=ta;i && i!=N+1;i=nxt[u][i]){
    //访问链表的基本操作
        //更新每个点的前根、后根
        rt[u][i][0]=ta;
        rt[u][i][1]=tb;
    }
    len[u][ta]+=len[u][b];
}

bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记
//如果这条路径找到终点, 返回 1, 否则返回 0
    if(u==minp){//如果找到了终点
        pre[u][N+1]=p;//把这条边设为最后删除的边
        nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的
        return 1;
    }
    int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
    if(p==N+1){//这是起飞点
        for(int i=tail[u],v;i;i=e[i].nxt){
            v=e[i].to;
            ta=rt[u][v][0],tb=rt[u][v][1];
            if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))
            //如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了
            //或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面
                continue;//那么这条边肯定不在路径上面, 可直接跳过
            if(getMark(v,u)){//如果这就是正确的路径
                nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边
                pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)
                return 1;
            }
        }
    }
    else{//如果点 u 是中转点, 那么考虑枚举中转边
        if(p==b){//如果这条边在链上后面没有其他边的时候
            for(int i=tail[u],v;i;i=e[i].nxt){
                v=e[i].to;
                ta=rt[u][v][0],tb=rt[u][v][1];
                if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释
                    continue;
                if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置
                    continue;
                if(getMark(v,u)){
                    merge(u,p,v);//把链表合并为一个
                    return 1;
                }
            }
        }
        else getMark(nxt[u][p],u);
    }
    return 0;
}

signed main(){
#ifdef FILEOI
    freopen("rdata.out","r",stdin);
    freopen("file.out","w",stdout);
#endif
    int T=qread();
    while(T--){
        init();
        if(N==1){
            writc(1,'\n');
            continue;
        }
        rep(i,1,N){
            minp=N+1;
            findPath(pt[i],N+1);
            // printf("%d\n",minp);
            getMark(pt[i],N+1);
            writc(minp,' ');
        }
        putchar('\n');
    }
    return 0;
}