[POJ 1200]Crazy Search

很容易想到哈希+set判重的方法,但好像会T吧……

那么就要直接开哈希表了,但是哈希函数会很大,怎么办呢?

我们看到还有一个NK啊……这样就有一个行之有效的方法了:将字符串里的字符映射到[tex][0,NK-1][/tex],然后就可以开哈希表了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=16000005;
int length,k;
bool P[maxn];
unsigned int hash[maxn],x_pow[maxn];
unsigned int ns[maxn];
void InitHash(){
	register int i;
	for(i=length;i>=1;i--)
		hash[i]=ns[i]+hash[i+1]*k;
	x_pow[0]=1;
	for(i=1;i<=length;i++)
		x_pow[i]=x_pow[i-1]*k;
}
unsigned int Hash(int i,int L){
	return hash[i]-x_pow[L]*hash[i+L];
}
char s[maxn];
int a[128];
int main(){
	int n;
	register int i,j=0,ans=0;
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	length=strlen(s);
	for(i=0;i<length;i++){
		if(!a[s[i]]){
			a[s[i]]=j++;
		}
		if(j==k)
			break;
	}
	for(i=1;i<=length;i++){
		ns[i]=a[s[i-1]];
	}
	InitHash();
	for(i=1;i<=(length-n+1);i++){
		j=Hash(i,n);
		if(!P[j]){
			P[j]=true;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ 2081]Beads

Hash第一题……

这个题直接枚举串长Hash判断即可。不过,注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣!

代码:

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}