题目描述
给出一片雪花六个角的值(顺时针or逆时针),问我们是否会有两片相同的雪花
样例
2
1 2 3 4 5 6
4 3 2 1 6 5
Twin snowflakes found.
最小表示法+set
蒟蒻实在想不到咋hash,直接暴力上了最小表示法
1.得到顺时针的最小表示法
2.得到逆时针的最小表示法
3.判断完这俩个在set内直接得到雪花是否重复,不重复的情形下,把新得到的两个最小表示法塞进去
时间复杂度
$O(n+nlogn)$
复杂度不咋会算,大概率算错了
C++ 代码
#include<bits/stdc++.h>
#include<unordered_map>
#define lowbit(x) x&(-x)
#define ls rt << 1
#define rs rt << 1|1
#define lson ls,l,m
#define rson rs,m+1,r
using namespace std;
typedef long long ll;
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;
struct node{
int a,b,c,d,e,f;
node(){}
node(int a,int b,int c,int d,int e,int f):a(a),b(b),c(c),d(d),e(e),f(f){}
void print(){
printf("%d %d %d %d %d %d\n",a,b,c,d,e,f);
}
friend bool operator < (node x,node y){
if(x.a != y.a) return x.a < y.a;
if(x.b != y.b) return x.b < y.b;
if(x.c != y.c) return x.c < y.c;
if(x.d != y.d) return x.d < y.d;
if(x.e != y.e) return x.e < y.e;
return x.f < y.f;
}
};
set <node> s;
int c[6];
inline node get(){
int k = 0,i = 0,j = 1;
while(k < 6 && i < 6 && j < 6){
if(c[(i+k)%6] == c[(j+k)%6]) k++;
else{
if(c[(i+k)%6] > c[(j+k)%6]) i = i+k+1;
else j = j+k+1;
if(i == j) i++;
k = 0;
}
}
int Min = min(i,j);
return node(c[Min],c[(Min+1)%6],c[(Min+2)%6],c[(Min+3)%6],c[(Min+4)%6],c[(Min+5)%6]);
}
inline void reverse(){
int t,l = 0,r = 5;
while(l < r){
t = c[l];
c[l] = c[r];
c[r] = t;
l++;
r--;
}
return ;
}
inline bool check(node p,node q){
if(s.find(p) != s.end()) return 1;
if(s.find(q) != s.end()) return 1;
return 0;
}
int main(){
int n;
bool f = 0;
scanf("%d",&n);
for(int i = 1;i <= n;++i){
for(int j = 0;j < 6;++j) scanf("%d",&c[j]);
if(f) continue;
node p = get();
reverse();
node q = get();
if(check(p,q)){
f = 1;
continue;
}
s.insert(p);
s.insert(q);
}
printf("%s\n",f ?"Twin snowflakes found." :"No two snowflakes are alike.");
return 0;
}