当前位置: 代码迷 >> 综合 >> 【暴力】AtCoder2142 Building Cubes with AtCoDeer
  详细解决方案

【暴力】AtCoder2142 Building Cubes with AtCoDeer

热度:36   发布时间:2023-09-27 07:14:58.0

分析:

给出N个正方形,每个正方形正面的四个角各有一种颜色,要求组成正方体的方案数(由于每个正方形中间都有一个数字,所以方向不同也算不同方案)。

也就是说,两种方案视为相同,当且仅当一个正方体可以通过各种旋转得到另一个。


分析:

考虑到N非常小(400)

有一个很显然的性质:只要确定了正方体一组正对的面的各个角的颜色,就可以唯一确定整个正方体。

所以。。。不就是爆枚么。。。爆枚一个正方形,再爆枚另一个以及相对方向,作为其对面的,然后一个map存方案即可。

注意一下,因为正方形可以旋转,所以存入map时,要把旋转4次的结果都插入进去。去重的时候也要将旋转之后的各个方案都去掉。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
ll ans;
int n;
struct node{int a1,a2,a3,a4;node() {}node(int aa1,int aa2,int aa3,int aa4):a1(aa1),a2(aa2),a3(aa3),a4(aa4) {}bool operator <(const node &a) const {if(a1!=a.a1)return a1<a.a1;if(a2!=a.a2)return a2<a.a2;if(a3!=a.a3)return a3<a.a3;return a4<a.a4;}bool operator ==(const node &a) const{if(a1==a.a1&&a2==a.a2&&a3==a.a3&&a4==a.a4)return 1;return 0;}
}t[MAXN];
map<node,ll> used;
void solve(int b1,int b2,int b3,int b4){used[node(b1,b2,b3,b4)]++;
}
ll check(node x,node y){ll res=0;if(x==y)res++;int tx=y.a1;y.a1=y.a2;y.a2=y.a3;y.a3=y.a4;y.a4=tx;if(x==y)res++;tx=y.a1;y.a1=y.a2;y.a2=y.a3;y.a3=y.a4;y.a4=tx;if(x==y)res++;tx=y.a1;y.a1=y.a2;y.a2=y.a3;y.a3=y.a4;y.a4=tx;if(x==y)res++;return res;
}   
void count(int b1,int b2,int b3,int b4,int b5,int b6,int b7,int b8){//PF("{%d %d %d %d %d %d %d %d}\n",b1,b2,b3,b4,b5,b6,b7,b8);node x1=node(b1,b2,b6,b5);node x2=node(b2,b3,b7,b6);node x3=node(b3,b4,b8,b7);node x4=node(b4,b1,b5,b8);node sp1=node(b4,b3,b2,b1);node sp2=node(b5,b6,b7,b8);ll res1=used[x1];ll res2=used[x2];ll res3=used[x3];ll res4=used[x4];res1=res1-check(sp1,x1)-check(sp2,x1);res2=res2-check(sp1,x2)-check(sp2,x2)-check(x1,x2);res3=res3-check(sp1,x3)-check(sp2,x3)-check(x1,x3)-check(x2,x3);res4=res4-check(sp1,x4)-check(sp2,x4)-check(x1,x4)-check(x2,x4)-check(x3,x4);ans+=res1*res2*res3*res4;//PF("{%lld %lld %lld %lld %lld}\n",used[x1],res1,check(sp1,x1),check(sp2,x1),res4);
}
int main(){SF("%d",&n);for(int i=1;i<=n;i++){SF("%d%d%d%d",&t[i].a1,&t[i].a2,&t[i].a3,&t[i].a4);solve(t[i].a4,t[i].a3,t[i].a2,t[i].a1);solve(t[i].a3,t[i].a2,t[i].a1,t[i].a4);solve(t[i].a2,t[i].a1,t[i].a4,t[i].a3);solve(t[i].a1,t[i].a4,t[i].a3,t[i].a2);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){count(t[i].a1,t[i].a2,t[i].a3,t[i].a4,t[j].a4,t[j].a3,t[j].a2,t[j].a1); count(t[i].a1,t[i].a2,t[i].a3,t[i].a4,t[j].a3,t[j].a2,t[j].a1,t[j].a4); count(t[i].a1,t[i].a2,t[i].a3,t[i].a4,t[j].a2,t[j].a1,t[j].a4,t[j].a3); count(t[i].a1,t[i].a2,t[i].a3,t[i].a4,t[j].a1,t[j].a4,t[j].a3,t[j].a2); }PF("%lld",ans/3ll);
}
  相关解决方案