2 条题解
-
3
根据题目描述,我们需要判断给定的雪花中是否存在两片形状相同的雪花。为了解决这个问题,我们可以使用哈希表来存储每片雪花的六元组,并逐一检查是否存在相同的六元组。
以下是一个可能的解决方案的示例代码:
#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
#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." ); }
- 1
信息
- ID
- 237
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 109
- 已通过
- 35
- 上传者