bzoj1717[Usaco2006 Dec]Milk Patterns 产奶的模式*「建议收藏」

bzoj1717[Usaco2006 Dec]Milk Patterns 产奶的模式*

大家好,又见面了,我是全栈君。

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账号...

(0)


相关推荐

  • 关于 python 的缩进「建议收藏」

    关于 python 的缩进「建议收藏」python对缩进是敏感的,而大多教程对应缩进也只是几句话带过,对新手十分不友好,本文就把python常见的缩进问题做了一些整理。

  • mysql 组合索引 前缀_Mysql中的联合索引、前缀索引、覆盖索引[通俗易懂]

    mysql 组合索引 前缀_Mysql中的联合索引、前缀索引、覆盖索引[通俗易懂]索引索引是一种特殊的文件,它们包含着对数据表里所有记录的引用指针。更通俗的说,数据库索引好比是一本书前面的目录,能加快数据库的查询速度。联合索引又名复合索引,由两个或多个列的索引。它规定了mysql从左到右地使用索引字段,对字段的顺序有一定要求。一个查询可以只使用索引中的一部分,更准确地说是最左侧部分(最左优先)。如索引是keyindex(a,b,c).可以支持a|a,b|a,b,c…

  • JavaScript给元素添加class属性

    JavaScript给元素添加class属性注意:element.classList.remove()、element.classList.add()—ie9及以下不兼容//移除div的class属性obj.classList.remove(‘active’);//添加class属性值//方式一obj.className+=’newactive’;//方式二//obj.className=…

  • Altium Designer 13 安装完整元件库「建议收藏」

    Altium Designer 13 安装完整元件库「建议收藏」AltiumDesigner更新的非常快,都快赶上chrome了,13出来没多久14又出来了,之前一直用AD9.4,算是10之前的最后一个版本,也是很经典的一个版本。安装新版本后看到在目录结构上有些

  • DLL注入explorer.exe进程[通俗易懂]

    DLL注入explorer.exe进程[通俗易懂]**DLL注入explorer.exe进程**  最近一直在学习dll注入远程进程的相关知识,于是有了这篇文章。通过注入的方式会运行程序,在资源管理器中是看不到,相关的进程的,这为程序的隐藏提供了极大的便利。一、新建dll动态链接库,然后在dllmain.cpp文件中的“caseDLL_PROCESS_ATTACH:”下输入当你dll被进程加载时要执行的代码。这里我们用“Messag…

  • hd2616

    hd2616

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号