【BKDR_hash】HDU 2648 Shopping

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);
}

 

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

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

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

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

int main()
{
	LL key;
	int n, i, j, k, d, 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);
			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;
}