题解：P10467 [CCC 2007] Snowflake Snow Snowflakes

Stars_visitor_tyw · 2024-05-22 13:24:39 · 题解

P10467 [CCC 2007] Snowflake Snow Snowflakes 题解

分析

排序不是正解。我们采用单哈希，这样不容易超时。

给每个序列按照处理字符串哈希值的方式处理数列的哈希值，一边输入一边判断，前后分别找，若这个数列的两个哈希值都有同一片雪花对应上，输出 Twin snowflakes found.。最后若程序还没有结束，输出 No two snowflakes are alike.。

代码

#include<bits/stdc++.h>
using namespace std;
long long a[7];
map<long long,long long> mp;
long long hs, pw, hs1;
const long long base=131, base1=191;
void hadsh(long long pos)
{
    hs=hs1=0;
    for(register int i=1;i<=6;i++)
    {
        hs=hs*base+a[pos];
//      hs1=hs1*base1+a[pos];
        pw=pw*base;
        if(pos!=6)
        {
            pos=pos+1;
        }
        else pos=1;
    }
}
void hadsh1(long long pos)
{
    hs=hs1=0;
    for(register long long i=1;i<=6;i++)
    {
        hs=hs*base+a[pos];
        pw=pw*base;
//      hs1=hs1*base1+a[pos];
        if(pos!=1)
        {
            pos-=1;
        }
        else pos=6;
    }
}
void work(long long x)
{
    hadsh(x);
    if(mp[hs])
    {
        cout<<"Twin snowflakes found.";
        exit(0);
    }
    mp[hs]=1;
}
void work1(long long x)
{
    hadsh1(x);
    if(mp[hs])
    {
        cout<<"Twin snowflakes found.";
        exit(0);
    }
    mp[hs]=1;
}
int n;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(register long long i=1;i<=n;i++)
    {
        for(register long long j=1;j<=6;j++)
        {
            cin>>a[j];
        }
        for(register long long j=1;j<=6;j++)
        {
            work(j),work1(j);
        }
    }
    cout<<"No two snowflakes are alike.";
}