`

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

 

1
0
分享到:
评论

相关推荐

    20多个常用的Hash算法C++ 实现

    Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!

    各种Hash函数(JAVA版)

    BKDR-Hash Function Value: " + ghl.BKDRHash(key)); System.out.println(" 6. SDBM-Hash Function Value: " + ghl.SDBMHash(key)); System.out.println(" 7. DJB-Hash Function Value: " + ghl.DJBHash(key)); ...

    hash字符串函数总结

    BKDR Hash(Berkely-Knuth-Dhrymes Hash)基于一个固定的种子值,每次迭代都将当前字符与种子值相乘,然后加上哈希值。这种方法简单且高效,适合处理简单的字符串。 这些哈希函数各有特点,适用于不同的场景。例如...

    hash函数 c语言

    本文将基于“hash函数 c语言”的主题,深入探讨几种常见的哈希算法及其C语言实现,包括RSHash、JSHash、P.J.Weinberger Hash(PJWHash)、SDBMHash、ELFHash、BKDRHash、DJBHash以及APHash,这些函数旨在将任意长度...

    各种字符串Hash函数比较1

    描述中提到了一些常见的哈希函数,如BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash,并且给出了这些函数在特定测试场景下的得分情况。这些测试场景包括了随机字符串、有意义的英文句子...

    Hash相关题解1

    这是另一个哈希模板题,可以通过哈希函数,如BKDRHash,对字符串进行快速的唯一性判断。C++中的STL库中的map也可以用于此目的,但哈希表通常提供更快的查找速度。Trie字典树也是解决这类问题的一种选择,但对于较大...

    hashmap中hash函数的构造问题

    接下来我们将介绍几种典型的哈希函数构造方法,包括SDBMHash、RSHash、JSHash、PJWHash、ELFHash、BKDRHash、DJBHash和APHash等。这些函数都具有良好的性能特点,可以作为学习和实践的参考。 ##### 1. SDBMHash ``...

    经典字符串hash函数

    在计算机科学中,字符串哈希(Hash)函数是一种将任意长度的字符串映射为固定长度数值的方法,这个数值通常称为哈希值。哈希函数在数据结构、算法和信息安全等领域有着广泛的应用,如散列表的构建、快速查找、数据...

    字符串哈希成数字的C实现的代码(含测试)

    unsigned int BKDRHash(char* str, unsigned int len); unsigned int SDBMHash(char* str, unsigned int len); unsigned int DJBHash (char* str, unsigned int len); unsigned int DEKHash (char* str, unsigned ...

    哈希算法模拟

    对于各种哈希算法的模拟 SDBMHash; RSHash; JSHash; P. J. Weinberger Hash Function; ELF Hash Function ; BKDR Hash Function ; DJB Hash Function ; AP Hash Function;

    哈希表的几种表示方式

    Weinberger Hash Function、BKDR Hash Function以及ELF Hash Function等。 1. **RS Hash Function**: RS Hash是由Ronald L. Rivest设计的一种哈希函数。它的基本思想是通过两个常数a和b来不断地更新哈希值。哈希...

    hash-encrypt:将几个常见的几个c++ hash加密算法改写成javascript

    关于hash-encrypt 本项目只是把几个常见的c++ hash算法转成js。这几个hash算法是: RSHash JSHash ELFHash BKDRHash SDBMHash DJBHash APHash 可以拿对应的js即可

    常用哈希函数结构 数据结构

    本文将深入探讨几种常用的哈希函数,包括SDBMHash、RSHash、JSHash、PJWHash、ELFHash、BKDRHash、DJBHash以及APHash,并分析它们的工作原理及特点。 ### SDBMHash SDBMHash是一种基于字符串的哈希函数,其计算...

    常用Hash算法(C语言的简单实现)

    5. **BKDRHash**(Bernstein哈希函数): 它使用一个种子值`seed`,并将哈希值与字符值相乘后累加。这种方式保证了连续的字符对哈希值的影响有累积效应,提高了哈希的区分度。 这些哈希函数虽然简单,但都具有一定...

    经典hash算法

    在`BKDRHash`函数中,种子通常是素数,以增加哈希值的随机性。这种方法简单易实现,但在处理特定输入时可能产生较多冲突。 这些经典哈希算法各有特点,适用于不同的场景。例如,RS和JS哈希适用于需要快速计算和较小...

    yxy版c++教程 Hash 浅谈哈希算法(csdn)————程序.pdf

    例如,BKDR Hash是一种常用的字符串哈希算法,其基本思想是将字符串视为一个P进制数,P通常取素数如131或13331。算法步骤如下: 1. **预处理**:计算字符串的所有前缀的哈希值`hash[i] = (hash[i-1] * P + str[i]) ...

    论文研究-基于分级匹配的维吾尔语文档相似性计算及剽窃检测方法.pdf

    然后,通过BKDRhash算法计算每个文本块的hash值并构建整个文档的hash指纹信息;最后,根据hash指纹信息,基于RKR-GST匹配算法在文档级、段落级和句子级将文档与文档库进行匹配,获得文档相似度,以此实现剽窃检测。...

    Java常用HASH算法总结【经典实例】

    4. RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法 这些算法是早期的哈希函数,它们各有特点,但通常不被现代哈希表实现所采用。例如,RS算法使用了移位和异或操作,而DJB算法...

Global site tag (gtag.js) - Google Analytics