1 条题解
-
1
这一题中计算哈希值时,如果将一个字符串所有字符都考虑一遍,就有几个点会超时,只能得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
- 上传者