Processing math: 100%


Do geese see god?

Description

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

Solution

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

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

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

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

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

  • l=r 时,直接返回 sl

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

  • slsr 时,我们有两种方法

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

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

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

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;
}