当前位置: 代码迷 >> 综合 >> Snowflake Snow Snowflakes
  详细解决方案

Snowflake Snow Snowflakes

热度:89   发布时间:2024-01-19 08:25:20.0

题目:http://poj.org/problem?id=3349

给你N串数字,每串由六个数字组成,让你求这其中有没有相似的六个数字。比如:
1 2 3 4 5 6
3 4 5 6 1 2
5 4 3 2 1 6
都是相似的。因为范围比较大,可以用hash记录。记录时将和相同的的六个数字记录在一起可以减少时间复杂度。最后对vector进行遍历,如果size大于1说明有可能有相似的。将有可能的拿出来进行比较就行了。
这道题做的时候是卡着边过的,用G++会TLE,用C++就能AC。

#include <iostream>
#include <vector>
#include <cstdio>
#define NUM 100000
#define LONG 10000000
using namespace std;typedef struct node{int bian[6];
}snow[NUM];vector<node>hs[NUM];void hash_(node tt){int no = 0;for(int i = 0; i < 6; i++){no += tt.bian[i];}no = no % NUM;hs[no].push_back(tt);
}bool cmp(node s1, node s2){for(int i = 0; i < 6; i++){if(s1.bian[i] == s2.bian[0] && s1.bian[(i+1)%6] == s2.bian[1] && s1.bian[(i+2)%6] == s2.bian[2] \&& s1.bian[(i+3)%6] == s2.bian[3] && s1.bian[(i+4)%6] == s2.bian[4] && s1.bian[(i+5)%6] == s2.bian[5]){return true;}if(s1.bian[i] == s2.bian[5] && s1.bian[(i+1)%6] == s2.bian[4] && s1.bian[(i+2)%6] == s2.bian[3] \&& s1.bian[(i+3)%6] == s2.bian[2] && s1.bian[(i+4)%6] == s2.bian[1] && s1.bian[(i+5)%6] == s2.bian[0]){return true;}}return false;
}int main(){ios::sync_with_stdio(false);int n;node tt;scanf("%d", &n);for(int i = 0; i < n; i++){for(int j = 0; j < 6; j++){scanf("%d", &tt.bian[j]);}hash_(tt);}for(int i = 0; i < NUM; i++){if(hs[i].size() <= 1){continue;}for(int j = 0; j < hs[i].size(); j++){for(int k = j + 1; k < hs[i].size(); k++){if(cmp(hs[i][j], hs[i][k])){printf("Twin snowflakes found.\n");return 0;}}}}printf("No two snowflakes are alike.\n");return 0;
}