| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
附上WA的代码和一组测试数据,求大佬指导#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 100005;
const int Mod = 1000005;
struct Node
{
int arm[6];
int next;
}A[MAXN];
int H[Mod];
int Hash(Node t)
{
int ans = 0;
for(int i = 0; i < 6; i++)
ans += t.arm[i];
return ans%Mod;
}
bool Judge(Node a, Node b)
{
int i, j, k, cnt;
for(k = 0; k < 6; k++)
if(b.arm[k] == a.arm[0])
break;
cnt = 0;
for(i = 0, j = k; i < 6; i++, j++)
{
j %= 6;
if(a.arm[i] == b.arm[j]) cnt++;
}
if(cnt == 6)
return true;
cnt = 0;
for(i = 0, j = k; i < 6; i++, j--)
{
if(j < 0) j = (j+6)%6;
if(a.arm[i] == b.arm[j]) cnt++;
}
if(cnt == 6)
return true;
return false;
}
bool InsertHash(Node t)
{
int ha = Hash(t);
int a = H[ha];
bool flag = false;
if(a == -1) H[ha] = t.next;
else
{
while(1)
{
if( Judge(A[a], t) )
flag = true;
a = A[a].next;
if(a == A[a].next)
break;
}
}
if(flag) return true;
A[a].next = t.next;
return false;
}
int main()
{
int N, cnt = 1;
scanf("%d", &N);
memset(H, -1, sizeof(H));
bool flag;
for(int i = 0; i < N; i++)
{
scanf("%d%d%d%d%d%d",&A[i].arm[0],&A[i].arm[1],&A[i].arm[2],&A[i].arm[3],&A[i].arm[4],&A[i].arm[5]);
A[i].next = i;
if(flag) continue;
else flag = InsertHash(A[i]);
}
if(flag) printf("Twin snowflakes found.\n");
else printf("No two snowflakes are alike.\n");
return 0;
}
/*
2
1 2 3 4 5 6
1 4 2 5 3 6
// 上面这组数据很关键,过了的答案是相同
5
1 2 3 4 5 6
2 3 8 5 6 1
2 4 5 6 7 1
6 5 7 3 2 1
5 6 1 2 3 4
*/
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator