是不是随便hash都能过
查看原帖
是不是随便hash都能过
807950
xyvsvg楼主2022/12/10 18:04
#include<iostream>
#include<stack>
#include<string.h>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
#include<vector>
#include<ctype.h>
using namespace std;
inline void mr(int& theNumberToRead) { theNumberToRead = 0; int prn = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-')prn = -1; c = getchar(); }while (isdigit(c)) { theNumberToRead = 10 * theNumberToRead + c - 48; c = getchar(); }theNumberToRead *= prn; }
int n, ans;
const int m = 999983, k = 1 << 8;
string s;
vector<string>l[m];
void ins()
{
	int h = 1;
	for (int i = 0; i < s.length(); ++i)
		h = (1LL * h * k + s[i]) % m;
	for (int i = 0; i < l[h].size(); ++i)
		if (l[h][i] == s)
			return;
	++ans;
	l[h].push_back(s);
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> s;
		ins();
	}
	cout << ans;
	return 0;
}

直接以首位字母作为hash值 甚至比常用hash快了一点,不过肯定是可以构造数据来卡的

2022/12/10 18:04
加载中...