HDU 2648 Shopping

Problem Description

Every girl likes shopping,so does dandelion.Now she

finds the shop is increasing the price every day because the Spring Festival is

coming .She is fond of a shop which is called "memory". Now she wants to know

the rank of this shop's price after the change of everyday.

Input

One line contians a number n ( n<=10000),stands for the number of shops.

Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop.

Then a line contians a number m (1<=m<=50),stands for the days .

Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p 's price has increased s.

Output

Contains m lines ,In the ith line print a number of the

shop "memory" 's rank after the ith day. We define the rank as :If there are t

shops' price is higher than the "memory" , than its rank is t+1.

Sample Input

3

memory

kfc

wind

2

49 memory

49 kfc

48 wind

80 kfc

85 wind

83 memory

Sample Output

1

2

这题目的意思就是有n个商店。这n个商店会进行m天的销售，你需要每一天输出一次' memory' 的排名，而且这个商品的价钱是会累加的

例如第一天 kfc是49 第二天kfc在49的基础上在涨80 也就是 129

这道题我也是参考了很多人的代码，在不断的摸索下还是TLE 我就在想我到底错在那里

难道是因为我没有用vector的原因吗？在我不断检测我的代码发现我错在了一个死循环上，我忘记写p=p->next后来加上ac了

头疼 。、。。 一定一定要好好的检查自己的代码。

好了我们来说下这道题要怎么想

简单来说这道题运用了Hash + map 或者 Hash + vector 或者向我一样 Hash + 结构体指针数组

来说下为什么这道题用Hash，因为这道题你想要他快速的算出来你就必须让每天对应的商品加上对应的价钱对把

例如   第一天 

49 memory

49 kfc

48 wind

那么我们就要找memory在那里啊，是不是第一想到的就是用for循环去找但是每次都那么找可以吗

数据量是10000，也就是说光是累加商品价格你就要花费大量的时间去寻找，我们有没有办法一下子找到这个memory呢？

所以我们就用了Hash表，这样给我们省下大量的时间

使用了Hash表我们就需要给我们的Hash表定一个key函数，以及一个冲突处理机制

这里key函数的意义就是将字符串memory变成一个整形的数，我们就可以Hash[ key ] 直接拿到值了对不对

所以我们需要做这个key函数

key 函数：

这里用的是BKDR Hash

int nums=0，seed=31；

for(inti=0;str[i]!='\0';i++)

        nums=nums*seed+str[i];

nums=nums % 10005;  这里为什么要%10005呢 ？ 是因为我们的Hash数组就[10005]就那么大为了防止这个数超出去

那这里的seed为什么是31呢，这里的seed甚至可以是131，是其他的素数只是为了尽可能的每个nums都不一样而然防止冲突

那这里key求出来，一旦数据量大冲突是不可避免的对把。总是有一个字符串算出来的key是和之前的key相等对不对

这时候我们的冲突处理就出来拉

我们将这个hash表以链式存起来

这里如果地址冲突了我们就在原本的链尾加入新的结点就好拉

下面是ac代码

实在不懂怎么贴代码上来。。发图片 了。。。

这里的ins就是我们的key函数+插入链尾的操作

这里的find函数是为了查找str 然后找到后把每天变化的价钱加入我们的值里

第一次写这种类型的文，真的不会贴代码。。头巨疼。。。