| ||||||||||
| 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