题目大意：
8888年，地球被PPF王国统治了。由于人口增长，PPF需要为新生儿找寻更多的陆地。最后，PPF决定攻击通知Mars火星的Kscinow。问题来了，怎样让士兵到火星上去呢？PPF召集士兵征询建议。最后决定从哈利波特那里买些魔法扫帚，让士兵们飞上去~现在那些士兵正在学习使用魔法扫帚。我们假设每个战士都有一个等级表示他的级别。高等级的战士可以指导低等级的，但是反过来不可以。一个战士最多有一名指导者，也可以没有指导者。类似的，一个战士最多可以指导一名学习者，也可以不指导任何人。指导者和学习者可以共用同一把扫帚。所有的战士必须在飞往火星之前准备好。扫把很贵，怎样才能使所需要的扫把数量最少？
例如，有五个战士a，b，c，d，e，他们级别是2，4，5，6，4；
方法一：
c teach b，bteach a，所以a，b，c可以使用一把扫帚；
d teach e，所以d，d可以使用一把扫帚；
这样就需要2把；
方法二：
d teach a，所以a，d用一把；
c teach b，所以b，c用一把；
e自用一把；
这样就需要3把；
。。。
最后在所有可能的方法中，我们发现最少要2把；
输入：多组测试用例
第一行：正整数N（0-3000）表示战士个数；
接下来N行，每行一个非负整数，表示战士级别；（不超过30位）
输出：每组测试用例，输出最少需要的扫把数；
===========由题可知===========
1、相同的数最多有几个。
2、如果战士级别不超过18位，那就可以用__int64或者long long来解决了，但是题目中要求30位，只能用字符串解决；
3、不到3000个士兵，也就是最多3000个士兵级别
==========代码【From HDUACMppt】==========
#include "stdio.h" #include "memory.h" #define MAXN 7003 inline int ELFhash(char *key)//一个Hash函数，通过key得到一个位置h { unsigned long h = 0,t; unsigned long g; while( *key ) { t =( h<< 4) ; h = t + *key++;//h右移四位，把*key的ASCII码存储在h的低四位；【0-9的ASCII码的后四位正好就是0-9的值】 g = h & 0xf0000000L;//取h的高四位 if( g ) h ^= g >> 24;//如果h的高四位非0，就把高四位右移24位（因为第四位存放的是刚放进来的数，所以不能右移28位） h &= ~g;//把h的高四位清零 } return h;//返回hash函数得到的位置 } int hash[MAXN],count[MAXN];//hash数组用来存放级别；count数组用来统计出现次数 int maxit,n;//n是士兵个数；maxit是最大重复次数 inline void hashit(char *str) { int k,t; while( *str == '0' ) str++;//去首0 k = ELFhash(str);//得到位置 t = k % MAXN;//确定位置 while( hash[t] != k && hash[t] != -1 )//解决冲突，找到一个空位置或者已经存放了k的位置 t = ( t + 10 ) % MAXN; if( hash[t] == -1 )//t位置为空 count[t] = 1,hash[t] = k; else//t位置已经存放了k if( ++count[t] > maxit ) maxit = count[t];//更新最大重复次数 } int main() { char str[100];//存储士兵级别的字符串 while(scanf("%d",&n)!=EOF)//读取士兵个数n { memset(hash,-1,sizeof(hash)); for(maxit=1,gets(str);n>0;n--) { gets(str);//读取级别 hashit(str);//处理士兵级别字符串 } printf("%d\n",maxit); } }
注意其中的hash函数：ELFHash，是字符串处理常用的一个hash函数；
关于这个hash函数解释的一篇文章：http://blog.csdn.net/zhccl/article/details/7826137
// ELF Hash Function unsigned int ELFHash(char *str) { unsigned int hash = 0; unsigned int x = 0; while (*str) { hash = (hash << 4) + (*str++);//hash左移4位，把当前字符ASCII存入hash低四位。 if ((x = hash & 0xF0000000L) != 0) { //如果最高的四位不为0，则说明字符多余7个，现在正在存第8个字符，如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。 //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位 //因为1-4位刚刚存储了新加入到字符，所以不能>>28 hash ^= (x >> 24); //上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。 hash &= ~x; } } //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负) return (hash & 0x7FFFFFFF); }
另一个人给的大同小异的解释：
unsigned int ELFHash( char * str) { unsigned int hash = 0 ; unsigned int x = 0 ; while ( * str) { hash = (hash < < 4 ) + ( * str ++ ); //hash值左移4位加上一个字符 if ((x = hash & 0xF0000000L ) != 0 )//判断hash值的高4位是否不为0，因为不为0时需要下面特殊处理，否则上面一步的左移4位会把这高四位给移走，造成信息丢失 { hash ^= (x >> 24 ); //把刚才的高4位跟hash的低5-8位异或 hash &= ~ x; //把高4位清0 } } return (hash & 0x7FFFFFFF ); //希望hash值是一个非负数 }
很遗憾，没有在网上搜到关于这个hash函数的原理。。。
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/12/19/2824879.html，如需转载请自行联系原作者
