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;
}
分享到:
相关推荐
Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!
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)); ...
BKDR Hash(Berkely-Knuth-Dhrymes Hash)基于一个固定的种子值,每次迭代都将当前字符与种子值相乘,然后加上哈希值。这种方法简单且高效,适合处理简单的字符串。 这些哈希函数各有特点,适用于不同的场景。例如...
本文将基于“hash函数 c语言”的主题,深入探讨几种常见的哈希算法及其C语言实现,包括RSHash、JSHash、P.J.Weinberger Hash(PJWHash)、SDBMHash、ELFHash、BKDRHash、DJBHash以及APHash,这些函数旨在将任意长度...
描述中提到了一些常见的哈希函数,如BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash,并且给出了这些函数在特定测试场景下的得分情况。这些测试场景包括了随机字符串、有意义的英文句子...
这是另一个哈希模板题,可以通过哈希函数,如BKDRHash,对字符串进行快速的唯一性判断。C++中的STL库中的map也可以用于此目的,但哈希表通常提供更快的查找速度。Trie字典树也是解决这类问题的一种选择,但对于较大...
接下来我们将介绍几种典型的哈希函数构造方法,包括SDBMHash、RSHash、JSHash、PJWHash、ELFHash、BKDRHash、DJBHash和APHash等。这些函数都具有良好的性能特点,可以作为学习和实践的参考。 ##### 1. SDBMHash ``...
在计算机科学中,字符串哈希(Hash)函数是一种将任意长度的字符串映射为固定长度数值的方法,这个数值通常称为哈希值。哈希函数在数据结构、算法和信息安全等领域有着广泛的应用,如散列表的构建、快速查找、数据...
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算法转成js。这几个hash算法是: RSHash JSHash ELFHash BKDRHash SDBMHash DJBHash APHash 可以拿对应的js即可
本文将深入探讨几种常用的哈希函数,包括SDBMHash、RSHash、JSHash、PJWHash、ELFHash、BKDRHash、DJBHash以及APHash,并分析它们的工作原理及特点。 ### SDBMHash SDBMHash是一种基于字符串的哈希函数,其计算...
5. **BKDRHash**(Bernstein哈希函数): 它使用一个种子值`seed`,并将哈希值与字符值相乘后累加。这种方式保证了连续的字符对哈希值的影响有累积效应,提高了哈希的区分度。 这些哈希函数虽然简单,但都具有一定...
在`BKDRHash`函数中,种子通常是素数,以增加哈希值的随机性。这种方法简单易实现,但在处理特定输入时可能产生较多冲突。 这些经典哈希算法各有特点,适用于不同的场景。例如,RS和JS哈希适用于需要快速计算和较小...
例如,BKDR Hash是一种常用的字符串哈希算法,其基本思想是将字符串视为一个P进制数,P通常取素数如131或13331。算法步骤如下: 1. **预处理**:计算字符串的所有前缀的哈希值`hash[i] = (hash[i-1] * P + str[i]) ...
然后,通过BKDRhash算法计算每个文本块的hash值并构建整个文档的hash指纹信息;最后,根据hash指纹信息,基于RKR-GST匹配算法在文档级、段落级和句子级将文档与文档库进行匹配,获得文档相似度,以此实现剽窃检测。...
4. RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法 这些算法是早期的哈希函数,它们各有特点,但通常不被现代哈希表实现所采用。例如,RS算法使用了移位和异或操作,而DJB算法...