解题报告

考虑决策树，每次枚举操作，根据返回的结果把符合当前状态的排列分成三份（当然如果符合当前状态的只有 $1$ 个排列就不需要继续分了），我们要做的是把决策树的深度弄小。

没错这就是个IDDFS……先枚举深度，然后加一道比较显然的剪枝：如果当前分成的三份中最大的那份超过了剩余深度能够承受的最大大小，就停止搜索。加了这个就能很快跑出来了，发现深度为答案下界 $6(log_3720)$ 。

示例程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include"Bucharest.h"
#include<cstdio>
#include<vector>
#include<algorithm>
#define getl getLightest
#define geth getHeaviest
#define getm getMedian
#define getn getNextLightest
#define pb push_back
using namespace std;
const int maxn=10000;

struct data{
    int a[7],rk[7];data(int *A) {rk[0]=1e9;for (int i=1;i<=6;i++) a[i]=A[i],rk[a[i]]=i;}
    inline int Miner(int a,int b) {return rk[a]<rk[b]?a:b;}
    inline int getl(int A,int B,int C) {return Miner(Miner(A,B),C);}
    inline int Maxer(int a,int b) {return rk[a]>rk[b]?a:b;}
    inline int geth(int A,int B,int C) {return Maxer(Maxer(A,B),C);}
    inline int getm(int A,int B,int C){
        if (Miner(A,B)==B) swap(A,B);if (Miner(A,C)==C) swap(A,C);
        if (Miner(B,C)==C) swap(B,C);return B;
    }
    inline int getn(int A,int B,int C,int D,int ans=0){
        if (Maxer(A,D)==A) ans=Miner(A,ans);
        if (Maxer(B,D)==B) ans=Miner(B,ans);
        if (Maxer(C,D)==C) ans=Miner(C,ans);
        return ans?ans:getl(A,B,C);
    }
    inline int Query(int tp,int A,int B,int C,int D=0){
        if (tp==1) return getl(A,B,C);
        if (tp==2) return geth(A,B,C);
        if (tp==3) return getm(A,B,C);
        if (tp==4) return getn(A,B,C,D);
    }
};
int a[7];bool vis[7];vector<data> p[maxn+5];vector<data>::iterator it;
int lim,tp[maxn+5],A[maxn+5],B[maxn+5],C[maxn+5],D[maxn+5];

void Make(int st){
    if (st>6) {p[1].pb(data(a));return;}
    for (int i=1;i<=6;i++) if (!vis[i]) {a[st]=i;vis[i]=true;Make(st+1);vis[i]=false;}
}
inline bool check(int si,int dep) {while (si>1) dep--,si=(si+2)/3;return dep>=0;}
bool Dfs(int x,int dep){
    if (p[x].size()<=1) return true;if (dep>lim) return false;
    vector<data> &pa=p[x*3],&pb=p[x*3+1],&pc=p[x*3+2];
    for (int t=1;t<=4;t++)
        for (int a=1;a<=4;a++)
            for (int b=a+1;b<=5;b++)
                for (int c=b+1;c<=6;c++){
                    if (t==4){
                        for (int d=1;d<=6;d++){
                            if (d==a||d==b||d==c) continue;
                            tp[x]=t;A[x]=a;B[x]=b;C[x]=c;D[x]=d;pa.clear();pb.clear();pc.clear();
                            for (it=p[x].begin();it!=p[x].end();it++){
                                int now=(*it).Query(t,a,b,c,d);
                                if (now==a) pa.pb(*it);if (now==b) pb.pb(*it);if (now==c) pc.pb(*it);
                            }int MAX=max(max(pa.size(),pb.size()),pc.size());if (!check(MAX,lim-dep)) continue;
                            if (Dfs(x*3,dep+1)&&Dfs(x*3+1,dep+1)&&Dfs(x*3+2,dep+1)) return true;
                        }
                    } else{
                        tp[x]=t;A[x]=a;B[x]=b;C[x]=c;pa.clear();pb.clear();pc.clear();
                        for (it=p[x].begin();it!=p[x].end();it++){
                            int now=(*it).Query(t,a,b,c);
                            if (now==a) pa.pb(*it);if (now==b) pb.pb(*it);if (now==c) pc.pb(*it);
                        }int MAX=max(max(pa.size(),pb.size()),pc.size());if (!check(MAX,lim-dep)) continue;
                        if (Dfs(x*3,dep+1)&&Dfs(x*3+1,dep+1)&&Dfs(x*3+2,dep+1)) return true;
                    }
                }
    return false;
}
void init(int T) {Make(1);/*for (lim=1;!Dfs(1,1);lim++);*/lim=6;Dfs(1,1);}
data getans(int x){
    if (p[x].size()==1) return p[x][0];int now;
    if (tp[x]==1) now=getl(A[x],B[x],C[x]);if (tp[x]==2) now=geth(A[x],B[x],C[x]);
    if (tp[x]==3) now=getm(A[x],B[x],C[x]);if (tp[x]==4) now=getn(A[x],B[x],C[x],D[x]);
    if (now==A[x]) return getans(x*3);if (now==B[x]) return getans(x*3+1);if (now==C[x]) return getans(x*3+2);
}
void orderDolls() {answer(getans(1).a+1);}