#P4310. 跳蚤

    ID: 3526 传统题 1000ms 512MiB 尝试: 1610 已通过: 445 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案后缀数组Kasai 算法LCP+RMQST 表一维前缀和二分查找交换论证倍增计数排序

跳蚤

题目描述

很久很久以前,森林里住着一群跳蚤。一天,跳蚤国王得到了一个神秘的字符串,它想进行研究。

首先,他会把串分成不超过 kk 个子串,然后对于每个子串 SS,他会从 SS 的所有子串中选择字典序最大的那一个,并在选出来的 kk 个子串中选择字典序最大的那一个。他称其为“魔力串”。

现在他想找一个最优的分法让“魔力串”字典序最小。

输入格式

第一行一个整数 kk。

输出格式

输出一行,表示字典序最小的“魔力串”。

13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba
cbc

数据规模与约定

对于 100%100\% 的数据,1≤k≤∣S∣≤1051\leq k\leq |S|\leq 10^5。