题解：CF1919D 01 Tree

Graph_Theory · 2025-05-19 11:51:46 · 题解

题意

有一种节点两边边权为 0 和 1 满二叉树，其中叶子结点 i 的边权为从根节点到当前节点路径上的边权之和 a_i。

给定 a_i，求是否存在一种满二叉树。

说明一下，这里的满二叉树是指子节点数量为 0 或 2 的二叉树。

思路

同一个父亲的两个叶子结点 i 和 i+1 由于边权为 1 和 0，所以一定满足 | a_i-a_{i+1}|=1。其父节点点权为 \min(a_i,a_{i+1})，因为是个满二叉树，所以删除一个节点的所有子节点后依旧是一个满二叉树。所以当遇到一对节点满足 | a_i-a_{i+1}|=1 时我们就可以把这两个点合并成 \min(a_i,a_{i+1})。最后若只剩下一个 0 就是成立的。

当然这个很明显是错的。

考虑 0 1 2 这样一组样例，如果按照上面的思路，我们可以得到两种结果，第一种是将 0 1 合并得到 0 2不成立。第二种是将 1 2 合并得到 0 1 此时又成立。

所以我们发现，我们每一次合并时都应该从最大节点开始合并。

所以直接搞一个优先队列每次把一个节点丢进去，每一次选择 a_i 最大的。

若一个点的左边和右边 a_i-a_{i+1}>1 且 a_i-a_{i-1}>1，显然不成立。

若一个点的左边和右边 a_i-a_{i+1}=1 且 a_i-a_{i-1}=1，这样的话向任意一个合并都是满足的。

然后 a_i=0 的数量是 1，否则不成立。

然后发现 3 3 2 1 0 过不去，原来访问到第一个 3 时左右没法合并，但是后面合并完之后又可以了，所以当一个点和右边或左边相等时，就再丢进去，防止连续两次访问到了同一个节点但是有多个 a 相同的，例如这里有两个 3，这里又加了一个 rank。

还是过不去。发现是合并完之后 3 2 1 0 会默认向右合并，于是当两个点都可以合并时优先合并 a 更大的那一个，可以证明更优。

还有就是当一个点非常大，两边都没法合并，也是无解的。

删除完之后把当前节点的右节点就连接在刚刚消除的那个点的右节点上，刚刚消除的那个点的右节点的左节点就连接到当前点上。

代码

#include <bits/stdc++.h>
#define maxn 200009
using namespace std;

int n;
//bool vis[maxn];

struct item
{
    int id, dis, live = 1, l, r;
    bool operator <(const item& b) const
    {
        return dis < b.dis;
    }
    bool operator >(const item& b) const
    {
        return dis > b.dis;
    }
} a[maxn];
int cnt0;
struct que
{
    int dis, id, rank, viscnt;
    bool operator <(const que& b) const
    {
        return dis == b.dis ? rank > b.rank : dis <= b.dis;
    }
    bool operator >(const que& b) const
    {
        return dis == b.dis ? rank<b.rank: dis >= b.dis;
    }
};
priority_queue<que> q;
int sum, num, ans, mergesum;
signed main_()
{
    sum = num = ans = mergesum = cnt0 = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i].l = i - 1;
        a[i].r = i + 1;
        a[i].id = a[i].dis = 0;
        a[i].live = 1;
    }
    while (!q.empty()) q.pop();
    cin >> n;
    mergesum = n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].dis;
        a[i].id = i;
        a[i].l = i - 1;
        a[i].r = i + 1;
        q.push({a[i].dis, i, 1, 0});
        if (a[i].dis == 0) cnt0++;
        if (cnt0 > 1) return cout << "No" << endl, 0;
    }
    if (cnt0 == 0) return cout << "No" << endl, 0;
    int now = 0;
//cerr<<q.size()<<endl;
    while (!q.empty())
    {
//cerr<<"run"<<endl;
        now++;
        auto top = q.top();
        q.pop();
        if (a[top.id].live == 0 || mergesum == 1) continue;

//      cerr<<top.id<<" "<<top.dis<<" "<<top.viscnt<<" "<<top.rank<<endl;

        if (a[top.id].dis - a[a[top.id].r].dis > 1 && a[top.id].dis - a[a[top.id].l].dis > 1) return cout << "No" << endl, 0;
        else if (a[a[top.id].r].dis == a[top.id].dis && a[a[top.id].l].dis == a[top.id].dis)
        {
            if (top.viscnt == now - 1) return cout << "No" << endl, 0;
            q.push({a[top.id].dis, top.id, top.rank + 1, now});
            continue;
        }
        int flag = 3;
        if (
        ((a[a[top.id].l].dis == a[top.id].dis + 1 || a[a[top.id].l].dis + 1 == a[top.id].dis) && a[top.id].l != 0)
            &&
        ((a[a[top.id].r].dis + 1 == a[top.id].dis || a[a[top.id].r].dis == a[top.id].dis + 1) && a[top.id].r != n + 1)
        )
        {
            if (a[a[top.id].l].dis < a[a[top.id].r].dis) flag = 1;
            else flag = 0;
//          cerr<<"2ok"<<endl;
        }
        if (
        (flag == 3 && ((a[a[top.id].r].dis + 1 == a[top.id].dis || a[a[top.id].r].dis == a[top.id].dis + 1) && a[top.id].r != n + 1)) || flag == 1)
        {
//          cerr<<a[top.id].dis<<" "<<a[a[top.id].r].dis<<" "<<a[top.id].r<<" "<<min(a[a[top.id].r].dis,a[top.id].dis)<<endl;
            a[a[top.id].r].live = 0;
            a[top.id].dis = min(a[a[top.id].r].dis, a[top.id].dis);

            a[a[a[top.id].r].r].l = top.id;
            a[top.id].r = a[a[top.id].r].r;
//
//          cerr<<a[top.id].dis<<endl;
            q.push({a[top.id].dis, top.id, 1, now});
            mergesum--;
//          cerr<<"merge r"<<endl;
        }
        else if (
        (flag == 3 && ((a[a[top.id].l].dis == a[top.id].dis + 1 || a[a[top.id].l].dis + 1 == a[top.id].dis) && a[top.id].l != 0)) || flag == 0)
        {
            a[a[top.id].l].live = 0;
            a[top.id].dis = min(a[a[top.id].l].dis, a[top.id].dis);

            a[a[a[top.id].l].l].r = top.id;
            a[top.id].l = a[a[top.id].l].l;

            q.push({a[top.id].dis, top.id, 1, now});
            mergesum--;
//          cerr<<"merge l"<<endl;
        }
//      cerr<<"end"<<endl;
    }
//  cerr<<endl<<endl<<endl;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].live == 1) sum++;
        if (a[i].dis == 0)  num++;
        if (a[i].live == 1 && a[i].dis == 0) ans++;
//      cerr<<i<<" "<<a[i].live<<" "<<a[i].dis<<endl;
    }
//  cerr<<sum<<" "<<num<<endl;
//  cerr<<a[1].r<<endl;
//  cerr<<a[1].dis<<endl;
    if (ans == 1 && sum == 1) cout << "Yes" << endl;
    else               cout << "No" << endl;
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
        main_();
    return 0;
}

然后发现上面这一坨石山代码常数太大超时了。

小小优化一下，发现成立的情况下合并的次数恰好是 n-1 次，这样大于 n-1 次时，直接退出。

然后又超时了。

如果连续两次访问到了同一个节点同样优化掉。发现这个似乎和上面的 rank 重复了。保留一个就可以

发现可以只向右边合并，然后初始化的 push 条件从无条件设置为能和右边合并再 push 进去。这样向右合并优化掉了，那种很大的两边都没法合并的就不会再进去了。然后又遇到 3 3 2 1 0 了，这里更新了一个点后，把当前这个点和左边这个点 push 进去，rank 也优化掉了，这下上面的一个没保留。

这样就写完了。

#include <bits/stdc++.h>
using namespace std;

#define maxn 200005
struct item
{
    int dis;
    int l, r;
    bool live;
} a[maxn];

struct que
{
    int dis, i;
    bool operator<(que const& o) const
    {
        return dis != o.dis ? dis < o.dis ： i > o.i;
    }
};

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].dis;
            a[i].live = true;
            a[i].l = i - 1;
            a[i].r = i + 1;
        }
        a[0].live = a[n + 1].live = false;
        a[0].r = 1;
        a[n + 1].l = n;
        priority_queue<que> pq;
        auto try_push = [&](int i)
        {//lambda表达式，这样不用清空数组了
            int j = a[i].r;
            if (i >= 1 && j <= n && a[i].live && a[j].live
            && abs(a[i].dis - a[j].dis) == 1)
            {
                pq.push({ min(a[i].dis, a[j].dis), i });
            }
        };

        for (int i = 1; i < n; i++)
            try_push(i);
        int merges = 0;
        while (!pq.empty() && merges < n - 1)
        {
            auto top = pq.top();
            pq.pop();
            int i = top.i, j = a[i].r;

            if (!(i >= 1 && j <= n && a[i].live && a[j].live
            && abs(a[i].dis - a[j].dis) == 1
            && min(a[i].dis, a[j].dis) == top.dis))
                continue;

            a[i].dis = top.dis;
            a[j].live = false;
            merges++;

            int jj = a[j].r;
            a[i].r = jj;
            a[jj].l = i;

            try_push(a[i].l);
            try_push(i);
        }
        bool ok = false;
        if (merges == n - 1)
            for (int i = 1; i <= n; i++)
                if (a[i].live)
                {
                    ok = (a[i].dis == 0);
                    break;
                }
        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}