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 |
java hash 为什么老是TLEpackage poj; import java.util.Scanner; public class Main3349 { private static final int N = 100003; private static HashArray[] hashAray = new HashArray[100003]; private static int[][] tables = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); tables = new int[n][6]; boolean flag = false; for (int i = 0; i < n; ++i) { int hashCode = 0; for (int j = 0; j < 6; ++j) { tables[i][j] = sc.nextInt(); hashCode += tables[i][j]; } if (!flag) { hashCode %= N; if (hashAray[hashCode] == null) { hashAray[hashCode] = new HashArray(); hashAray[hashCode].index = i; } else { HashArray front = hashAray[hashCode]; HashArray parents = front; do { if (check(i, front.index)) { flag = true; break; } parents = front; front = front.next; } while (front != null); if (!flag) { front = new HashArray(); front.index = i; front.next = parents; hashAray[hashCode] = front; } } } } if (!flag) System.out.println("No two snowflakes are alike."); else System.out.println("Twin snowflakes found."); } private static boolean check(int r1, int r2) { int[] snow1 = tables[r1]; int[] snow2 = tables[r2]; int j = 0, i = 0; int[] start = new int[6]; int s = 0; for (; i < 6; ++i) { if (snow2[i] == snow1[0]) { start[s++] = i; } } for (i = 0; i < s; ++i) { j = 0; int step2 = start[i]; boolean flag1 = false; boolean flag2 = false; for (int step1 = start[i]; step1 < 6 && j < 6 && step2 < 6;) { if (snow1[j] != snow2[step1] && !flag1) flag1 = true; if (snow1[j] != snow2[step2] && !flag2) flag2 = true; if (flag1 && flag2) break; j++; if (!flag1) step1 = (step1 + 1) % 6;//顺时针 if (!flag2) { step2--;//逆时针 if (step2 == -1) step2 = 5; } } if (j == 6) return true; } return false; } private static class HashArray { private int index; private HashArray next = null; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator