题意翻译
给出一个长度为 \(n\) 的字符串 \(S\) 以及整数 \(m,k\)。 对于一个把 \(S\) 分割成非空的 \(m\) 段的一个方案，我们用这个方案中分割出的字典序最小的一个串代表这个分割方案。 eg. \(S=abaabb,m=3\)，存在分割方案 \(\{ab,aab,b\}\)，则我们用字典序最小的 \(aab\) 来代表这个分割方案。 现在把所有分割方案对应的代表该方案的串按字典序从大到小排序，求排序后的第 \(k\) 个串。
题目描述
VK just opened its second HQ in St. Petersburg! Side of its office building has a huge string $ s $ written on its side. This part of the office is supposed to be split into $ m $ meeting rooms in such way that meeting room walls are strictly between letters on the building. Obviously, meeting rooms should not be of size 0, but can be as small as one letter wide. Each meeting room will be named after the substring of $ s $ written on its side. 
For each possible arrangement of $ m $ meeting rooms we ordered a test meeting room label for the meeting room with lexicographically minimal name. When delivered, those labels got sorted backward lexicographically. What is printed on $ k $ th label of the delivery?
输入输出格式
输入格式
In the first line, you are given three integer numbers $ n, m, k $ — length of string $ s $ , number of planned meeting rooms to split $ s $ into and number of the interesting label ( $ 2 \le n \le 1,000; 1 \le m \le 1,000; 1 \le k \le 10^{18} $ ). Second input line has string $ s $ , consisting of $ n $ lowercase english letters. For given $ n, m, k $ there are at least $ k $ ways to split $ s $ into $ m $ substrings.
输出格式
Output single string – name of meeting room printed on $ k $ -th label of the delivery.
输入输出样例
输入样例 #1
4 2 1
abac
输出样例 #1
aba
输入样例 #2
19 5 1821
aupontrougevkoffice
输出样例 #2
au
说明
In the first example, delivery consists of the labels "aba", "ab", "a". In the second example, delivery consists of $ 3060 $ labels. The first label is "aupontrougevkof" and the last one is "a".
SOLUTION
首先我们可以将s的所有子串排一个序，然后二分，check每个mid：
-
将s划分，其中每段都大于mid，看划分成m段的方案数是否大于等于k
-
由于mid越大，划分的段数越少，证明了其单调性，可以二分
第一个问题是怎么排序
我们应该可以知道用lcp可以解决这个问题
lcp指的是两个后缀的最长前缀
\(lcp(i,j)\)：\(s[i,n]\)和\(s[j,n]\)的最长前缀的长度
我们可以这样写：
bool operator<(node x,node y){
ll lp=lcp[x.l][y.l];
if(lp>=x.r-x.l+1||lp>=y.r-y.l+1){
//如果两串中至少有一个是小于等于lcp的，说明一个是另一个的前缀，那么比较长度即可
return x.r-x.l+1<y.r-y.l+1;
}
//否则比较lcp的后一位（这一位必然不相等）
return s[x.l+lp]<s[y.l+lp];
}
这样就可以\(O(nlogn)\)排序了
接下来的问题就是如何check了
比较显然是一个dp，但是怎么d呢？
我们可以设\(dp_{i,j}\)表示\(s[i,n]\)划分为\(j\)段的方案数
\[dp_{i,j}=\sum_{(i≤t)and(s[i,t]>S)}dp_{t+1,j-1} \]由于若\(s[i,t]>S\)，那么\(s[i,t+1]\)肯定也大于\(S\)
所以我们可以倒着dp，然后存\(dp\)的后缀，\(dp\)方程就变成了
\[dp_{i,j}=d_{t,j-1},其中t为满足s[i,t]>S的最小t \]CODE
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e3+2;
char s[N];
ll n,m,k,dp[N][N],lcp[N][N],d[N][N],cnt;
struct node{
ll l,r;
}a[N*N];
bool operator<(node x,node y){
ll lp=lcp[x.l][y.l];
if(lp>=x.r-x.l+1||lp>=y.r-y.l+1){
//如果两串中至少有一个是小于等于lcp的，说明他们前面的部分都是一样滴，那么比较长度即可
return x.r-x.l+1<y.r-y.l+1;
}
//否则比较lcp的后一位（这一位必然不相等）
return s[x.l+lp]<s[y.l+lp];
}
bool check(ll p){
memset(dp,0,sizeof(dp));
memset(d,0,sizeof(d));
d[n+1][0]=1;//d是dp的后缀
ll len=a[p].r-a[p].l+1;
for(ll i=n;i>=1;i--){
ll t=min(len,lcp[a[p].l][i]);//第一个满足s[i,t]>S的t
if(t==len||s[i+t]>s[a[p].l+t]){//s[i,n]>S
for(ll j=1;j<=m;j++){
dp[i][j]=d[i+t+1][j-1];
}
}
for(ll j=0;j<=m;j++){
d[i][j]=min(d[i+1][j]+dp[i][j],k);
}
}
return dp[1][m]>=k;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
scanf("%s",s+1);
for(ll i=n;i>=1;i--){
for(ll j=n;j>=1;j--){
if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
else lcp[i][j]=0;
}
}
for(ll i=1;i<=n;i++){
for(ll j=i;j<=n;j++){
a[++cnt]={i,j};
}
}
sort(a+1,a+1+cnt);
ll l=1,r=cnt;
while(l<=r){//二分第k个
ll mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
}else{
r=mid-1;
}
}
for(int i=a[l].l;i<=a[l].r;i++){
printf("%c",s[i]);//输出
}
return 0;
}
完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。
标签：le,lcp,Pont,ll,mid,CF1310C,Au,meeting,dp From： https://www.cnblogs.com/Aurora1217/p/16725826.html