这是我自己的代码
#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;
}
不能说是十分相似,只能说是一模一样。。。 但为什么我就超时了呀!!!(萌新瑟瑟发抖)