最小表示法 + 字符串hash
把每个雪花的正反求一次最小表示法。然后字符串hash就可以了.....
时间复杂度O(N),空间复杂度O(N)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull maxn = 1e7 + 9;
int n;
ull a[20],b[20];
int f(ull *t)
{
int i = 1,j = 2,k;
while(i <= 6 && j <= 6)
{
for(k = 0; k <= 6 && t[i + k] == t[j + k];k++);
if(k == 6) break;
if(t[i + k] > t[j + k])
{
i = i + k + 1;
if(i == j) i++;
}
else
{
j = j + k + 1;
if(i == j) j++;
}
}
return min(i,j);
}
int main()
{
unordered_map<ull,int> ump;
cin >> n;
for(int t = 1; t <= n; t++)
{
ull hash = 0;
for(int j = 1, k = 6; j <= 6; j++, k--) cin >> a[j], b[k] = a[j];
for(int j = 7; j <= 12; j++) a[j] = a[j - 6],b[j] = b[j - 6];
int k = f(a);
for(int j = 0; j < 6; j++) hash =hash*maxn+a[k + j];
if(ump.find(hash) == ump.end()) ump[hash] = 1;
else
{
cout<<"Twin snowflakes found.";
return 0 ;
}
k = f(b);hash = 0;
for(int j = 0; j < 6; j++) hash =hash*maxn+b[k + j];
if(ump.find(hash) == ump.end()) ump[hash] = 1;
else
{
cout << "Twin snowflakes found.";
return 0;
}
}
cout<<"No two snowflakes are alike.";
}
如果六个角度都相同的话，正向的哈希值存进去之后再判断反向的哈希值的时候不就误判了吗
我认为的处理方式是要对正反两次哈希值判断一下是否相等
是的，还需做一次判断
为什么正向做一遍以后还必须反向做一遍？不做答案还是错的
可能是为了减少哈希冲突？我也不太清楚
因为是顺时针和逆时针两个方向的旋转，所以还得反向做一遍
老哥map的插入、查找的时间复杂度都是log级别的吧。所以执行n次插入和查找的时间复杂度上界应该是NlogN吧。
unordered_map 是哈希表，操作都是o(1)的
谢谢
大佬，我直接用字符串正反最小表示 T了 求助%>_<%
#include<iostream> #include<cstdio> #include<tr1/unordered_map> #include<set> #include<cmath> #include<queue> #include<cstring> #include<algorithm> #include<stack> using namespace std; using namespace tr1; typedef long long ll; const int N=200005,inf=0x3f3f3f3f; int n,len; string s1,s2; unordered_map<string,bool> m1; int get_min(){ len=s1.size(); int i=0,j=1,k=0; while(i<len&&j<len){ for(k=0;k<len&&s2[i+k]==s2[j+k];k++); //cout<<s2[i+k]<<" "<<s2[j+k]<<endl; if(k==len)return min(i,j); if(s2[i+k]>s2[k+j]){ i=i+k+1; if(i==j)i++; } else{ j=j+k+1; if(j==i)j++; } } return min(i,j); } void my_reverse(){ int num=s2.size()-1; string want; while(1){ string ps; while(s2[num]!=' '&&num>=0)ps+=s2[num],num--; reverse(ps.begin(),ps.end()); want+=ps; want+=' '; //cout<<want<<endl; num--; if(num<0)break; } s2=want; } int main(){ freopen("123.txt","r",stdin); cin>>n; getchar(); while(n--){ getline(cin,s1,'\n'); s1+=' '; s2=s1+s1; // cout<<s2<<endl; int minmark=get_min(); for(int i=0;i<len;i++)s1[i]=s2[i+minmark]; if(m1[s1]==1){ printf("Twin snowflakes found."); return 0; } // cout<<s1<<endl; m1[s1]=1; my_reverse(); minmark=get_min(); for(int i=0;i<len;i++)s1[i]=s2[i+minmark]; if(m1[s1]==1){ printf("Twin snowflakes found."); return 0; } // cout<<s1<<endl; m1[s1]=1; } printf("No two snowflakes are alike."); return 0; }