P8041 [COCI2016-2017#7] POKLON 题解

伟大的王夫子 · 2022-08-18 21:17:09 · 题解

树形 DP。

令 dp_{x} 表示以 x 为根的子树的最小质量。设 L_x 为 x 左子节点，R_x 为右子节点，那么 dp_x = 2 \times \max(dp_{L_x}, dp_{R_x})。对于一个叶子节点，那么其 dp 值等于该节点的砝码重量。

但这样明显通过不了此题。可以构造数据，使得答案非常大。于是我们可以将 dp_x 的定义改为答案的对数，并且用数组 pre 记录 dp_x 是从哪个节点转移过来的，方便构造方案。我们输出答案则是根据 pre 数组一直往下走，直到找到一个叶子节点为止。设这个叶子结点的质量为 y，并且我们走过了 cnt 条边，那么答案便是 y \times 2 ^ {cnt}，十分容易用二进制输出。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
using LL = long long;
struct {
    int l, r, v;
} a[N];
bool v[N];
int n, pre[N];
double dfs(int x) {
    double ll, rr;
    if (a[x].l > 0)
        ll = dfs(a[x].l);
    else
        ll = log2(-a[x].l);
    if (a[x].r > 0)
        rr = dfs(a[x].r);
    else
        rr = log2(-a[x].r);
    if (ll > rr)
        pre[x] = a[x].l;
    else
        pre[x] = a[x].r;
    return max(ll, rr) + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].l, &a[i].r);
        if (a[i].l > 0)
            v[a[i].l] = 1;
        if (a[i].r > 0)
            v[a[i].r] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!v[i]) {
            dfs(i);
            int x = i, cnt = 0;
            while (x > 0) {
                x = pre[x];
                ++cnt;
            }
            bool ff = 0;
            x = -x;
            for (int i = 30; i >= 0; --i)
                if (x & 1 << i)
                    printf("1"), ff = 1;
                else if (ff)
                    printf("0");
            for (int i = 1; i <= cnt; ++i) printf("0");
        }
}