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