题目描述
本来map那里用的二分查找,TLE了,换map直接快一个档次
ai,1,ai,2,…,ai,6 和 ai,2,ai,3,…,ai,6,ai,1 就是形状相同的雪花。
ai,1,ai,2,…,ai,6 和 ai,6,ai,5,…,ai,1 也是形状相同的雪花。
我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。
求这 N 片雪花中是否存在两片形状相同的雪花。
样例
2
1 2 3 4 5 6
4 3 2 1 6 5
Twin snowflakes found.
(hash) $O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
struct node{
int w[6];
friend bool operator<(node a, node b) // 按字典序比较大小
{
for (int i = 0; i < 6; i ++ )
if (a.w[i] != b.w[i]) return a.w[i] < b.w[i];
return false;
}
};
map <node, bool> m;
node f(node a) // 找出所有变换中字典序最小的
{
node res = a;
for (int i = 1; i < 6; i ++ )
{
int temp = a.w[0];
for (int j = 1; j < 6; j ++ )
a.w[j - 1] = a.w[j];
a.w[5] = temp;
if (a < res) res = a;
}
for (int i = 0; i < 3; i ++ )
swap(a.w[i], a.w[5 - i]);
if (a < res) res = a;
for (int i = 1; i < 6; i ++ )
{
int temp = a.w[0];
for (int j = 1; j < 6; j ++ )
a.w[j - 1] = a.w[j];
a.w[5] = temp;
if (a < res) res = a;
}
return res;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
node a;
for (int i = 0; i < 6; i ++ )
scanf("%d", &a.w[i]);
a = f(a);
if (m.count(a)){
puts("Twin snowflakes found."); // 如果之前出现过
return 0;
}
m[a] = true;
}
puts("No two snowflakes are alike.");
}