首页 > 代码库 > COGS 902 乐曲主题 题解 & hash入门贺
COGS 902 乐曲主题 题解 & hash入门贺
【题意】
给定一个长为n的序列，元素都是不超过88的正整数，求序列中主题的最大长度。
所谓主题是指在序列中出现了至少两次并且不相交的子串。特别的，主题可以变调，也就是说如果一个子串全部加上或减去一个数后与另一个子串相同，那么也认为它们是相同的。
对于100%的数据，n<=5000。
【解法】
所谓的变调不过是升降趋势相同，直接来一发差分就好。
答案显然有单调性，长度越长主题越不容易出现，因此可以二分答案，每次只要查询长为ans的子串中是否存在相同且不相交的两个子串即可。
查询子串是否相同可以用哈希实现，这样只要O(n)预处理一发h数组并递推幂取模，取hash值就果断O(1)了。
关于hash的取模，可以直接用unsigned long long自动溢出取模(虽然这是最容易被卡的hash……)。
贴个代码(也不知道出了什么事儿，莫名的折叠不了了，垃圾cnblogs)：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<map> 5 #define ULL unsigned long long 6 using namespace std; 7 const int maxn=5010; 8 const ULL T=173ull; 9 void init(); 10 ULL hash(int,int); 11 ULL h[maxn],pw[maxn],tmp; 12 int n,a[maxn],L,R,M; 13 bool ok; 14 map<ULL,int>id; 15 int main(){ 16 #define MINE 17 #ifdef MINE 18 freopen("theme.in","r",stdin); 19 freopen("theme.out","w",stdout); 20 #endif 21 scanf("%d",&n); 22 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 23 for(int i=n;i;i--)a[i]-=a[i-1]; 24 init(); 25 L=4;R=n; 26 while(L<=R){ 27 M=(L+R)>>1; 28 ok=false; 29 for(int i=1;i+M-1<=n;i++){ 30 tmp=hash(i,M); 31 if(id.count(tmp)){ 32 if(id[tmp]<i-M){ 33 ok=true; 34 break; 35 } 36 } 37 else id[tmp]=i; 38 } 39 if(ok)L=M+1; 40 else R=M-1; 41 } 42 if(L<5)L=0; 43 printf("%d",L); 44 #ifndef MINE 45 printf("\n-------------------------DONE-------------------------\n"); 46 for(;;); 47 #endif 48 return 0; 49 } 50 inline void init(){ 51 for(int i=n;i;i--)h[i]=h[i+1]*T+(a[i]+1); 52 pw[0]=1ull; 53 for(int i=1;i<=n;i++)pw[i]=pw[i-1]*T; 54 } 55 inline ULL hash(int x,int l){return h[x]-h[x+l]*pw[l];} 56 /* 57 30 58 25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18 59 82 78 74 70 66 67 64 60 65 80 60 Answer: 61 9 62 */
【hash相关】
虽说是抄的蓝书的hash……但不管怎么说自己算是会写hash了……好感动……
如果字符串给定，询问的串都是它的子串，那么可以O(n)预处理，O(1)查询。
具体来说，定义后缀hash函数为
hi=Tn-i+1si+Tn-isi+1+……+sn，其中T代表字符集大小。
那么利用秦九韶大法，有如下递推式：
hi=hi+1*T+si
然后就可以happy的O(n)推出所有h值啦。
查询的时候，记以x开头，长为l的子串的hash值为hash(x,l)，那么有
hash(x,l)=Tlsx+Tl-1sx+1+……+sx+l-1
由上面h函数的公式，可以推出
hash(x,l)=hx-Tlhx+l
然后就可以happy的O(1)查询啦。
COGS 902 乐曲主题 题解 & hash入门贺
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。