54分单哈希求助,wa了5,7,9,10,11
查看原帖
54分单哈希求助,wa了5,7,9,10,11
136992
ClearDream15楼主2023/7/28 11:45
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll MAXN = 10005;
const ll mod = 1000000;
string hashl[mod];
//ll conflict;
ll cnt;
ll gethash(string s){
	ll idx = 1;
	for(int i = 0;i<s.length();i++){
		ll num = s[i]-'0';
		idx =  idx*7*num+1001;
		idx%=mod;
	}
	return idx;
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	ll n;
	scanf("%lld",&n);
	while(n--){
		string s;
		cin >> s;
		ll idx = gethash(s);
		if(hashl[idx]==s) continue;
		while(hashl[idx]!=""&&hashl[idx]!=s){
			idx++;
			idx%=mod;
//			conflict++;
		}
		hashl[idx] = s;
		cnt++;
	}
//	cout << "Conflict " << conflict << " times";
	cout << cnt;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
2023/7/28 11:45
加载中...