POJ3349 Snowflake Snow Snowflakes(哈希)

题目链接

分析:

哈希竟然能这么用。检查两片雪花是否相同不难,但如果是直接暴力,定会超时。所以要求哈希值相同时再检查。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <ctime> using namespace std; const int maxn = +;
const int MOD_VAL = ; int sn[maxn][];
vector<int>hash[MOD_VAL]; bool check(int a, int b) { //检查两片是否相等
for(int i=; i<; i++) {
bool flag = true;
for(int j=; j<; j++) {
if(sn[a][j] !=sn[b][(i+j)%]) {
flag = false; break;
}
} if(flag == true) return true; flag = true;
for(int j=; j<; j++) {
if(sn[a][j] != sn[b][(i-j+)%]) {
flag = false; break;
}
} if(flag == true) return true;
} return false;
} int main() {
int n; bool flag = false; scanf("%d", &n);
for(int i=; i<n; i++) {
for(int j=; j<; j++) {
scanf("%d", &sn[i][j]);
}
} for(int i=; i<n; i++) {
int sum = ;
for(int j=; j<; j++) sum += sn[i][j];
int key = sum % MOD_VAL;
for(int j=; j<hash[key].size(); j++) {
//check
if(check(hash[key][j], i)) {
flag = true; break;
}
} if(flag) break; hash[key].push_back(i);
} if(flag) printf("Twin snowflakes found.\n");
else printf("No two snowflakes are alike.\n"); return ;
}
上一篇:HIVE:用外连接替代子查询


下一篇:Android-5 理解context