文档章节

【bzoj1717】Milk Patterns 后缀数组 + (二分||单调队列)

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 394
阅读 11
收藏 0

这题看完之后想用单调队列……结果调了一个下午……
DQS学长看了几秒钟之后说是可以二分……
然后……
OrzOrzOrz

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 100000 + 5;
int sa[MAXN],rank[MAXN],tmp[MAXN];
int n,m,k;
int c[MAXN];
bool cmp_sa(int a,int b)
{
    if(rank[a] != rank[b])
        return rank[a] < rank[b];
    else
    {
        int x = a + k <= n ? rank[a + k] : -1;
        int y = b + k <= n ? rank[b + k] : -1;
        return x < y;
    }
}
void make_sa(int s[])
{
    for(int i = 0;i <= n;i ++)
    {
        rank[i] = i < n ? s[i] : -1;
        sa[i] = i;
    }
    for(k = 1;k <= n;k <<= 1)
    {
        sort(sa,sa + n + 1,cmp_sa);
        tmp[sa[0]] = 0;
        for(int i = 1;i <= n;i ++)
            tmp[sa[i]] = tmp[sa[i - 1]] + cmp_sa(sa[i - 1],sa[i]);
        for(int i = 0;i <= n;i ++)
            rank[i] = tmp[i];
    }
    return;
}
int lcp[MAXN];
void make_lcp(int s[])
{
    for(int i = 1;i < n;i ++)
        rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for(int i = 0;i < n;i ++)
    {
        int j = sa[rank[i] - 1];
        if(h)
            h--;
        for(;i + h < n,j + h < n;h ++)
            if(s[i + h] != s[j + h])
                break;
        lcp[rank[i] - 1] = h;
    }
    return;
}
bool can(int x)
{
    int ans = 0,num = 0;
    for(int i = 1;i <= n;i ++)
    {
        num = (num + 1) * (lcp[i] >= x);
        ans = max(num,ans);
    }
    return ans >= m - 1;
}
int div()
{
    int ans;
    int l = 1,r = n;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(can(mid))
            ans = mid,l = mid + 1;
        else
            r = mid - 1;
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 0;i < n;i ++)
        scanf("%d",&c[i]);
    make_sa(c);
    make_lcp(c);
    printf("%d\n",div());
    return 0;
}

D(y)Q(d)S(c):“一般后缀数组或者高度数组都是套个二分什么的,把lcp数组切成一块一块的之后就可以简单的验证了……”
%%%

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
poj3261 Milk Patterns【二分答案+后缀数组】

题目大意: 给定一个长度为n的数字串,问可重叠至少出现k次的最长重复子串的长度。 解题思路: 做法有很多,比如二分+哈希+map(或哈希表)就比较清新,这里说说后缀数组的做法。 建立后缀数组...

cdsszjj
2018/01/28
0
0
Codeforces 762C Two strings

• 给定两个字符串A,B • 再B中删除最少的连续字符(一段字符),使得B成为A的子序列 • 1 ≤ |A|, |B| ≤ 1e5 二分+预处理前缀和后缀 题目大意: 给定两个字符串a,b(len≤105),让你去b中的一个...

阿豪boy
2017/08/15
11
0
ACM程序设计大赛题目分类

第一类:基础算法 (1) 基础算法:枚举,贪心,递归,分治,递推,构造,模拟 (2) 动态规划:背包问题,树形dp,状态压缩dp,单调性优化,插头dp (3) 搜索:dfs,bfs,记忆化搜索,优化...

齐勇cn
2016/04/20
185
0
12.8~12.9题解

今天主要写一下题解,总结待整理好后另开一篇发表(大约是明天)。 题面见各大OJ。本次题解都是讨论对于已经列好的DP方程的优化。 【HDU3401】 单调队列优化要求参数分离和枚举区间单调。对于...

myjs999
2017/12/10
0
0
2019CCPC网络赛 C - K-th occurrence HDU - 6704(后缀数组+ST表+二分+主席树)

题意 求区间l,r的子串在原串中第k次出现的位置。 链接:https://vjudge.net/contest/322094#problem/C 思路 比赛的时候用后缀自动机写的,TLE到比赛结束。 学了后缀数组后,发现这题用后缀数...

swineherd_MCQ
09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

用原生js对表格排序

本文转载于:专业的前端网站➸用原生js对表格排序 阿里的模拟笔试题,当时时间有限没写出来,其实是因为自己对原生dom操作不熟悉,这里补一下。 题目的大意是有一个表格,如代码所示 <table>...

前端老手
12分钟前
2
0
IT兄弟连 HTML5教程 HTML5表单 HTML5新增表单元素

HTML5有一些新的表单元素:<datalist>、<keygen>、<output>。不是所有的浏览器都支持HTML5新的表单元素,但即使浏览器不支持该表单属性,仍然可以显示为常规的表单元素。 1 <datalist>元素 ...

老码农的一亩三分地
14分钟前
2
0
【朝花夕拾】Android自定义View篇之(一)View绘制流程

https://www.cnblogs.com/andy-songwei/p/10955062.html

shzwork
16分钟前
3
0
Qt编写自定义控件70-扁平化flatui

一、前言 对于现在做前端开发人员来说,FlatUI肯定不陌生,最近几年扁平化的设计越来越流行,大概由于现在PC端和移动端的设备的分辨率越来越高,扁平化反而看起来更让人愉悦,而通过渐变色产...

飞扬青云
25分钟前
1
0
教你玩转Linux—添加批量用户

添加和删除用户对每位Linux系统管理员都是轻而易举的事,比较棘手的是如果要添加几十个、上百个甚至上千个用户时,我们不太可能还使用useradd一个一个地添加,必然要找一种简便的创建大量用户...

Linux就该这么学
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部