2 条题解

  • 3
    @ 2023-7-24 19:51:38

    根据题目描述,我们需要判断给定的雪花中是否存在两片形状相同的雪花。为了解决这个问题,我们可以使用哈希表来存储每片雪花的六元组,并逐一检查是否存在相同的六元组。

    以下是一个可能的解决方案的示例代码:

    #include <iostream>
    #include <unordered_set>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    bool checkDuplicateSnowflakes(const vector<vector<int>>& snowflakes) {
        unordered_set<string> snowflakeSet;
    
        for (const auto& snowflake : snowflakes) {
            // 将雪花的六元组转换为字符串作为哈希表的键
            string key = "";
            for (int length : snowflake) {
                key += to_string(length) + " ";
            }
    
            if (snowflakeSet.count(key) > 0) {
                return true;
            } else {
                // 将六元组添加到哈希表中
                snowflakeSet.insert(key);
            }
        }
    
        return false;
    }
    
    int main() {
        int N;
        cin >> N;
    
        vector<vector<int>> snowflakes;
        for (int i = 0; i < N; i++) {
            vector<int> snowflake(6);
            for (int j = 0; j < 6; j++) {
                cin >> snowflake[j];
            }
            snowflakes.push_back(snowflake);
        }
    
        // 检查是否存在相同的雪花形状
        bool hasDuplicate = checkDuplicateSnowflakes(snowflakes);
    
        // 输出结果
        if (hasDuplicate) {
            cout << "Twin snowflakes found." << endl;
        } else {
            cout << "No two snowflakes are alike." << endl;
        }
    
        return 0;
    }
    
  • 1
    @ 2023-7-3 18:26:51

    image

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N=1e5+10,P=92083;
    int n,snow[N][6];
    vector<int> head[P];
    int get_hash( int *a )//对雪花求和求积,作为hash值 
    {
        int res1=0,res2=1;
        for ( int i=0; i<6; i++ )
            res1=(res1+a[i])%P,res2=(ll)res2*a[i]%P;
        return (res1+res2)%P;
    }
    bool check( int *a,int *b )//判断两片雪花是否相同 
    {
        for ( int i=0; i<6; i++ )
         for ( int j=0; j<6; j++ )
         {
            bool flag=1;
            for ( int k=0; k<6; k++ )//两个雪花方向上相同和相反都判一遍 
                if ( a[(i+k)%6]!=b[(j+k)%6] ) flag=0;
            if ( flag ) return 1;
            flag=1;
            for ( int k=0; k<6; k++ )
                if ( a[(i+k)%6]!=b[(j-k+6)%6] ) flag=0;
            if ( flag ) return 1;
         }
        return 0;
    }
    bool insert( int j,int *a )//把新的雪花插入hash表中 
    {
        int hval=get_hash(a);
        for (int &i:head[hval]) 
            if ( check(snow[i],a) ) return 1;//判重 
    	head[hval].push_back(j);//插入hash表中 
        return 0;
    }
    int main()
    {
        scanf( "%d",&n );
        for (int j=1;j<=n;++j)
        {
            for ( int i=0; i<6; i++ )
                scanf( "%d",&snow[j][i] );
            if ( insert(j,snow[j]) ) { printf( "Twin snowflakes found.\n" ); return 0; }
        }
        printf( "No two snowflakes are alike." );
    }
    
    
    
    
    • @ 2023-7-15 21:01:13

      假如两片雪花分别是(1,2,3,4,5,6),(1,3,2,4,5,6),它们的Hash值一样,但并不一样啊

    • @ 2023-7-15 22:05:11

      @ 没事,没看到判重

  • 1

信息

ID
237
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
109
已通过
35
上传者