TIOJ 1885：【IOI2015】Scales 斯克兒悠斯-一堆天平

TIOJ 1885：【IOI2015】Scales 斯克兒悠斯-一堆天平

題目大意：有 $6$ 顆編號 $1\sim 6$ 的石頭，每顆重量都不一樣，可以做四種詢問，第一種是問 $3$ 顆石頭中最重的，第二種是問 $3$ 顆石頭中最輕的，第三種是問 $3$ 顆石頭重量介在中間的，第四種是問石頭 $a,b,c,d$ 中，比 $d$ 重最輕的石頭，若都比 $d$ 輕，則回答最輕的。你最多只能用 $6$ 次詢問找出石頭的重量關係。

解法：很難直接想出一個簡單的策略，所以只能用電腦暴搜，總共有 $720$ 個排列，每次詢問會有 $3$ 種結果，相當於把這些排列分成 $3$ 份，如果某一份的大小太大，那就會詢問太多次 ，之後繼續遞迴就能建出要問的東西了。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "lib1885.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int MAX = 720;

array<int, 6> P[MAX];
int pos[MAX][7];

struct Tree {
    int ty, a, b, c, d;
    Tree *nxt[3];
    Tree() {}
    Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
    tuple<int, int, int, int, int> id() {
        return {ty, a, b, c, d};
    }
};
Tree *root;

bool build(Tree *&t, vector<int> cur, int lim) {
    if (cur.size() <= 1) return 1;
    t = new Tree();
    FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
        *t = Tree(ty, i, j, k);
        vector<int> vi, vj, vk;
        bool f = 1;
        for (int id : cur) {
            int cp;
            if (ty == 1) cp = min({pos[id][i], pos[id][j], pos[id][k]});
            if (ty == 2) cp = max({pos[id][i], pos[id][j], pos[id][k]});
            if (ty == 3) cp = pos[id][i] + pos[id][j] + pos[id][k] - min({pos[id][i], pos[id][j], pos[id][k]}) - max({pos[id][i], pos[id][j], pos[id][k]});
            (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id);
            if (max({vi.size(), vj.size(), vk.size()}) > lim) {
                f = 0;
                break;
            }
        }
        if (f) f &= build(t->nxt[0], vi, lim / 3);
        if (f) f &= build(t->nxt[1], vj, lim / 3);
        if (f) f &= build(t->nxt[2], vk, lim / 3);
        if (f) return 1;
    }
    FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
        *t = Tree(4, i, j, k, d);
        vector<int> vi, vj, vk;
        bool f = 1;
        for (int id : cur) {
            int pi = pos[id][i], pj = pos[id][j], pk = pos[id][k], pd = pos[id][d], cp = 6;
            for (int xp : {pi, pj, pk}) if (xp > pd) cp = min(cp, xp);
            if (cp == 6) cp = min({pi, pj, pk});
            (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id);
            if (max({vi.size(), vj.size(), vk.size()}) > lim) {
                f = 0;
                break;
            }
        }
        if (f) f &= build(t->nxt[0], vi, lim / 3);
        if (f) f &= build(t->nxt[1], vj, lim / 3);
        if (f) f &= build(t->nxt[2], vk, lim / 3);
        if (f) return 1;
    }
    delete(t);
    return 0;
}

int main() {
    int tt = Init();
    array<int, 6> a;
    iota(a.begin(), a.end(), 1);
    FOR (i, 0, MAX - 1) {
        P[i] = a;
        FOR (j, 0, 5) pos[i][a[j]] = j;
        next_permutation(a.begin(), a.end());
    }
    vector<int> all(MAX);
    iota(all.begin(), all.end(), 0);
    build(root, all, 243);
    while (tt--) {
        orderCoins();
        vector<int> all(MAX);
        iota(all.begin(), all.end(), 0);
        Tree *cur = root;
        while (all.size() > 1) {
            int result;
            auto [ty, a, b, c, d] = cur->id();
            if (ty == 1) result = getLightest(a, b, c);
            if (ty == 2) result = getHeaviest(a, b, c);
            if (ty == 3) result = getMedian(a, b, c);
            if (ty == 4) result = getNextLightest(a, b, c, d);
            vector<int> tmp;
            for (int id : all) {
                int pi = pos[id][a], pj = pos[id][b], pk = pos[id][c];
                if (ty == 1 && min({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
                if (ty == 2 && max({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
                if (ty == 3 && pi + pj + pk - min({pi, pj, pk}) - max({pi, pj, pk}) == pos[id][result]) tmp.pb(id);
                if (ty == 4) {
                    int mn = 6;
                    for (int xp : {pi, pj, pk}) if (xp > pos[id][d]) mn = min(mn, xp);
                    if (mn == 6) mn = min({pi, pj, pk});
                    if (mn == pos[id][result]) tmp.pb(id);
                }
            }
            all = tmp;
            cur = (result == a ? cur->nxt[0] : result == b ? cur->nxt[1] : cur->nxt[2]);
        }
        int ans[6];
        FOR (i, 0, 5) ans[i] = P[all[0]][i];
        answer(ans);
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！