Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

java hash 为什么老是TLE

Posted by wskwsk at 2010-09-02 21:03:06 on Problem 3349
package 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator