【BKDR_hash】HDU 2468 Shopping_C/C++_编程开发_程序员俱乐部

KIDx 的解题报告

?

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2648

题意很简单，不解释，用map暴力也可以，但是要1000ms左右，或者更慢

?

引用：各种字符串Hash函数比较

?

其中我用的是BKDR Hash：

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    } 
    return (hash & 0x7FFFFFFF);
}

?第3名?

?

#include <iostream>
#include <vector>
using namespace std;
#define LL unsigned int
#define M 10005
#define N 13131

struct shop{
	int p;
	char s[35];
}sp[M];
vector<shop> g[N];
LL hash[M], key;

bool cmp (shop a, shop b)
{
	return strcmp (a.s, b.s) < 0;
}

LL BKDR_hash (char *s)
{
	LL seed = 131, hash = 0;
	while (*s)
	{
		hash = hash*seed + (*s++);
	}
	return (hash & 0x7fffffff);
}

int main()
{
	LL key;
	unsigned int k;
	int n, i, d, j, x, rank, ans;
	char s[35];
	while (~scanf ("%d", &n))
	{
		for (i = 0; i < N; i++)
			g[i].clear();
		for (i = 0; i < n; i++)
		{
			scanf ("%s", sp[i].s);
			sp[i].p = 0;
			key = BKDR_hash (sp[i].s) % N;
			g[key].push_back (sp[i]);
		}
		scanf ("%d", &d);
		ans = 0;
		for (i = 0; i < d; i++)
		{
			for (j = 0; j < n; j++)
			{
				scanf ("%d %s", &x, s);
				key = BKDR_hash(s) % N;
				for (k = 0; k < g[key].size(); k++)
				{
					if (strcmp (g[key][k].s, s) == 0)
					{
						g[key][k].p += x;
						if (strcmp (s, "memory") == 0)
							ans = g[key][k].p;
						break;
					}
				}
			}
			rank = 1;
			for (j = 0; j < N; j++)
			{
				for (k = 0; k < g[j].size(); k++)
				{
					if (g[j][k].p > ans)
						rank++;
				}
			}
			printf ("%d\n", rank);
		}
	}
    return 0;
}

?

• 
• 大小: 11 KB

• 
• 大小: 8.1 KB

• 查看图片附件