题解：P15284 [IOI 2015] Scales 天平

harmis_yz · 2026-10-20 10:21:04 · 题解

分析

首先不难发现 Q 应该是 6。

考虑把决策树建出来。

具体的，搜索过程中维护可能的排列集合 S 以及剩余询问次数 stp。枚举所有可能的询问方式，一种询问方式会将排列集合分成 S_1,S_2,S_3 三个部分。

如果 3^{stp - 1} < \max(|S_1|,|S_2|,|S_3|) 显然不能这么问，因为极端情况下也无法区分。

对于可能的询问方式，定义其熵 H = -\sum\limits_{i=1}^{3}(\frac{|S_i|}{|S|})\log(\frac{|S_i|}{|S|})。优先尝试搜索 H 较大的，直到存在一组能够在 stp 次询问内区分所有排列的询问方式或所有询问方式均不可能为止。

最后把询问路径存下来就得到了决策树。

代码

extern "C"
{
    void init(int T);
    void orderCoins();
    void answer(int W[]);
    int getMedian(int A, int B, int C);
    int getHeaviest(int A, int B, int C);
    int getLightest(int A, int B, int C);
    int getNextLightest(int A, int B, int C, int D);
}
#include<bits/stdc++.h>
using namespace std;
#define re register
#define U(i, x, y) for(re int i = (x); i <= (y); ++ i)
#define D(i, x, y) for(re int i = (x); i >= (y); -- i)
#define UU(i, x, y) for(re int i = (x); i < (y); ++ i)
#define DD(i, x, y) for(re int i = (x); i > (y); -- i)
#define il inline
#define pii pair<int, int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x = 0, f = 1; char ch = gc;
        while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = gc;}
        while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc;
        return x * f;
    }
    il int qmi(int a, int b, int p){
        if(a == 0) return 0;
        int ans = 1;
        while(b){
            if(b & 1) ans = ans * a % p;
            a = a * a % p, b >>= 1;
        }
        return ans;
    }
    il int gcd(int a, int b){
        if(!b) return a;
        return gcd(b, a % b);
    }
    il int lcm(int a, int b){
        return a / gcd(a, b) * b;
    }
    il void exgcd(int a, int b, int &x, int &y){
        if(! b) return x=1, y=0, void(0);
        exgcd(b, a % b, x, y);
        int t = x;
        x = y, y = t - a / b * x;
        return ;
    }
    struct lb{
        int d[65];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void cle(){
            memset(d,0,sizeof(d));
        }
        il bool operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x, 0;
            }
            return 1;
        }
        il bool insert(int x){
            D(i, 63, 0){
                if(!((x >> i) & 1)) ;
                else{
                    if(d[i]) x^=d[i];
                    else return d[i]=x, 0;
                }
            }
            return 1;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
    mt19937 rnd(time(0));
}
namespace fwt{
    const int M = 3;
    int C0[M][M], G0[M];
    il void FWT(int *f, int C, int n){
        for(re int len = 1; len < n; len *= C){
            for(re int l = 0; l < n; l += len * C){
                for(re int i = l; i < l + len; ++ i){
                    for(re int k = 0; k < C; ++ k){
                        G0[k] = f[i + k * len];
                        f[i + k * len] = 0;
                    }
                    for(re int i0 = 0; i0 < C; ++ i0)
                    for(re int k = 0; k < C; ++ k){
                        f[i + i0 * len] += G0[k] * C0[i0][k];
                    }
                }
            }
        }
        return ;
    }
}
using namespace yzqwq;
// using namespace fwt;

const int inf = 1e9 + 7;
struct node{ int a, b, c, d, typ; double H; };
map<int, node> nxt;
map<int, bool> st;
int B = 12347;

il int getHs(vector<vector<int>> S, int stp){
    long long Hs = 0;
    for(auto x: S) for(auto y: x){ 
        Hs = (1ll * Hs * B + y + 1) % inf;
    }
    Hs = (1ll * Hs * B + stp + 1) % inf;
    return (int)Hs;
}
il double Log(double x){
    if(x == 0) return 0;
    return log2(x);
}
il bool dfs(vector<vector<int>> S, int stp){
    if(S.size() <= 1) return true;
    if(stp == 0) return false;
    int Hs = getHs(S, stp);
    if(st.count(Hs)) return st[Hs];
    vector<node> vec; vec.clear();
    { //getHeaviest
        U(a, 0, 5) U(b, a + 1, 5) U(c, b + 1, 5){
            int s1, s2, s3;
            s1 = 0, s2 = 0, s3 = 0;
            for(auto x: S){
                int v = max({x[a], x[b], x[c]});
                if(v == x[a]) ++s1;
                else if(v == x[b]) ++s2;
                else ++s3;
            }
            int Lim = pow(3, stp - 1);
            if(s1 > Lim || s2 > Lim || s3 > Lim) continue;
            double p1 = s1 * 1.0 / (s1 + s2 + s3);
            double p2 = s2 * 1.0 / (s1 + s2 + s3);
            double p3 = s3 * 1.0 / (s1 + s2 + s3);
            double H = -(p1 * Log(p1) + p2 * Log(p2) + p3 * Log(p3));
            vec.push_back({a, b, c, 0, 1, H});
        }
    }
    { //getMedian
        U(a, 0, 5) U(b, a + 1, 5) U(c, b + 1, 5){
            int s1, s2, s3;
            s1 = 0, s2 = 0, s3 = 0;
            for(auto x: S){
                int v = (x[a] + x[b] + x[c]) - max({x[a], x[b], x[c]}) - min({x[a], x[b], x[c]});
                if(v == x[a]) ++s1;
                else if(v == x[b]) ++s2;
                else ++s3;
            }
            int Lim = pow(3, stp - 1);
            if(s1 > Lim || s2 > Lim || s3 > Lim) continue;
            double p1 = s1 * 1.0 / (s1 + s2 + s3);
            double p2 = s2 * 1.0 / (s1 + s2 + s3);
            double p3 = s3 * 1.0 / (s1 + s2 + s3);
            double H = -(p1 * Log(p1) + p2 * Log(p2) + p3 * Log(p3));
            vec.push_back({a, b, c, 0, 2, H});
        }
    }
    { //getLightest
        U(a, 0, 5) U(b, a + 1, 5) U(c, b + 1, 5){
            int s1, s2, s3;
            s1 = 0, s2 = 0, s3 = 0;
            for(auto x: S){
                int v = min({x[a], x[b], x[c]});
                if(v == x[a]) ++s1;
                else if(v == x[b]) ++s2;
                else ++s3;
            }
            int Lim = pow(3, stp - 1);
            if(s1 > Lim || s2 > Lim || s3 > Lim) continue;
            double p1 = s1 * 1.0 / (s1 + s2 + s3);
            double p2 = s2 * 1.0 / (s1 + s2 + s3);
            double p3 = s3 * 1.0 / (s1 + s2 + s3);
            double H = -(p1 * Log(p1) + p2 * Log(p2) + p3 * Log(p3));
            vec.push_back({a, b, c, 0, 3, H});
        }
    }
    { //getNextLightest
        U(a, 0, 5) U(b, a + 1, 5) U(c, b + 1, 5) U(d, 0, 5) if(d != a && d != b && d != c){
            int s1, s2, s3;
            s1 = 0, s2 = 0, s3 = 0;
            for(auto x: S){
                int v = min({((x[a] > x[d]) ? x[a] : inf), ((x[b] > x[d]) ? x[b] : inf), ((x[c] > x[d]) ? x[c] : inf)});
                if(v == inf) v = min({x[a], x[b], x[c]});
                if(v == x[a]) ++s1;
                else if(v == x[b]) ++s2;
                else ++s3;
            }
            int Lim = pow(3, stp - 1);
            if(s1 > Lim || s2 > Lim || s3 > Lim) continue;
            double p1 = s1 * 1.0 / (s1 + s2 + s3);
            double p2 = s2 * 1.0 / (s1 + s2 + s3);
            double p3 = s3 * 1.0 / (s1 + s2 + s3);
            double H = -(p1 * Log(p1) + p2 * Log(p2) + p3 * Log(p3));
            vec.push_back({a, b, c, d, 4, H});
        }
    }
    sort(vec.begin(), vec.end(), [](node x, node y){
        return x.H > y.H;
    });
    if(vec.empty()) return st[Hs] = false;
    for(auto [a, b, c, d, typ, H] : vec){
        vector<vector<int>> s1, s2, s3;
        s1.clear(), s2.clear(), s3.clear();
        for(auto x: S){
            int v;
            if(typ == 1){
                v = max({x[a], x[b], x[c]});
            }
            else if(typ == 2){
                v = (x[a] + x[b] + x[c]) - max({x[a], x[b], x[c]}) - min({x[a], x[b], x[c]});
            }
            else if(typ == 3){
                v = min({x[a], x[b], x[c]});
            }
            else{
                v = min({((x[a] > x[d]) ? x[a] : inf), ((x[b] > x[d]) ? x[b] : inf), ((x[c] > x[d]) ? x[c] : inf)});
                if(v == inf) v = min({x[a], x[b], x[c]});
            }
            if(v == x[a]) s1.push_back(x);
            else if(v == x[b]) s2.push_back(x);
            else s3.push_back(x);
        }
        if(dfs(s1, stp - 1) && dfs(s2, stp - 1) && dfs(s3, stp - 1)){
            nxt[Hs] = {a, b, c, d, typ, H};
            st[Hs] = true;
            return true;
        }
    }
    return st[Hs] = false;
}
il void solve(vector<vector<int>> S, int stp){
    if(S.size() == 1){
        int W[6];
        U(i, 0, 5) W[S[0][i] - 1] = i + 1;
        answer(W);
        return ;
    }
    int Hs = getHs(S, stp);
    auto [a, b, c, d, typ, H] = nxt[Hs];
    vector<vector<int>> s1, s2, s3;
    s1.clear(), s2.clear(), s3.clear();
    for(auto x: S){
        int v;
        if(typ == 1){
            v = max({x[a], x[b], x[c]});
        }
        else if(typ == 2){
            v = (x[a] + x[b] + x[c]) - max({x[a], x[b], x[c]}) - min({x[a], x[b], x[c]});
        }
        else if(typ == 3){
            v = min({x[a], x[b], x[c]});
        }
        else{
            v = min({((x[a] > x[d]) ? x[a] : inf), ((x[b] > x[d]) ? x[b] : inf), ((x[c] > x[d]) ? x[c] : inf)});
            if(v == inf) v = min({x[a], x[b], x[c]});
        }
        if(v == x[a]) s1.push_back(x);
        else if(v == x[b]) s2.push_back(x);
        else s3.push_back(x);
    }
    int A;
    if(typ == 1) A = getHeaviest(a + 1, b + 1, c + 1);
    else if(typ == 2) A = getMedian(a + 1, b + 1, c + 1);
    else if(typ == 3) A = getLightest(a + 1, b + 1, c + 1);
    else A = getNextLightest(a + 1, b + 1, c + 1, d + 1);
    if(A == a + 1) solve(s1, stp - 1);
    else if(A == b + 1) solve(s2, stp - 1);
    else solve(s3, stp - 1);
    return ;
}

void init(int T){
    vector<vector<int>> S; S.clear();
    vector<int> x; x.clear();
    U(i, 1, 6) x.push_back(i);
    do{
        S.push_back(x);
    } while(next_permutation(x.begin(), x.end()));
    dfs(S, 6);
}

void orderCoins(){
    vector<vector<int>> S; S.clear();
    vector<int> x; x.clear();
    U(i, 1, 6) x.push_back(i);
    do{
        S.push_back(x);
    } while(next_permutation(x.begin(), x.end()));
    solve(S, 6);
}