【arc062e】Building Cubes with AtCoDeer

Description

STL有n块瓷砖，编号从1到n，并且将这个编号写在瓷砖的正中央；

瓷砖的四个角上分别有四种颜色（可能相等可能不相等），并且用C_i,0，C_i,1，C_i,2，C_i,3分别表示左上、右上、右下、左下的颜色。颜色有1000种，编号从0到999。

现在STL想知道，从这n块瓷砖中选出不同的6块，能围成多少本质不同的合法的立方体。

一个立方体被称为合法的，当且仅当瓷砖有编号的一侧在外面，并且立方体的每个顶点处的三个颜色相同。

注意，由于瓷砖的中间是写着编号的，因此将一个瓷砖旋转90度之后，这个瓷砖会发生变化，也就是说一块瓷砖可以被用作四个方向（哪怕旋转后四个角的颜色对应相等）。

两个立方体被称作是本质相同的，当且仅当存在在空间中旋转一个立方体的方式，使其和第二个立方体一模一样（包括每面瓷砖上编号的方向）。

Solution

n最大为400，显然可以暴力解决。

我们可以发现，当一个立方体中，只要确定了任意两个相对的面，就可唯一确定整个立方体。

因此我们枚举相对两面编号及编号方向，用map储存瓷砖，计算方案即可。

ps：由于正方形可旋转，因此存入map时，要将旋转4次的结果都存入map中。

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 using namespace std;

 #define hash func

 typedef long long ll;

 int n,c[][];

 ll ans=,h[];

 map<ll,int>mp;

 ll hash(ll a,ll b,ll c,ll d){

     return a<<|b<<|c<<|d;

 }

 void add(ll x,int k){

     for(int i=;i;x=x>>|(x&)<<,i--)

         mp[x]+=k;

     return;

 }

 int main(){

     mp.clear();

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d%d%d%d",c[i]+,c[i]+,c[i]+,c[i]+);

         h[i]=hash(c[i][],c[i][],c[i][],c[i][]);

         add(h[i],);

     }

     for(int i=;i<n-;i++){

         add(h[i],-);

         for(int j=i+;j<=n;j++){

             add(h[j],-);

             for(int k=;k<;k++){

                 ll a[];

                 a[]=hash(c[i][],c[i][],c[j][(k+)%],c[j][k]);

                 a[]=hash(c[i][],c[i][],c[j][(k+)%],c[j][(k+)%]);

                 a[]=hash(c[i][],c[i][],c[j][(k+)%],c[j][(k+)%]);

                 a[]=hash(c[i][],c[i][],c[j][k],c[j][(k+)%]);

                 if(mp[a[]]==||mp[a[]]==||mp[a[]]==||mp[a[]]==)

                     continue;

                 ll res=;

                 for(int l=;l<;l++){

                     res*=mp[a[l]];

                     add(a[l],-);

                 }

                 ans+=res;

                 for(int l=;l<;l++)

                     add(a[l],);

             }

             add(h[j],);

         }

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

【arc062e】Building Cubes with AtCoDeer

Description

Solution

Code

最新文章

热门文章