社区讨论

单哈希,自然溢出,为什么只有20分

P3370【模板】字符串哈希参与者 5已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi86ict1
此快照首次捕获于
2025/11/21 09:25
4 个月前
此快照最后确认于
2025/11/21 09:25
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define ONLINE_JUDGE 1
#define lowbit(x) ((x)&(-x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)>(y)?(x):(y))

using namespace std;

inline long long read()
{
    register int w=1;
    register long long s=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}

inline void write(long long x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

const int kmax=10010;
const unsigned long long prime=19260817,base=97;
unsigned long long a[kmax];
char s[kmax];
int n;

unsigned long long hash()
{
	int len=strlen(s);
	unsigned long long ans=0;
	for(int i=0;i<len;i++)
	{
		ans=(ans*base+s[i])+prime;
	}
	return ans;
}

int main()
{

#ifdef ONLINE_JUDGE
#else
    freopen("testdata.in","r",stdin);
    freopen("testdata.out","w",stdout);
#endif // ONLINE_JUDGE

    n=read();
    for(int i=0;i<n;i++)
    {
    	scanf("%s",s);
    	a[i]=hash();
	}
	write(unique(a,a+n)-a-1);

#ifdef ONLINE_JUDGE
#else
    fclose(stdin);
    fclose(stdout);
#endif // ONLINE_JUDGE

    return 0;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...