Do geese see god?

Description

给一个字符串 $s$ 和一个整数 $k$ 。求所有最短的满足 $s$ 是他的一个子序列并且是一个回文串的字符串中字典序第 $k$ 大的。

Solution

令 $f[i][j]$ 表示 $s$ 中 $i$ 到 $j$ 所构成的字符串至少还要再添加几个字符使得其变成回文串。

令 $g[i][j]$ 表示满足最短的条件的前提下的添加字符的方案数。

这两个数组都可以通过简单的 $O(n^2)$ 的 dp 完成。

接下来便是求第 $k$ 大的字符串。如果 $k > g[1][n]$ 直接输出无解。接下来处理有解的情况。

solve(l, r, k) 表示从 $s_l$ 到 $s_r$ 构成的字符串满足添加字符最少的前提下所构成的字典序第 $k$ 大的回文串。

  • $l=r$ 时,直接返回 $s_l$

  • $s_l = s_r$ 时,返回 s[l] + solve(l + 1, r - 1, k) + s[r] (这里加法 = 按顺序拼接 = string 加法)

  • $s_l \not= s_r$ 时,我们有两种方法

    1. 把字符串变成 s[l] + solve(l + 1, r) + s[l] 即在后面添加一个 $s_l$ 并且把中间变成回文
    2. 把字符串变成 s[r] + solve(l, r - 1) + s[r] 即在前面添加一个 $s_r$ 并且把中间变成回文

    此时,我们显然会贪心的走字典序小的那一边,这取决于 $s_l$ 和 $s_r$ 的大小。

    不妨设 $s_l < s_r$ 那么如果 $g[l+1][r] >= k$ 我们就直接往第一种情况递归。否则把 $k$ 减掉 $g[l+1][r]$ 放到第二种情况递归。对于 $s_l > s_r$ 也是同理。

Code

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
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2005;
const int INF = (int)1e9;

int n; ll k;
char s[N]; int f[N][N]; ll g[N][N];

string solve(int l, int r, ll k) {
if(l > r) return "";
if(l == r) { string t = ""; t += s[l]; return t; }
if(s[l] == s[r])
return s[l] + solve(l + 1, r - 1, k) + s[r];
if(f[l + 1][r] < f[l][r - 1]) return s[l] + solve(l + 1, r, k) + s[l];
if(f[l + 1][r] > f[l][r - 1]) return s[r] + solve(l, r - 1, k) + s[r];
if(s[l] < s[r]) {
if(g[l + 1][r] >= k)
return s[l] + solve(l + 1, r, k) + s[l];
else return s[r] + solve(l, r - 1, k - g[l + 1][r]) + s[r];
} else {
if(g[l][r - 1] >= k)
return s[r] + solve(l, r - 1, k) + s[r];
else return s[l] + solve(l + 1, r, k - g[l][r - 1]) + s[l];
}
}

int main() {
scanf("%s %lld", s + 1, &k); n = strlen(s + 1);
for(int i = 1; i <= n; i++) f[i][i] = 0, g[i][i] = 1;
for(int l = 2; l <= n; l++) {
for(int i = 1; i <= n - l + 1; i++) {
if(l == 2) {
if(s[i] == s[i + 1]) { f[i][i + 1] = 0, g[i][i + 1] = 1; }
else { f[i][i + 1] = 1; g[i][i + 1] = 2; }
continue ;
}
int L = i, R = (i + l - 1);
int mn = INF;
if(s[L] == s[R]) {
f[L][R] = f[L + 1][R - 1];
g[L][R] = g[L + 1][R - 1];
continue ;
}
mn = min(mn, 1 + min(f[L][R - 1], f[L + 1][R]));
f[L][R] = mn;
if(mn == f[L + 1][R] + 1) {
g[L][R] += g[L + 1][R];
}
if(mn == f[L][R - 1] + 1) {
g[L][R] += g[L][R - 1];
}
if(g[L][R] > k) g[L][R] = k + 1;
}
}
if(k > g[1][n]) { puts("NONE"); return 0; }
cout << solve(1, n, k) << endl;
return 0;
}