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

POJ 3349 Snowflake Snow Snowflakes hash表

热度:44   发布时间:2024-01-13 18:12:10.0

题目大意是给出n组序列,判断其中是否有同构的

同构的定义是,若一个序列中,从某个位置往左读,到头后从最后边接着往左读到起点,或者同理往右读,能够跟另一个序列一样,就表示两个序列是同构的。

那么,由于n是巨大的,常用的做法就是哈希表了

将序列映射成某个值,然后判断。

由于序列中存在一些较大的值,使得哈希的难度增大,这里我们采用的方法是,先使用一个比较容易想出来的哈希操作,然后对于哈希值相同的序列,一同放入这个值下,这里我们用到的是链表。

比较好想的hash就是求和了,然后mod一个质数,这个质数可以自己来定,但最好不要很小。在实际测试中,质数为9997和100007的效率是相差很少的。

然后对于每个哈希值下的所有序列,互相比较,看其是否相同。

另外,不得不说这道题的输入量是巨大的,只好用getchar()来增加速度。

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100007
#define INF 1000000000
#define eps 1e-7
using namespace std;
struct node
{int v, next;
}edge[100005];
int head[MAXN];
const int M = MAXN;
int a[100005][6], e = 0;
void insert(int u, int v)
{edge[e].v = v;edge[e].next = head[u];head[u] = e++;
}
bool cmp(int x, int y)
{int i, j;for(i = 0; i < 6; i++){if(a[x][0] == a[y][i]){for(j = 1; j < 6; j++)if(a[x][j] != a[y][(i + j) % 6])break;if(j == 6) return true;for(j = 1; j < 6; j++)if(a[x][6 - j] != a[y][(i + j) % 6])break;if(j == 6) return true;}}return false;
}
bool solve()
{for(int i = 0; i < M; i++)for(int j = head[i]; j != -1; j = edge[j].next)for(int k = edge[j].next; k != -1; k = edge[k].next)if(cmp(j, k)) return true;return false;
}
int in()
{int flag = 1;char ch;int a = 0;while((ch = getchar()) == ' ' || ch == '\n');if(ch == '-') flag = -1;elsea += ch - '0';while((ch = getchar()) != ' ' && ch != '\n'){a *= 10;a += ch - '0';}return flag * a;
}
int main()
{int n;memset(head, -1, sizeof(head));scanf("%d", &n);for(int i = 0; i < n; i++){int sum = 0;for(int j = 0; j < 6; j++){a[i][j] = in();sum += a[i][j];}insert(sum % M, i);}if(solve()) puts("Twin snowflakes found.");else puts("No two snowflakes are alike.");return 0;
}