1 条题解

  • 1
    @ 2023-12-18 14:49:31

    这一题中计算哈希值时,如果将一个字符串所有字符都考虑一遍,就有几个点会超时,只能得63分。 我们可以当字符串过长时,只读取它的某一部分(例如前200个字符),就可以避免超时。 不过如果这样做,当两个字符串前200个字符相同,后面却不相同时,哈希冲突是不可避免的,所以有一个点过不了。 经过调试,我发现按照同样的方式从后往前读,当字符串过长时只读200个字符,就可以通过所有测试点。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    
    const int k = 114514,p=11451419198101145;
    
    int ksm(int a,int b,int p){
    	if(b==2) return a*a%p;
    	if(b==1) return a%p;
    	if(b==0) return 1;
    	if(b<0) return 0;
    	if(b&1) return a%p*ksm(a*a%p,b/2,p);
    	return ksm(a*a%p,b/2,p);
    }//递归快速幂
    
    int strhash(string s){
    	int lens=s.size();
    	int ret = 0;
    	for(int i=lens-1;i>=max(0LL,lens-200LL);i--){
    		ret%=p;
    		ret+=s[i]*ksm(k,lens-1-i,p);
    	}
    	return ret;
    }
    
    map<int,int> cxcs;
    
    signed main(){
    	string nows;
    	int n,nowhsh;
    	cin>>n;
    	while(n--){
    		cin>>nows;
    		nowhsh=strhash(nows);
    		cxcs[nowhsh]++;
    	}
    	int ans=0;
    	for(auto it:cxcs){
    		if(it.second>0) ans++;
    	}
    	cout<<ans;
    }
    

    信息

    ID
    1355
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    36
    已通过
    12
    上传者