引理 $1$ ：优先加入符合要求的最长子串。（把后一个子串的前缀拿过来显然不劣）
到这里其实就差不多了，子串显然能够想到那个算法：SAM 。
如果给你一个字符串，怎么求出其的最小操作数呢？显然是拉上 SAM 上跑一遍，现在要我们确定一个最小操作数为 $x$ 的字符串，显然也是在 SAM 上 DP 一下就行了。
如果没有字典序的约束，这道题目就是：$dp[i][j]k$ 表示是否存在一个方案满足终止位置 SAM 上的第 $i$ 个节点，目前长度为 $j$ ，已经有了 $k$ 段，然后直接转移就行了。
但是因为我赛时分析错了复杂度，以为是四次方的，就没有往下接着想了，但实际上是三次方的。
显然时间复杂度是：$O(26nmx)$ ，而且如果实现的足够精妙能够到达 $O(nmx)$ ，因为考虑固定 $j,k$ ，这样对于 $i$ 的转移分两种，跑存在的边（ SAM 边的数量级是 $O(n)$ 的），跑不存在的边（可以状压，也可以调整搜索顺序，优先跑 $26$ ，然后去找可行且不能到达的状态（因此需要提前把可行的状态记录一下））。
但是如果要求字典序最小的字符串呢？
显然，我们必须要查询对于一个前缀，是否存在满足要求的答案，为此，我们不妨考虑整个字符串是倒着加子串的，然后把 $A$ 翻转，反着跑一遍 $DP$ ，然后枚举刚好跑到前缀时位于哪个点，然后继续扔到后缀数组上跑，看看能否凑出一个 $X$ 段出来。
时间复杂度：$O(26nmx)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
#define N 310
#define M 160
using namespace std;
struct node{
int a[26],len,fa;
}tr[N];int tot,last;
char st[M];int n;
void add(int c){
int p=last;int np=last=++tot;
tr[np].len=tr[p].len+1;
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;
if(!p)tr[np].fa=1;
else{
int q=tr[p].a[c];
if(tr[q].len==tr[p].len+1)tr[np].fa=q;
else{
int nq=++tot;
tr[nq].fa=tr[q].fa;tr[q].fa=nq;
tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));
tr[np].fa=nq;
for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;
}
}
}
bool dp[N][M][M];
int m,X;char ans[M];int fuck;
int getval(int x,int fucklen){
int cnt=1;
for(int i=fucklen;i>=1;i--){
if(tr[x].a[ans[i]-'a'])x=tr[x].a[ans[i]-'a'];
else x=tr[1].a[ans[i]-'a'],cnt++;
}
return cnt;
}
bool v[40];
bool work(){
if(fuck!=m){
for(int i=2;i<=tot;i++){
int x=getval(i,fuck);
if(x<=X && dp[i][m-fuck][X-x+1])return 1;
}
return 0;
}
else return getval(tr[1].a[ans[m]-'a'],m-1)==X;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&X);
scanf("%s",st+1);
tot=last=1;memset(tr,0,sizeof(tr));memset(v,0,sizeof(v));
for(int i=1;i+i<=n;i++)swap(st[i],st[n-i+1]);
for(int i=1;i<=n;i++)add(st[i]-'a'),v[st[i]-'a']=1;
for(int i=0;i<=25;i++){
if(tr[1].a[i])dp[tr[1].a[i]][1][1]=1;
}
for(int i=1;i<m;i++){
for(int j=2;j<=tot;j++){
for(int t=1;t<=i && t<=X;t++){
if(!dp[j][i][t])continue;
for(int k=0;k<=25;k++){
if(tr[j].a[k])dp[tr[j].a[k]][i+1][t]=1;
else if(tr[1].a[k] && t<X)dp[tr[1].a[k]][i+1][t+1]=1;
}
}
}
}
bool bk=0;
for(int i=1;i<=tot;i++)bk|=dp[i][m][X];
if(!bk){
for(int i=1;i<=tot;i++)memset(dp[i],0,sizeof(dp[i]));
printf("-1\n");continue;
}
for(int i=1;i<=m;i++){
fuck=i;
for(int j=0;j<=25;j++){
if(!v[j])continue;
ans[i]=j+'a';
if(work()==1)break;
}
}
ans[m+1]='\0';printf("%s\n",ans+1);
for(int i=1;i<=tot;i++)memset(dp[i],0,sizeof(dp[i]));
}
return 0;
}
|
官方做法：
不得不说这应该是经典 trick 但是我忘了，在遇到 DP + 字符串 + 字典序最小就应该马上意识过来才对。
简单来说，用 BFS 更新 DP 状态，这样只要更新出了最终状态那么这条更新路径就是答案，而且不止最终状态，准确来说对于每个状态其的更新路径都是字典序最小的路径。（那这样是不是 DFS 也可以啊，只要加个记忆化就行了，本质应该是一样的）
原因：队列中对于两个长度相等的状态，一定满足更新路径字典序小的在前面，大的在后面，同时只要前面符合这种情况，后面也一定符合这种情况，想想就知道了，挺有意思的，
队友的做法：
赛后讨论了一下，他的做法是正着做，反过来标记每个状态如果要到达最终状态的最优决策是什么（实际上只要处理出能否到达最终状态就行了），然后在正着处理出答案。
然而，我突然发现，实际上倒着跑就可以只跑两遍了，先倒着跑一遍 DP ，处理出每个位置的最优，然后正着跑出结果就行了。 (错误原因：一个点可能有多个点走同一个字符的边转移过来，因此无法在常数的时间判断出来哪个是最优决策)
同机房同学的做法：
非常的有意思，我只能说不愧是他，A不了，但是可以看一下。
观察发现实际上会出问题当且仅当某个子串的下一个位置和下一个子串的首位置相等，所以一个操作次数 $≥2$ 的子串的某个前缀一定是由一个子串+某个字符构成的（且这个前缀不是一个子串），不妨考虑处理出所有这样的字符串（最多 $26n^2$ 个），然后排序，可以发现，这样的字符串具有一个性质，不存在一个字符串是另外一个字符串的前缀，这个性质后面有用。
然后设 $f[i][j][k]$ 表示长度为 $j$ ，首字母为 $i$ ，最小操作次数为 $k$ 的最小字典序的字符串（其实也不需要保留字符串，保留转移就行了）。
这样，转移的时候只需要从小到达遍历前面那个字符串，能转移就转移，不难发现这就是最优的决策。
但是仔细计算一下复杂度是 $O(26^2nmx)$ ，非常遗憾不能通过此题，但是我个人感觉这个思想非常的有意思，所以就把它给记录下来了，而且也很有启示意义，就是很多时候可以尝试一下脱离算法思考，可以发现这个方法并不依赖任何字符串算法，却得到了一个非常有意思的方法（这个老哥就是这个想法的忠实拥护者，不怎么学算法，坚信大部分题目都是可以用思维解决，所以他的思维就非常的厉害）。
听说同机房还有基于字典树和 bitset 优化的四方做法过了，厉害厉害。
