关于双哈希超时的问题
查看原帖
关于双哈希超时的问题
398312
国王的新账号楼主2021/4/8 19:08

这是我自己的代码

#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
int n,sum;
ull p1=393241,p2=1572689,mod1=25165843,mod2=50331653;
char s[100010];
struct node{
	ull x,y;
}num[10004];
int mp(char c)
{
	if(c>='0'&&c<='9')	c-=47;
	else if(c>='A'&&c<='Z')	c-=54;
	else if(c>='a'&&c<='z')	c-=60;
	return (int)c;
}
ull hash1(char s[])
{
	ull ans=0;
	for(int i=0;i<strlen(s);i++)	ans=(ans*p1+mp(s[i]))%mod1;
	return ans;
}
ull hash2(char s[])
{
	ull ans=0;
	for(int i=0;i<strlen(s);i++)	ans=(ans*p2+mp(s[i]))%mod2;
}
bool cmp(node a,node b)
{
	if(a.x==b.y)	return a.y<b.y;
	return a.x<b.x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s;
		num[i].x=hash1(s);
		num[i].y=hash2(s);
	}
	sort(num+1,num+1+n,cmp);
	for(int i=1;i<n;i++){
		if(num[i].x==num[i+1].x&&num[i].y==num[i].y)	sum++;
	}
	printf("%d",n-sum);
	return 0;
}

这是学长写的示范代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define ull unsigned long long
ull p1=393241,p2=1572689,mod1=25165843,mod2=50331653;

int map(char c){
	if(c>='0'&&c<='9') return c-47;
	if(c>='A'&&c<='Z') return c-54;
	if(c>='a'&&c<='z') return c-60;
}

struct node{
	ull x;
	ull y;
}a[10005];

ull hash1(string str){
	ull ans=0;
	for(int i=0;i<str.length();i++) ans = (ans * p1 + map(str[i]) ) % mod1;
	return ans;
}

ull hash2(string str){
	ull ans=0;
	for(int i=0;i<str.length();i++) ans = (ans * p2 + map(str[i]) ) % mod2;
	return ans;
}

bool cmp(node a, node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string str;
		cin>>str;
		a[i].x=hash1(str);
		a[i].y=hash2(str);
	}
	sort(a,a+n,cmp);
	int sum=0;
	for(int i=1;i<n;i++){
		if(a[i].x==a[i-1].x && a[i].y==a[i-1].y) sum++;
	}
	cout<<n-sum<<endl;
}

不能说是十分相似,只能说是一模一样。。。 但为什么我就超时了呀!!!(萌新瑟瑟发抖)

2021/4/8 19:08
加载中...