hdu 1800 Flying to the Mars (字符串hash)

题目链接

题意:n个人,每个人有一个level值,用一个最长30位的,可能带前缀0的数字串表示,如果i的level大于j的level,那么i可以教j飞行,每个人只能有一个老师,每个人也只能收一个徒弟。师生可以共用一把扫帚飞行。现在问最少需要多少扫帚。

思路:分析发现,影响扫帚多少的是相等的数有多少,因为只要不相等,就肯定可以构成师生关系….

更确切得说,是所有数出现次数的最大值。

有一个trick点,就是带前缀0和不带前缀0的两个level被认为是相等的,hash的时候要处理前缀0.

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz