题解 CF1283F 【DIY Garland】

· · 题解

出题人题解咕掉了，照着代码理解了一下写写个人的看法。

算法的思想大致是这样：按照给出边的顺序遍历，$i$为边序号。如果$i<n$且第$i+1$条边的父亲未定，则连接$a[i]$与$a[i+1]$。否则连接$a[i]$和$cur$，后者为当前未确定父亲的编号最大的节点。 这样，每次连接第$i$条边时，$a[i]$的父亲都是已经确定的（$a[1]$是根节点例外）。这意味着，满足$used[i]=1$的点$i$不可能对之后的边的重要性产生贡献。 设第$i$条边的重要性是$d_i$。 如果$a[i]$连接了$cur$，因为$cur$是当前$used[i]=0$的编号最大节点，之后的边的子树中的节点编号必然小于$cur$。$2^i>2^{i-1}+2^{i-2}+...+2^1+2^0$。所以$d_i>d_j (j>i)$，特殊地，$d_i>d_{i+1}$。 如果$a[i]$连接了$a[i+1]$,那么$a[i]$是$a[i+1]$的父亲，显然$d_i>d_{i+1}$。 综上所述$d_1>d_2>...>d_{n-1}>d_n

对于所有合法数据均能构造出这样的解，不需要考虑无解情况。

code：

#include <bits/stdc++.h>
#define MAXN 210000
#define _ 0
using namespace std;

int n;
int a[MAXN];
int used[MAXN];

int main()
{
    int n;
    cin>>n;
    int cur=n;
    n--;
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    cout<<a[1]<<endl;
    used[a[1]]=1;
    for (int i=1;i<=n;i++)
    {
        while (used[cur])
            cur--;
        if (used[a[i+1]] || i==n)
        {
            cout<<a[i]<<' '<<cur<<endl;
            used[cur]=1;
        }
        else
        {
            cout<<a[i]<<' '<<a[i+1]<<endl;
            used[a[i+1]]=1;
        }
    }
    return ~~(0^_^0);
}