題意:
雪花有六條棱,每條棱對應一個數,要求在一組雪花中看能否尋找到所有棱對應相同的雪花(棱有順序要求)。
要點:
poj1741、剛自學了一下hash,這題剛上手有點思路但自己實在也寫不出來,看了網上的代碼覺得還是很簡單的。首先這題只要用取余hash即可,將每條棱求和進行取余hash,然后用m[sum]記錄有幾個雪花sum相同,然后用snow[sum][m[sum]]存儲這個雪花即可,還是比較簡單的,這題的key值要設成一個比較大的素數,同時也要兼顧一下數組的范圍,所以也不能太大。
15448052 | Seasonal | 3349 | Accepted | 27620K | 3000MS | C++ | 912B | 2016-04-28 19:28:34 |
#include<cstdio>
#include<algorithm>
#define maxn 10000
#define key 9997
using namespace std;
struct node
{int f[7];
};
int m[maxn];//存儲sum相同的雪花個數
node snow[maxn][100];bool cmp(node a, node b)
{sort(a.f, a.f + 6); //先排序再比較即可sort(b.f, b.f + 6);for (int i = 0; i < 6; i++){if (a.f[i] != b.f[i])return false;}return true;
}
int main()
{int n,i,j;while (scanf("%d", &n) != EOF){memset(m, 0, sizeof(m));bool ok = false;while(n--){int sum = 0;node temp;for (i = 0; i < 6; i++){scanf("%d", &temp.f[i]);sum = (sum + temp.f[i]) % key;//求和進行簡單的取余hash,這里要進行取余操作否則數組會過大}if (!ok){for (i = 0; i < m[sum]; i++){if (cmp(temp, snow[sum][i])){ok = true;break;}}snow[sum][m[sum]] = temp; //snow記錄總和為sum中的第m[sum]個關鍵字m[sum]++;}}if (ok)printf("Twin snowflakes found.\n");elseprintf("No two snowflakes are alike.\n");}return 0;
}