Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
已亥年端午节清晨,哈希表1A留念#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator