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

Hash map成功 516MS

Posted by mingrui at 2008-04-11 14:09:35 on Problem 1002
In Reply To:Re:Hash map 定义了一个unsigned int items[10000000],超内存 Posted by:wcw at 2008-03-31 19:48:25
原来是32位int
另外还要一个longint做后备,测试数据中确实有一类重复出现超过了65535次
正确的解19768K	516MS	C	1213B

#include<stdio.h>
unsigned short int items[10000000]={0};
long int backnum=0;

void main()
{
	long int num,i;
	char s_item[200],dup=0;
	scanf("%li",&num);
	for(i=0;i<num;i++)
	{
		long int j,k=1000000,li_item=0;
		scanf("%s",s_item);
		for(j=0;j<200&&k>0;j++)
		{
			char digit=s_item[j];
			long int n;
			if(digit>='0'&&digit<='9')
				n=(digit-'0')*k;
			else
				switch(digit)
				{
					case'A':case'B':case'C':n=2*k;break;
					case'D':case'E':case'F':n=3*k;break;
					case'G':case'H':case'I':n=4*k;break;
					case'J':case'K':case'L':n=5*k;break;
					case'M':case'N':case'O':n=6*k;break;
					case'P':case'R':case'S':n=7*k;break;
					case'T':case'U':case'V':n=8*k;break;
					case'W':case'X':case'Y':n=9*k;break;
					default:n=0;k*=10;break;
				}
			k/=10;
			li_item+=n;
		}
		if(items[li_item]<65535)
			items[li_item]++;
		else
			backnum++;

	}

	for(i=0;i<10000000;i++)
	{
		if(items[i]>1)
		{
			long int j;
			for(j=10000000;j>1;j/=10)
			{
				putchar((i%j-i%(j/10))*10/j+'0');
				if(j==100000)
					putchar('-');
			}
			printf(" %li\n",items[i]+(items[i]==65535?backnum:0));
			dup=1;
		}
	}
	if(!dup)
		printf("No duplicates.");
}

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