字符串的哈希hdu1800

题目：
(a b c d e)
(a b c d )
(a c f e)
这不就是求，含有最多战士的等级人数
本题的本质是——求相同级别（level）的人最多是几个

Sample Input
4 ((0<=N<=300)4个战士，下面4行，表示这个战士的level(小于30个数字，仲表示非负数，顶))
10
20
30
04

5
2
3
4
3
4
 

Sample Output
1
2

根据题意可知：意思是有若干个飞行员，需要在扫帚上练习飞行，每个飞行员具有不同的等级，且等级高的飞行员可以当等级低的飞行员的老师，且每个飞行员至多有且只有一个老师和学生。具有老师和学生关系的飞行员可以在同一把扫帚上练习，并且这个性质具有传递性。即比如有A，B，C，D，E五个飞行员，且等级是A>B>C>D>E，那么可以使A当B的老师，B当C的老师，E当D的老师，那么A，B，C可以在同一扫帚上练习，D，E在同一把扫帚上练习，这样需要2把扫帚，而如果是A当B的老师，B当C的老师，C当D的老师，D当E的老师，那么只需要一把扫帚。题目所求即所需最少的扫帚数目。

假设有若干个飞行员，{{A1,A2,A3...AK},{B1,B2,B3,...Bm}......{F1,F2,F3.....Fn}}。其已经按照等级由低到高排好序，在同一个集合里的飞行员等级相同。若需要最少数目的扫帚，则只能是{A1,B1.....F1},{A2,B2....F2}..这样进行组合，扫帚数目最少。因此决定所需最少扫帚数目的集合是含有飞行员最多的集合，即同一等级数目最多的飞行员集合。因此可以采用STL中的map直接实现。

 

就是找出最大的相同个数。  有可能，有前缀0.所以要去掉前缀0。 这个点错了几次。。= =！
用map ，100W个数据，1秒内一般会超时！！！这时还是果断码字典树！

 

不加大数组又越界，加大数组又超时了，想练下哈希，还是用字典树算了

#include<stdio.h>
#include<string.h>
#define Max 70003
int hashlevel[Max];

unsigned int BKDRHash(char * str)
{
    while(*str=='0')
        *str++;
    unsigned int seed=131;
    unsigned int hash=0;
    //从前缀非0，开始
    while(*str)
    {
        hash=hash*seed + *str++;
    }
    return (hash&0x7FFFFFFF);
}

int main()
{
    int N;
    while(scanf("%d",&N)!=EOF)
    {
        char tempstr[30];
        unsigned int index;
        memset(hashlevel,0,sizeof(hashlevel));
        int maxlevel=0;
        for(int i=0;i<N;i++)
        {
            scanf("%s",tempstr);
            index=BKDRHash(tempstr);
            hashlevel[index]++;
            if(hashlevel[index]>maxlevel)//免得待会又要遍历一次
                maxlevel=hashlevel[index];
        }
        printf("%d\n",maxlevel);
    }
    return 0;
}

 

直接用map,不自己写哈希算法，用自带的的 一下就OK掉

/*hdu 1800 最大分配 2011.10.12*/
#include <iostream>
#include<map>
using namespace std;

int main(int argc, char *argv[])
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int i;
        map<int,int> mp;
        int max=INT_MIN;
        for(i=0;i<n;i++)
        {
            int level;
            scanf("%d",&level);
            mp[level]++;
            if(mp[level]>max)
            {
                max=mp[level];
            }
        }
        printf("%d\n",max);
    }
    return 0;
}