AcWing 137. 雪花雪花雪花    原题链接    困难

作者： 作者的头像   这个显卡不太冷 ,  2019-02-27 14:54:34 ,  所有人可见 ,  阅读 2108

4


2

最小表示法 + 字符串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.";
}

10 评论

用户头像
寂封.   2023-03-17 21:21         踩      回复

如果六个角度都相同的话，正向的哈希值存进去之后再判断反向的哈希值的时候不就误判了吗

用户头像
寂封.   2023-03-17 21:22         踩      回复

我认为的处理方式是要对正反两次哈希值判断一下是否相等

用户头像
汐_zh   2个月前    回复了 寂封. 的评论         踩      回复

是的，还需做一次判断

用户头像
56475540@qq.com   2021-08-08 14:54         踩      回复

为什么正向做一遍以后还必须反向做一遍？不做答案还是错的

用户头像
霹雳暴龙战士   2022-01-13 22:03         踩      回复

可能是为了减少哈希冲突？我也不太清楚

用户头像
汐_zh   2个月前         踩      回复

因为是顺时针和逆时针两个方向的旋转，所以还得反向做一遍

用户头像
WestTree   2019-10-18 15:22         踩      回复

老哥map的插入、查找的时间复杂度都是log级别的吧。所以执行n次插入和查找的时间复杂度上界应该是NlogN吧。

用户头像
这个显卡不太冷   2019-10-23 17:09         踩      回复

unordered_map 是哈希表，操作都是o(1)的

用户头像
WestTree   2019-10-23 17:30    回复了 这个显卡不太冷 的评论         踩      回复

谢谢

用户头像
羽笙   2019-05-30 20:24         踩      回复

大佬，我直接用字符串正反最小表示 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; 
}