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)


相关推荐

  • office2016、office365和office其它版本JH[通俗易懂]

    office2016、office365和office其它版本JH[通俗易懂]Win10系统中会预安装Office,但是没有给JH,网上给了各种解决方案,如JH码、KMS等方式JH。但是效果差强人意。但是网上有一些大牛写的方法倒是立竿见影,下面分享给大家:CSDN现在被网安查的我都不敢修改了,自己原创被搞得涉及版权问题,文章中还不能有pojie和jihuoOJBK我将在JH中间遇到的问题,都罗列在这篇文章里了,也很感谢提出问题的C友们,此处我特别强调一下…

  • 一维数组二分法查找_二分查找算法c语言

    一维数组二分法查找_二分查找算法c语言在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。示例:现有矩阵 matrix 如下:[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5,返回

  • HTML5学习笔记之History API

    这系列文章主要是学习Html5相关的知识点,以学习API知识点为入口,由浅入深的引入实例,让大家一步一步的体会"h5"能够做什么,以及在实际项目中如何去合理的运用达到使用自如,完美

    2021年12月28日
  • 浅析MySQL中concat及group_concat的使用

    浅析MySQL中concat及group_concat的使用

  • 数据可视化工具d3_前端3d可视化

    数据可视化工具d3_前端3d可视化可视化工具D3教程第1章D3简介第2章第一个程序HelloWorld第3章正式进入D3的世界第4章选择、插入、删除元素第5章做一个简单的图表第6章比例尺的使用第7章坐标轴第8章完整的柱形图第9章让图表动起来第10章理解update()、enter()、exit()第11章交互式操作第12章布局第13章饼状图第14章力导向图第15章树状图第16章地图可视化学习D……

发表回复

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

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