题目描述

blablabla

样例

blablabla

算法1

这个题目我们可以将具有相同特征的雪花保存在一个邻接表中。

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

blablabla

时间复杂度分析：blablabla

C++ 代码

#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");
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla