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+链式前向星 3000MS AC

Posted by NtNlyCoder at 2015-12-05 13:01:30 on Problem 2785
Hash函数就用最简单的绝对值取模就好

(如果不好使,就先<<k位再绝对值取模,反正在不牺牲过多计算的情况下越乱越好),

关键是质数P要取的够大,大概要7位数,我取的是2222219;

以下是与Hash相关的部分代码:

#define N 4444
#define P 2222219

class Value
{
	public:
		int val;
		int num;
		int next;
};

int vn;
int hash[P];
Value v[N*N];

void Init()
{
	vn = 0;
	memset(hash,-1,sizeof(hash));
}

int Hash(int val)
{
	int hval = val > 0 ? val : -val;
	int hcode = hval % P;
	return hcode;
}

int Find(int val)
{
	int hcode = Hash(val);
	int u;
	for(u=hash[hcode];u!=-1;u=v[u].next)
	{
		if(v[u].val==val)
		{
			return u;
		}
	}
	return -1;
}

void AddValue(int val)
{
	int index = Find(val);
	if(index==-1)
	{
		int hcode = Hash(val);
		v[vn].val = val;
		v[vn].num = 1;
		v[vn].next = hash[hcode];
		hash[hcode] = vn++;
	}
	else
	{
		v[index].num++;
	}
}

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