HDU 1800 Flying to the Mars

Description

给出n，与n个字符串，求出现次数最多的字符串出现的次数

（给出n个大数，求众数出现次数）

链接： http://acm.hdu.edu.cn/showproblem.php?pid=1800

Analyze

mapTLE了，即使ios::sync_with_stdio(false);

而哈希是解决普通算法TLE的，尤其是mapTLE的

字符串的Hash才有点真正的密码的味道

Code

///Hash 是解决 TLE 问题的，尤其是用mapTLE了
///字符串的Hash才有点真正Hash的味道
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

char s[40];
string str;
int has[3005];

int hashit(char * s)
{
    ll base = 131;
    ll res = 0;
    while(*s == '0')  ///指针所指字符为‘0’
        s++;
    while(*s)         ///指针不指向NULL
    {
        res = res * base + *s;
        s++;
    }
    return (res & 0x7fffffff); ///取了res较低位的31位，符号位为0(正)
}

int Hashit(string str)///slower 312 ms than char * s
{
    ll base = 131;
    ll res = 0;
    int pos = str.find_first_not_of('0', 0);
    if(pos == -1)
        return 0;
    int sz = str.size();
    for(int i = pos; i < sz; ++i)
        res = res * base + str[i];
    return (res & 0x7fffffff);
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        map<int, int> mp;
//        int ans = 0, tem = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s);
            has[i] = hashit(s);
//            tem = hashit(s);
//            mp[tem]++;
//            if(mp[tem] > ans)
//                ans = mp[tem];
//            cin >> str;
//            has[i] = Hashit(str);
        }

        sort(has, has + n);
        int tem = 1, ans = 1;
        for(int i = 1; i < n; ++i)
        {
            if(has[i] == has[i - 1])
            {
                tem++;
                ans = max(ans, tem);
            }
            else
                tem = 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

一点发现

string 会比 char * s 慢

调用map 会比 数组改装 慢

结论：封装好的东西往往要比自己写的原生态的东西要慢 -> 自己造轮子是合理的