题解：P8041 [COCI 2016/2017 #7] POKLON

linjinkun · 2025-10-21 13:15:18 · 题解

简单树形 DP。

首先设 f_i 表示 i 的子树中天平砝码的总质量，那么显然存在转移式 f_i = 2 \times \max(f_{l_i},f_{r_i})，但这样很明显无法通过此题。那么根据题目中的二进制，又可以想到绝妙的办法，你会发现每一个 f_i 都可以表示为 2^k \times x，那么可以通过取 \log 来避免溢出，这样也更方便表示二进制。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local

#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() {
        T s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s * w;
    }
    template<typename T> inline bool read(T &s) {
        s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s *= w, true;
    }
    inline bool read(char &s) {
        while (s = getchar(), isspace(s));
        return true;
    }
    inline bool read(char *s) {
        char ch;
        while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) *s++ = ch, ch = getchar();
        *s = '\000';
        return true;
    }
    template<typename T> inline void print(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) print(x / 10);
        putchar(x % 10 + 48);
    }
    inline void print(char x) {
        putchar(x);
    }
    inline void print(char *x) {
        while (*x) putchar(*x++);
    }
    inline void print(const char *x) {
        for (int i = 0; x[i]; ++i) putchar(x[i]);
    }
    inline bool read(std::string& s) {
        s = "";
        char ch;
        while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) s += ch, ch = getchar();
        return true;
    }
    inline void print(std::string x) {
        for (int i = 0, n = x.size(); i < n; ++i)
            putchar(x[i]);
    }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) {
        return read(a) + read(other...);
    }
    template<typename T, typename... T1> inline void print(T a, T1... other) {
        print(a);
        print(other...);
    }

    struct Fast_IO {
        ~Fast_IO() {
            fwrite(obuf, p3 - obuf, 1, stdout);
        }
    } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
        return read(b), io;
    }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
        return print(b), io;
    }
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
const int N = 1e6+5;
struct node
{
    int l;
    int r;
}a[N];
int pre[N];
int v[N];
double dfs(int x)
{
    double l,r;
    if(a[x].l>0)
    {
        l = dfs(a[x].l);
    }
    else 
    {
        l = log2(-a[x].l);
    }
    if(a[x].r>0)
    {
        r = dfs(a[x].r);
    }
    else
    {
        r = log2(-a[x].r);
    }
    if(l>r)
    {
        pre[x] = a[x].l;
    }
    else
    {
        pre[x] = a[x].r;
    }
    return max(l,r)+1;
}
signed main()
{
    int n;
    cin >> n;
    for(int i = 1;i<=n;++i)
    {
        cin >> 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;
            }
            x = -x;
            int flag = 0;
            for(int i = 30;i>=0;--i)
            {
                if(x&(1<<i))
                {
                    cout << 1;
                    flag = 1;
                }
                else if(flag)
                {
                    cout << 0;
                }
            }
            for(int i = 1;i<=cnt;++i)
            {
                cout << 0;
            }
        }
    }
    return 0;
}