热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

poj3261

MilkPatternsTimeLimit: 5000MSMemoryLimit: 65536KTotalSubmissions: 13249Accepted: 5894CaseT
Milk Patterns
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 13249   Accepted: 5894
Case Time Limit: 2000MS

Description

Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can‘t predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality.

To perform a rigorous study, he has invented a complex classification scheme by which each milk sample is recorded as an integer between 0 and 1,000,000 inclusive, and has recorded data from a single cow over N (1 ≤N ≤ 20,000) days. He wishes to find the longest pattern of samples which repeats identically at least K (2 ≤ K ≤ N) times. This may include overlapping patterns -- 1 2 3 2 3 2 3 1 repeats 2 3 2 3 twice, for example.

Help Farmer John by finding the longest repeating subsequence in the sequence of samples. It is guaranteed that at least one subsequence is repeated at least K times.

Input

Line 1: Two space-separated integers: N and K 
Lines 2..N+1: N integers, one per line, the quality of the milk on day i appears on the ith line.

Output

Line 1: One integer, the length of the longest pattern which occurs at least K times

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

4


二分答案
技术分享技术分享
#include
#include
#include
#define MN 200003
using namespace std;

int n,m;
int s[MN],a[MN];
int v[MN],sa[MN],q[MN],rank[MN],h[MN],mmh=0;
bool w[101];
inline void gr(int x){
    rank[sa[1]]=1;
    for (int i=2;i<=n;i++) rank[sa[i]]=(s[sa[i]]==s[sa[i-1]]&&s[sa[i]+x]==s[sa[i-1]+x])?rank[sa[i-1]]:rank[sa[i-1]]+1;
    for (int i=1;i<=n;i++) s[i]=rank[i];
}
inline void gv(){memset(v,0,sizeof(v));for (int i=1;i<=n;i++) v[s[i]]++;for (int i=1;i<=2e5;i++)v[i]+=v[i-1];}
inline void gsa(){
    gv();for (int i=n;i>=1;i--) sa[v[s[i]]--]=i;gr(0);
    for (int i=1;i1){
        gv();for (int j=n;j>=1;j--) if (sa[j]>i) q[v[s[sa[j]-i]]--]=sa[j]-i;
        for (int j=n-i+1;j<=n;j++) q[v[s[j]]--]=j;
        for (int j=1;j<=n;j++) sa[j]=q[j];gr(i);
        if (rank[sa[n]]==n) return;
    }
}
inline void gh(){for (int i=1,k=0,j;i<=n;h[rank[i++]]=k) for (k?k--:0,j=sa[rank[i]-1];a[i+k]==a[j+k]&&i+k<=n&&j+k<=n;k++);}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=a[i];
    gsa();gh();
    int l=0,r=n,mid,i,j,k,mmh;
    while(l<r){
        mid=(l+r+1)>>1;
        for (i=1,j,k=2;i<=n;i=k++){
            memset(w,0,sizeof(w));
            while (h[k]>=mid&&k<=n) k++;
            if (k-i>=m) break;
        }
        if (i<=n) l=mid;else r=mid-1;
    }
    printf("%d\n",l);
}
1668K 94MS G++ 1288B


 

poj 3261


推荐阅读
  • 深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准,旨在为第三方应用提供安全的用户资源访问授权,同时确保用户的账户信息(如用户名和密码)不会暴露给第三方。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 本文介绍了在Windows环境下使用pydoc工具的方法,并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外,还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 几何画板展示电场线与等势面的交互关系
    几何画板是一款功能强大的物理教学软件,具备丰富的绘图和度量工具。它不仅能够模拟物理实验过程,还能通过定量分析揭示物理现象背后的规律,尤其适用于难以在实际实验中展示的内容。本文将介绍如何使用几何画板演示电场线与等势面之间的关系。 ... [详细]
  • MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举(ENUM)类型字段所有可能取值的方法,帮助开发者更好地理解和利用这一数据类型。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 本文介绍如何在应用程序中使用文本输入框创建密码输入框,并通过设置掩码来隐藏用户输入的内容。我们将详细解释代码实现,并提供专业的补充说明。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文介绍如何使用 NSTimer 实现倒计时功能,详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器,确保在指定时间间隔内执行特定任务。 ... [详细]
  • 本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本,并进行数据处理和保存。 ... [详细]
  • MATLAB实现n条线段交点计算
    本文介绍了一种通过逐对比较线段来求解交点的简单算法。此外,还提到了一种基于排序的方法,但该方法较为复杂,尚未完全理解。文中详细描述了如何根据线段端点求交点,并判断交点是否在线段上。 ... [详细]
  • 高效解决应用崩溃问题!友盟新版错误分析工具全面升级
    友盟推出的最新版错误分析工具,专为移动开发者设计,提供强大的Crash收集与分析功能。该工具能够实时监控App运行状态,快速发现并修复错误,显著提升应用的稳定性和用户体验。 ... [详细]
author-avatar
琦琦蔡外_734
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有