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