题目描述
看题
思路
由于是和前面的判断是否出现过,可以用哈希表记录
map 时间复杂度就是nlog级别的
unordered_map 快则n 慢就在乘以一个n
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
int a[N][12], b[N][12];
unordered_map<string,int> ump;
int get_min(int s[])
{
int i =0, j = 1;
while(i < 6 && j < 6){
int k = 0;
while(k < 6 && s[i+k] == s[j+k]) k++;
if(k == 6) break;
if(s[i+k]> s[j+k]) i += k +1;
else j += k + 1;
if(i == j) j++;
}
int k =min(i, j);
return k;
}
string get_sum(int s[], int x)
{
string str = "";
for(int i = x; i < x + 6; i++){
str += s[i] + '0';
}
return str;
}
int main()
{
cin >> n;
for(int j = 0; j < n; j++){
for(int i = 0; i < 6; i++){
cin >> a[j][i];
a[j][i + 6] = a[j][i];
b[j][i + 6] = b[j][i] = a[j][i];
}
reverse(b[j], b[j] + 12);
}
//cout << b[0][0] << endl;
for(int i = 0; i < n; i++){
int x = get_min(a[i]);
int y = get_min(b[i]);
//cout << x << endl;
string sum1 = get_sum(a[i], x);
if(ump.count(sum1)){
cout << "Twin snowflakes found." << endl;
return 0;
}
string sum2 = get_sum(b[i], y);
if(ump.count(sum2)){
cout << "Twin snowflakes found." << endl;
return 0;
}
ump[sum1]++;
ump[sum2]++;
}
cout << "No two snowflakes are alike." << endl;
return 0;
}