137. 雪花雪花雪花(hash)

迷南。 2021-12-13 04:42 243阅读 0赞

### 题目描述： ###

有N片雪花，每片雪花由六个角组成，每个角都有长度。

第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6

。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

例如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片雪花中是否存在两片形状相同的雪花。  
输入格式

第一行输入一个整数N，代表雪花的数量。

接下来N行，每行描述一片雪花。

每行包含6个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。

同行数值之间，用空格隔开。  
输出格式

如果不存在两片形状相同的雪花，则输出：

No two snowflakes are alike.

如果存在两片形状相同的雪花，则输出：

Twin snowflakes found.  
数据范围

1≤n≤100000  
,  
0≤ai,j<10000000

输入样例：

2  
1 2 3 4 5 6  
4 3 2 1 6 5

输出样例：

Twin snowflakes found.

##### 分析： #####

这个题目我们可以将具有相同特征的雪花保存在一个邻接表中。  
那么这道题目，我们可以采用雪花长度之和+雪花长度之积 并取于p。作为每个雪花的特征值。然后比较相同特征值的雪花是否完全一样即可。  
在比较是否完全一样的时候，一定不要排序之后再比较。  
看这组数据：  
2  
1 2 3 4 5 6  
4 2 3 1 6 5  
可以得出排序之后再比较的思想是错误的。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    #define p 99991
    typedef long long ll;
    
    int n;
    ll a[100100][8];
    vector<ll> Q[99993];
    
    int euqul(int x,int y)
    {
        int flag = 0;
        for(int i = 0; i <= 5; i ++)
        {
            int k,j;
            for( k = 0,j = 0; k < 6; k ++,j ++)
            {
                if(a[x][k] != a[y][(j + i)%6])
                  break;
            }
            if(k == 6) return 1;
        }
        for(int i = 0;i <= 5; i ++)
        {
            int k ,j;
            for(k = 0,j = 5; k < 6; k ++,j --)
            {
                if(a[x][k] != a[y][(j + i)%6])
                    break;
            }
            if(k == 6) return 1;
        }
        return 0;
    }
    
    int main()
    {
        scanf("%d",&n);
        int mark = 0;
        for(int i = 1; i <= n; i ++)
        {
            ll s = 0,s1 = 1;
            for(int j = 0; j < 6; j ++)
            {
                scanf("%lld",&a[i][j]);
                s = s + (ll)a[i][j];
                s1 *= (ll)a[i][j];
                s %= p;
                s1 %= p;
            }
            if(mark == 1)
                continue;
            s += s1;
            s1 = s % (ll)p;
            for(int j = 0; j < Q[s1].size(); j ++)
                if(euqul(i,Q[s1][j]))
                {
                    mark = 1;
                    break;
                }
            if(mark == 0)
                Q[s1].push_back(i);
        }
        if(mark == 1)
            printf("Twin snowflakes found.\n");
        else
            printf("No two snowflakes are alike.\n");
    }