Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

已亥年端午节清晨,哈希表1A留念

Posted by vjubge4 at 2019-06-07 09:05:17 on Problem 2408
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull, int> P1;
int N;
vector<P1> Hash_Table;
char input[30000][51];
const ull base = 31;
vector<int> Bucket[30000];

bool Comp_Vec(vector<int> a, vector<int> b){
    if(a.size() == b.size()){
        if(strcmp(input[a[0]], input[b[0]]) < 0){
            return true;
        } else {
            return false;
        }
    }
    return a.size() > b.size();
}

bool Comp_P1(P1 a, P1 b) {
    if(a.first == b.first) {
        if(strcmp(input[a.second], input[b.second]) < 0) {
            return true;
        } else {
            return false;
        }
    }
    return a.first < b.first;
}

ull get_hash_code(char * s) {
    ull res = 0;
    int ctr[26];
    memset(ctr, 0, sizeof(ctr));
    int L = strlen(s);
    for(int i = 0; i < L; i ++) {
        ctr[s[i] - 'a'] ++;
    }
    for(int i = 0; i < 26; i++) {
        res = res * base + ctr[i];
    }
    return res;
}

int main() {
    N = 0;
    while(~scanf("%s", input[N])) {
        ull hashcode = get_hash_code(input[N]);
        Hash_Table.push_back(make_pair(hashcode, N));
        N ++;
    }
    sort(Hash_Table.begin(), Hash_Table.end(), Comp_P1);
    int M = -1;
    ull prev;
    for(int i = 0; i < N; i ++) {
        if(i == 0 || Hash_Table[i].first != prev) {
            M ++;
            prev = Hash_Table[i].first;
        }
        Bucket[M].push_back(Hash_Table[i].second);
    }
    M++;
    sort(Bucket, Bucket + M, Comp_Vec);
    for(int i = 0; i < min(5, M); i ++){
        printf("Group of size %d: ", Bucket[i].size());
        for(int j =0; j < Bucket[i].size(); j ++){
            if(j != 0 && strcmp(input[Bucket[i][j]], input[Bucket[i][j - 1]]) == 0){
                continue;
            }
            printf("%s ", input[Bucket[i][j]]);
        }
        printf(".\n");
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator