Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > C/C PLUSPLUS > » 正文

【BKDR_hash】HDU 2468 Shopping

来源: 基德KID.1412 分享至:

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
  • 查看图片附件

Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史