大家好,又见面了,我是全栈君。
bzoj1717[Usaco2006 Dec]Milk Patterns 产奶的模式
题意:
John记录了n天的牛奶质量值。他想知道最长的出现了至少k次的模式(即一个连续子串)的长度。n≤20000。
题解:
求一个总哈希值,二分模式长度,枚举每个模式开始端点,获得它的哈希值,然后排序比较有没有至少k个相等。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 20010 6 #define ll unsigned long long 7 #define yyl 2333 8 using namespace std; 9 10 inline int read(){ 11 char ch=getchar(); int f=1,x=0; 12 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} 13 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 14 return f*x; 15 } 16 ll hash[maxn],mi[maxn],calc[maxn],pat[maxn]; int n,k,l,r,ans,tot; 17 int main(){ 18 n=read(); k=read(); inc(i,1,n)pat[i]=read(); mi[0]=1; 19 inc(i,1,n)hash[i]=hash[i-1]*yyl+pat[i],mi[i]=mi[i-1]*yyl; l=1; r=n; 20 while(l<=r){ 21 int mid=(l+r)>>1; tot=0; inc(i,mid,n)calc[++tot]=hash[i]-hash[i-mid]*mi[mid]; 22 sort(calc+1,calc+tot+1); int x=0,y=0; 23 inc(i,1,tot){ if(!x||calc[i]!=calc[x])x=i; y=max(y,i-x+1);} 24 if(y>=k)ans=mid,l=mid+1;else r=mid-1; 25 } 26 printf("%d",ans); return 0; 27 }
20161102
转载于:https://www.cnblogs.com/YuanZiming/p/6038743.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108801.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...