第一次用hash解题。 这道题早就想A了，只是觉得挺难，便一直放下。今天本想下定决心自己做出来的，没想到自己写的代码一直WA，相当恼人。最后参考了网友的程序，虽要3454MS，但总算也过了。 解决此题的关键有二： 1. 构造hash表，应能想到hash表项存储的是雪花数组下标。其实hash表项设定为vector挺好用的，当hash表项存储的元素增加时，直接push_back即可，vector这个动态数组很好用; 2. 判断两个雪花是否相同，注意到顺时针和逆时针即可。 嗯，好了，上代码，你们看吧，注释挺详细的了。 #include <cstdio> #include <cstdlib> #include <vector> #include <iostream> using namespace std; const int MAX_SIZE = 100005; //最大的雪花数 const int MOD_VAL = 90001; //hash函数，取余的数 int snow[MAX_SIZE][6]; //存储雪花信息 vector<int> hash[MOD_VAL]; //hash表，表中存储的是snow数组的下标 /*判断雪花a与雪花b是否同样 *输入：两个雪花在snow数组的下标 *输出：true or false */ bool isSame(int a, int b) { for(int i=0;i<6;i++) { if(/*顺时针方向*/ (snow[a][0] == snow[b][i] && snow[a][1] == snow[b][(i+1)%6] && snow[a][2] == snow[b][(i+2)%6] && snow[a][3] == snow[b][(i+3)%6] && snow[a][4] == snow[b][(i+4)%6] && snow[a][5] == snow[b][(i+5)%6]) || /*逆时针方向*/ (snow[a][0] == snow[b][i] && snow[a][1] == snow[b][(i+5)%6] && snow[a][2] == snow[b][(i+4)%6] && snow[a][3] == snow[b][(i+3)%6] && snow[a][4] == snow[b][(i+2)%6] && snow[a][5] == snow[b][(i+1)%6]) ) return true; } return false; } int main() { /*处理输入*/ int n; scanf("%d", &n); for(int i = 0; i < n; i++) { for(int j = 0; j < 6; j++) { scanf("%d", &snow[i][j]); } } /*分别处理这n个雪花，判断有没两个雪花是相同的*/ int sum, key; for(int i = 0; i < n; i++) { /*求出雪花六个花瓣的和*/ sum = 0; for(int j = 0; j < 6; j++) { sum += snow[i][j]; } key = sum % MOD_VAL; //求出key /*判断在hash表中hash[key]存储的雪花是否与雪花i相同*/ for(vector<int>::size_type j = 0; j < hash[key].size(); j++) { /*若相同，则直接输出，并结束程序*/ if(isSame(hash[key][j], i)) { printf("%s/n", "Twin snowflakes found."); exit(0); } } /*若key相同的雪花没有一个与雪花i相同*/ hash[key].push_back(i); } /*若都不相同*/ printf("%s/n", "No two snowflakes are alike."); return 0; }
