[COGS902]乐曲主题

本文主要是介绍[COGS902]乐曲主题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题一开始想的是hash+枚举长度+sort寻重$O(N^2log_2N)≈5000^2*12≈3*10^8$，但是模一个数就WA了，模两个数就T了；卡得不行不行的。
问题在于，实际上长度显然是单调合法的（如果len行，则小于len一定行），所以我们可以变枚举为二分。（宏哥Orz）
！！这也正是我没有想到的了，最近总是想着要寻找枚举顺序，改变枚举顺序；但是却忽略了寻找单调性。

#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#include<iostream>
#define P 1000000009
struct S{long long key;int r;inline bool operator < (const S a) const{return key!=a.key?key<a.key:r<a.r;}
}hash[5005];
int a[5005],N;
long long ni[2505],sum[90][2505];
inline bool check(int len){int i,k,j;k=1,hash[0]=(S){0,len-1};for(i=0;i<len;++i)hash[0].key=(hash[0].key*89+a[i])%P;for(;i<N;++i,++k)hash[k].key=((hash[k-1].key-a[i-len]*ni[len-1]%P)*89+a[i])%P,hash[k].r=i;for(i=0;i<k;++i)hash[i].key=((hash[i].key-sum[a[i]][len-1])%P+P)%P;sort(hash,hash+k),hash[k].key=-1;for(i=0;i<k;i=j){j=i+1;while(hash[j].key==hash[j-1].key)++j;if(hash[j-1].r-hash[i].r>=len)return 1;}return 0;
}
int main(){freopen("theme.in","r",stdin);freopen("theme.out","w",stdout);int i,j;scanf("%d",&N);for(i=0;i<N;++i)scanf("%d",a+i);ni[0]=1;for(i=1;i<N>>1;++i)ni[i]=ni[i-1]*89%P;for(i=88;i;--i){sum[i][0]=i;for(j=1;j<N>>1;++j)sum[i][j]=(sum[i][j-1]+i*ni[j])%P;}long long tmp;int l=5,r=(N>>1)+1;if(!check(5)){puts("0");return 0;}while(r-l>1){if(check(l+r>>1))l=l+r>>1;else r=l+r>>1;}printf("%d\n",l);
}

但是，其实模一个数是很容易被坑的，还是模两个数比较靠谱！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int Mod[2]={100000007,86028121};
typedef long long LL;
struct HS{int data[2],i;inline bool operator < (HS a)const{return data[0]!=a.data[0]?data[0]<a.data[0]:data[1]!=a.data[1]?data[1]<a.data[1]:i<a.i;}
}hash[5000];
int a[5005],delta[5005];
int N;
LL jc[5005][2],base=175;
int cal(int l,int r,int D){LL ans=0;for(;l<r;++l)ans=(ans*base%Mod[D]+delta[l])%Mod[D];return (ans+Mod[D])%Mod[D];
}
inline bool check(int len){//printf("----------%d-------\n",len);int i,tot,D;hash[0]=(HS){0};for(i=0;i<len;++i)for(D=0;D<2;++D)hash[0].data[D]=(hash[0].data[D]*base%Mod[D]+delta[i])%Mod[D];for(D=0;D<2;++D)hash[0].data[D]=(hash[0].data[D]+Mod[D])%Mod[D];/*printf("0:");for(D=0;D<2;++D)printf("%d ",hash[0].data[D]);printf("---");for(D=0;D<2;++D)printf("%d ",cal(0,len,D));puts("");*/for(i=1;i+len<N;++i){for(D=0;D<2;++D)hash[i].data[D]=(((hash[i-1].data[D]-delta[i-1]*jc[len-1][D]%Mod[D])%Mod[D]*base%Mod[D]+delta[i+len-1])%Mod[D]+Mod[D])%Mod[D];hash[i].i=i;/*printf("%d:",i);for(D=0;D<2;++D)printf("%d ",hash[i].data[D]);printf("---");for(D=0;D<2;++D)printf("%d ",cal(i,i+len,D));puts("");*/}tot=i;sort(hash,hash+tot);int j;for(i=0;i<tot;i=j+1){j=i;while(hash[j].data[0]==hash[j+1].data[0]&&hash[j].data[1]==hash[j+1].data[1])++j;if(hash[j].i-hash[i].i>len)return 1;}return 0;
}
int main(){freopen("theme.in","r",stdin);freopen("theme.out","w",stdout);scanf("%d",&N);int i,D;for(i=0;i<N;++i)scanf("%d",a+i);for(i=0;i+1<N;++i)delta[i]=a[i+1]-a[i]+87;jc[0][0]=1,jc[0][1]=1;for(i=1;i<=N>>1;++i)for(D=0;D<2;++D)jc[i][D]=jc[i-1][D]*base%Mod[D];/*for(i=1;i<=N>>1;++i){printf("%d:",i);for(D=0;D<2;++D)printf("%d ",jc[i][D]);puts("");}*/if(!check(4)){puts("0");return 0;}int l=4,r=(N>>1)+1,mid;while(r-l>1){mid=l+r>>1;if(check(mid))l=mid;else r=mid;}printf("%d\n",l+1);
}

这篇关于[COGS902]乐曲主题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---