【AtCoder Regular Contest 062 E】Building Cubes with AtCoDeer | Mrsrz's blog

枚举。

题目大意：

给定 $n$ 个面，每个面有数字，四个角上有颜色。一个面可以旋转，所以有 $4$ 种本质不同的方案。

现在问可以构成多少个本质不同的立方体。如果两个立方体能通过旋转同构则是相同的。

构成立方体要六个面，且每个角上的颜色要相等。

题解：

用 unsigned long long 可以把颜色的状态压缩起来。用 map 来计数。

我们可以枚举前、后两个面，这样所有角的颜色就确定了，每个面的状态就确定了。

然后直接乘法原理合并答案即可。

一个立方体在三对面中会被计算，每对被计算 $4$ 次，所以最后要除以 $12$。

注意如果出现四个角相等或对角相等的面，则计数时需要额外乘上这个面旋转后角相等的方案数。

时间复杂度 $O(n^2\log n)$。

Code：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef unsigned long long LL;
map<LL,int>c;
const int N=404;
struct zk{
    int a[4];
    inline zk(int A,int B,int C,int D){a[0]=A,a[1]=B,a[2]=C,a[3]=D;}
    inline zk(){}
    inline LL Hash(){
        LL r=0x3fffffffffffffff;
        for(int i=0;i<4;++i)
        r=min(r,((LL)a[i]<<48)|((LL)a[(i+1)&3]<<32)|((LL)a[(i+2)&3]<<16)|(a[(i+3)&3]));
        return r;
    }
    inline int check(){
        if(a[0]==a[1]&&a[1]==a[2]&&a[2]==a[3])return 4;
        if(a[0]==a[2]&&a[1]==a[3])return 2;
        return 1;
    }
}A[N];
inline istream&operator>>(istream&in,zk&a){in>>a.a[0]>>a.a[1]>>a.a[2]>>a.a[3];return in;}
int n;LL ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>A[i],++c[A[i].Hash()];
    for(int X=1;X<=n;++X)
    for(int X_=0;X_<4;++X_)
    for(int Y=X+1;Y<=n;++Y)
    for(int Y_=0;Y_<4;++Y_){
        zk H=zk(A[X].a[X_],A[X].a[(X_+1)&3],A[X].a[(X_+2)&3],A[X].a[(X_+3)&3]);
        zk T=zk(A[Y].a[Y_],A[Y].a[(Y_+1)&3],A[Y].a[(Y_+2)&3],A[Y].a[(Y_+3)&3]);
        --c[H.Hash()],--c[T.Hash()];
        zk L=zk(T.a[1],H.a[0],H.a[3],T.a[2]),R=zk(H.a[1],T.a[0],T.a[3],H.a[2]);
        zk U=zk(T.a[1],T.a[0],H.a[1],H.a[0]),D=zk(H.a[3],H.a[2],T.a[3],T.a[2]);
        LL r=1;
        r*=c[L.Hash()]--;
        r*=c[R.Hash()]--;
        r*=c[U.Hash()]--;
        r*=c[D.Hash()]--;
        ++c[L.Hash()],++c[R.Hash()],++c[U.Hash()],++c[D.Hash()];
        ++c[H.Hash()],++c[T.Hash()];
        r*=L.check()*R.check()*U.check()*D.check();
        ans+=r;
    }
    cout<<ans/12<<'\n';
    return 0;
}