BZOJ4310 : 跳蚤

首先求出后缀数组,得到本质不同的子串的个数。

然后二分答案,每次先通过后缀数组求出第$mid$小的子串,然后贪心进行检验。

检验的时候,从后往前贪心,每次加入一个后缀,如果不能加了,那就划为一段。

时间复杂度$O(n\log n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long ll;
char s[N];
int K,n,i,j,rk[N],sa[N],height[N],tmp[N],cnt[N],Log[N],f[16][N],g[N];
ll L=1,R,mid;
int len,nowl,nowr,ansl,ansr;
void suffixarray(int n,int m){
  int i,j,k;n++;
  for(i=0;i<n;i++)cnt[rk[i]=s[i]]++;
  for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
  for(i=0;i<n;i++)sa[--cnt[rk[i]]]=i;
  for(k=1;k<=n;k<<=1){
    for(i=0;i<n;i++){
      j=sa[i]-k;
      if(j<0)j+=n;
      tmp[cnt[rk[j]]++]=j;
    }
    sa[tmp[cnt[0]=0]]=j=0;
    for(i=1;i<n;i++){
      if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])cnt[++j]=i;
      sa[tmp[i]]=j;
    }
    memcpy(rk,sa,n*sizeof(int));
    memcpy(sa,tmp,n*sizeof(int));
    if(j>=n-1)break;
  }
  for(j=rk[height[i=k=0]=0];i<n-1;i++,k++)
    while(~k&&s[i]!=s[sa[j-1]+k])height[j]=k--,j=rk[sa[j]+1];
}
inline int lcp(int x,int y){
  if(x==y)return n-x;
  x=rk[x],y=rk[y];
  if(x>y)swap(x,y);
  int k=Log[y-x];
  return min(f[k][x+1],f[k][y-(1<<k)+1]);
}
void kth(ll k){
  ll s=0;
  for(int i=1;i<=n;s+=n-sa[i]-height[i],i++)if(s+n-sa[i]-height[i]>=k){
    nowl=sa[i],nowr=nowl+height[i]+k-s-1;
    len=nowr-nowl+1;
    return;
  }
}
inline bool ask(int l,int r){
  int t=min(lcp(l,nowl),min(r-l+1,len));
  if(t==r-l+1&&t<=len)return 1;
  if(t==len)return 0;
  return s[l+t]<=s[nowl+t];
}
bool check(){
  int i,j,k=0;
  for(i=n-1;~i;i=j,k++){
    for(j=i;~j;j--)if(!ask(j,i))break;
    if(j==i)return 0;
  }
  return k<=K;
}
int main(){
  scanf("%d%s",&K,s);
  n=strlen(s);
  suffixarray(n,128);
  for(i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
  for(i=1;i<=n;i++)f[0][i]=height[i];
  for(j=1;j<17;j++)for(i=1;i+(1<<j-1)<=n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);
  for(i=1;i<=n;i++)R+=n-sa[i]-height[i];
  while(L<=R){
    kth(mid=(L+R)>>1);
    if(check())ansl=nowl,ansr=nowr,R=mid-1;else L=mid+1;
  }
  for(i=ansl;i<=ansr;i++)putchar(s[i]);
  return 0;
}

  

时间: 01-08

BZOJ4310 : 跳蚤的相关文章

目前的字符串

Aho-Corasick automaton:BZOJ4820[bzoj2754][SCOI2012]喵星球上的点名后缀数组:BZOJ4310 跳蚤manacher: BZOJ3160万径人踪灭Palindromic Tree:bzoj4044Bzoj3676:[Apio2014]回文串 bzoj 1559 ** ac+jvchengBZOJ1195:[HNOI2006]最短母串 ** ac+jvchengbzoj 1692 * sabzoj 1031 * sabzoj 3796 ** sa+k

字符串题表

已完成bzoj1559 ** ac+jvchengbzoj1195:[HNOI2006]最短母串 ** ac+jvchengbzoj1692 * sabzoj1031 * sabzoj3796 ** sa+kmpbzoj3230:相似子串 ** sa+stbzoj4698 *** sabzoj2160:拉拉队排练 * manacherbzoj3790 * manacher+tanxinbzoj2565:最长双回文串 * manacher+luangaobzoj1414:[ZJOI2009]对称的

【bzoj4310】跳蚤 后缀数组+二分

题目描述 很久很久以前,森林里住着一群跳蚤.一天,跳蚤国王得到了一个神秘的字符串,它想进行研究. 首先,他会把串分成不超过 k 个子串,然后对于每个子串 S,他会从S的所有子串中选择字典序最大的那一个,并在选出来的 k 个子串中选择字典序最大的那一个.他称其为“魔力串”. 现在他想找一个最优的分法让“魔力串”字典序最小. 输入 第一行一个整数 k. 接下来一个长度不超过 105 的字符串 S. 输出 输出一行,表示字典序最小的“魔力串”. 样例输入 13 bcbcbacbbbbbabbacbcb

[HNOI2002]跳蚤

题目描述 Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正中央.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有N+1个自然数.其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字.跳蚤每次可以从卡片上任意选择一个自然数S,然后向左,或向右跳S个单位长度.而他最终的任务是跳到距离他左边一个单位长度的地方,并捡起位于那里的礼物. 比如当N=2,M=18时,持有卡片(10, 15, 18)的跳蚤,就可以完成任务:他可以先向左

bzoj 4310: 跳蚤

Description 很久很久以前,森林里住着一群跳蚤.一天,跳蚤国王得到了一个神秘的字符串,它想进行研究. 首先,他会把串分成不超过 k 个子串,然后对于每个子串 S,他会从S的所有子串中选择字典序最大的那一个,并在选出来的 k 个子串中选择字典序最大的那一个.他称其为"魔力串". 现在他想找一个最优的分法让"魔力串"字典序最小. Input 第一行一个整数 k. 接下来一个长度不超过 105 的字符串 S. Output 输出一行,表示字典序最小的"

小JAVA大世界之程序建模跳蚤实验

package com.chigoe;//房子类class House { private int m;// 保存行数 private int n;// 保存列数 private int[][] a; public House() { // 无参构造方法 m = 10; n = 10; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { a[i][j] = 0; } } public House(int m,int n){//带参

[BZOJ1220][POJ1091][HNOI2002]跳蚤

试题描述 Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正中央.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有N+1个自然数.其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字.跳蚤每次可以从卡片上任意选择一个自然数S,然后向左,或向右跳S个单位长度.而他最终的任务是跳到距离他左边一个单位长度的地方,并捡起位于那里的礼物.比如当N=2,M=18时,持有卡片(10, 15, 18)的跳蚤,就可以完成任务:他可以先向左跳

POJ 1091 跳蚤

   Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 9914   Accepted: 3032 Description Z 城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正中央.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤 发一张卡片.卡片上写有N+1个自然数.其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字.跳蚤每次可以从卡片上任意选择一个自然数S, 然后向左

POJ 1091 跳蚤(分解质因数 + 容斥 + 大数)

跳蚤 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 8910   Accepted: 2676 Description Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正中央.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有N+1个自然数.其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字.跳蚤每次可以从卡片上任意选择一个自然数S,然后向左,或向