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

坑爹为什么用HashMap直接存雪花的六边会超时,不过还是A了

Posted by zt990323 at 2019-02-20 23:16:16 on Problem 3349
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static boolean jud(int[][] map,int x,int y) {
		int[] temp=new int[12];
		boolean flag=false;
		
		for(int i=0;i<6;i++) {
			temp[i]=map[x][i];
			temp[i+6]=map[x][i];
		}
		for(int i=0;i<6;i++) {
			if(temp[i]==map[y][0]&&temp[i+1]==map[y][1]&&temp[i+2]==map[y][2]&&temp[i+3]==map[y][3]&&temp[i+4]==map[y][4]&&temp[i+5]==map[y][5]) {
				flag=true;
				break;
			}
			if(temp[11-i]==map[y][0]&&temp[11-i-1]==map[y][1]&&temp[11-i-2]==map[y][2]&&temp[11-i-3]==map[y][3]&&temp[11-i-4]==map[y][4]&&temp[11-i-5]==map[y][5]) {
				flag=true;
				break;
			}
		}
		
		return flag;
	}
	
	public static boolean check(int[][] map,LinkedList res,int i) {
		Iterator<Integer> ope=res.iterator();
		boolean flag=false;
		
		while(ope.hasNext()&&!flag) {
			flag=jud(map,i,ope.next());
		}
		
		return flag;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException{
		int mod=999983;
		LinkedList<Integer>[] hash=new LinkedList[mod];
		int[][] map=new int[100005][6];
		int index=0;
		BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
		String[] temp=new String[6];
		int n;
		boolean flag=false;
		
		n=Integer.parseInt(sc.readLine());
		for(int i=0;i<n&&!flag;i++) {
			temp=sc.readLine().split(" ");
			int count=0;
			for(int j=0;j<6;j++) {
				map[i][j]=Integer.parseInt(temp[j]);
				count+=map[i][j];
				count%=mod;
			}
			if(hash[count]==null) {
				hash[count]=new LinkedList<Integer>();
				hash[count].offer(i);
			}
			else {
				if(check(map,hash[count],i)) {
					flag=true;
					break;
				}
				else 
					hash[count].offer(i);
			}
			
		}
		if(flag)
			System.out.println("Twin snowflakes found.");
		else
			System.out.println("No two snowflakes are alike.");
	}
}

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