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

写了N多HASH,都TLE,用经典的也TLE

Posted by jiangwuqwe at 2010-05-25 11:18:06 on Problem 2503
#include <stdio.h>
#include <string.h>
//#include <windows.h>

#define MAXN 100000
#define Prime 3999971

typedef struct _dir{
	char F[11];
	char E[11];
}DIR;

unsigned char hash[Prime];
DIR dir[MAXN+2];

int hashcode(char *str) // 0.35
{
	int hash=0,x = 0,i;
	int n = strlen(str);
	
	for (i = 0; i <n; i++) {
		hash = (hash <<4) + str[i];
		if ((x = hash & 0xf0000000) != 0) {
			hash ^= (x>> 24);
			hash &= ~x;
		}
	}
	hash %= Prime;
	if(hash<0)hash += Prime;
	return hash;
}


// int hashcode(char *str)
// {
// 	int n = strlen(str);
// 	int hash = n;
// 	int i;
// 	for(i=0;i<n;i++)
// 	{
// 		hash *= (str[i]-'a'+1);
// 	}
// 	hash %= Prime;
// 	if(hash<0)hash+=Prime;
// 	return hash;
// }

int main()
{
	int i=1;
	int p;
	char str[30];
//	long start = GetTickCount();
	freopen("in.txt","r",stdin);

	while (1)
	{
		gets(str);
		if(!strlen(str))break;
		sscanf(str,"%s%s",dir[i].E,dir[i].F);
		p = hashcode(dir[i].F);
		while (hash[p]!=0)
		{
			p++;
			p %= Prime;
		}
		hash[p] = i++;
	}
	//scanf("%*c");
	while(scanf("%s",str)!=EOF)
	{
		p = hashcode(str);
		while (hash[p]!=0)
		{
			if (!strcmp(str,dir[hash[p]].F))
			{
				printf("%s\n",dir[hash[p]].E);
				break;
			}
			p++;
			p%=Prime;
		}
		if (hash[p]==0)printf("eh\n");
	}
//	printf("%d ms\n",GetTickCount()-start);
	return 0;
}

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