CF2171F Rae Taylor and Trees (hard version) 题解

· · 题解

思路

Easy ver.

先考虑简单版，刚开始盲猜只要有 n-1 条或更多合法边即可，即顺序对个数 \ge n-1，于是问题转化为求逆序对个数的模板，最后用数对总数减去逆序对个数再与 n-1 比较即可。

但是这是错误的，例如样例中的：

7
4 3 5 7 6 2 1

其中有 8 个顺序对，但显然无法构成一颗树。

更加极端的有如下样例：

6
6 1 2 3 4 5

显然 6 无法与任何节点建立连边。可以看出逆序对无法解决此问题，考虑换一个思路。

由于边是无向的，因此只要能使 n 个点连通，则必定存在一颗生成树。考虑用并查集维护连通块，倒序枚举序列，同时维护一个单调栈，当有新元素加入时，将栈顶所有大于新元素的与新元素合并，并将新元素入栈。但是需要注意的是，新元素入栈后其值要设置成与它合并的所有块中的最大值，这样后面的元素才能与它继续合并。举个例子：

3
2 1 3

显然 1,3 合并后，2 仍能跟 3 合并，但此时栈顶元素为 1 的话无法合并，故 1,3 合并时将 3 入栈。

最后判断是否只剩一个连通块即可。

Hard ver.

简单版做出来后，困难版就秒了。

其实刚才的过程中已经包含建树了：每次入栈元素与栈顶连通块中最大值合并。这样一次连通块合并只产生一条边，若可行则产生 n-1 条边，必定形成一棵树。具体看代码实现。

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+5;
int T,n;
int a[NR];
int f[NR],sz[NR];
vector<int> g[NR];
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
bool merge(int x,int y){
    int t1=find(x),t2=find(y);
    if(t1==t2) return 0;
    if(sz[t1]<sz[t2]){
        f[t1]=t2;
        sz[t2]+=sz[t1];
    }
    else{
        f[t2]=t1;
        sz[t1]+=sz[t2];
    }
    return 1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            f[i]=i,sz[i]=1;
            g[i].clear();
        }
        stack<pair<int,int>> st;//first表示实际下标，second表示first所在连通块的最大值的下标
        int cnt=n;
        for(int i=n;i>=1;i--){
            int mx=i;
            while(!st.empty()&&a[i]<a[st.top().second]){//与最大值比较
                cnt-=merge(i,st.top().first);//与实际下标合并
                if(a[st.top().second]>a[mx]) mx=st.top().second;
                g[i].push_back(st.top().second);//与最大值连树边
                st.pop();
            }
            st.push(make_pair(i,mx));
        }
        if(cnt!=1) printf("No\n");
        else{
            printf("Yes\n");
            for(int i=1;i<=n;i++){
                for(auto j:g[i]){
                    printf("%d %d\n",a[i],a[j]);
                }
            }
        }
    }
    return 0;
}
/*
1
6
1 3 4 5 2 6
*/

简单版和困难版真的有区别吗？