2021 ICPC 沈阳 G. Encoded Strings II

Wings 收录于类别 ACM

2022-02-16 2022-02-16 约 1811 字预计阅读 4 分钟次阅读条评论

怎么有人半年后才补题的啊…

对字符串 $s$, 函数 $F_s(c) = chr(G(c, s))$. 其中, $c$ 表示字符串 $s$ 中的字符, $chr(i)$ 表示第 $i+1$ 个小写字母, $G(c, s)$ 表示字符串 $s$ 中最右边的 $c$ 之后不同字母的个数. 给出一个长度为 $n$ 的字符串 $s$, 对于所有非空子序列 $s_0$, 将 $s_0$ 中的字符替换 $s_{0i}$成 $F_{s_0}(s_{0i})$, 得到共 $2^{|s|} - 1$ 个新的字符串. 输出其中字典序最大的字符串.

$1 \le n \le 1000$, $\Sigma = \{a, b, \dots t\}$ ($|\Sigma| = 20$)

不知道从什么地方下手, 尝试先分析答案的性质. 这也是一个普遍的做法.

先做一个非常平凡的转换, 把选择最大的 $F_{s_0}$ 转换为选择 $s_0$ 使得 $F_{s_0}$ 最大. 那么问题就变成了, 我们要选的子序列是什么样子的. 手玩一下, 可以发现, 子序列一定包含了所有字母, 只有这样, $F_{s_0}$ 的第一个字母才是最大的, 才能够让字典序最大.

接下来手玩可以发现, 第一位接着往后, 相同的字母应该是要连续的. 因为如果不连续, 可以把中间更小的删掉, 让相同的往前提, 拼成连续的, 这样字典序会更大.

再接下来的字母, 要么和之前相同, 要么比之前小 $1$. 如果不是小 $1$, 而是小更多, 就说明之后有比他小 $1$ 的字母出现, 那么把他删掉会更好.

于是, 可以归纳证明到, 答案是单调不递增的字典序最大的序列.

这样, 问题就变成了, 选一个子序列 $s_0$, 满足每个字母都选上, 且第一个字母的数量尽量多, 然后第二个字母的数量尽量多…… 以此类推.

选择的字母顺序不能马上确定, 而字母数量只有 $20$, 所以考虑状压 DP. 设 $dp(S)$ 为从前往后, 包含集合 $S$, 且选出来的字母满足上述条件, 最小的边界位置 (因为要给后续的字母更多的可能性, 所以是最小位置). 这样, 区间 $(dp(S - \{x\}), dp(S)]$ 中的所有 $x$ 都被选上(假设 $x$ 是最优决策点). 于是我们需要记录最优决策点, 才知道怎么选. 转移的时候, 希望 $x$ 的数量越多越好. 但是, 如果跑太远, 可能把某一个字母全部删掉了, 这不是想要的结果. 所以再预处理一个类似的 $f(T)$, 表示从后往前, 包含集合 $T$ 的最大边界位置 (因为从后往前, 所以是最大, 给 $x$ 数量更多的可能性). 这个 $f$ 不是和 $dp$ 对称的, 因为它不需要满足条件, 并且这个 $f$ 非常好求.

在转移的过程中, 枚举 $x \in S$, 区间 $(dp(S - \{x\}), f(\bar S))$, 就是可以选 $x$ 的区间 (如果 $dp(S - \{x\})$ 存在, 或者说, 可以用来转移, 这一点很重要). 我们希望选的数量越多越好, 所以需要预处理每个字母在任意区间的数量 $cnt(x, l, r)$, 这里对每个字母求一个前缀和就可以解决. 如果数量相等, 那就选最后一个位置最小的, 因为要给后面选的字母更多可能性. 所以还要预处理一下, 每个字母最后一个不超过 $r$ 的位置, 记为 $pos(x, r)$. 这样, 我们就可以根据 $cnt(x, dp(S - \{x\} + 1, f(\bar S) - 1))$ 为第一关键字, $pos(x, r)$ 为第二关键字, 找到最优决策点, 记录并转移 $dp(S) = pos(x, r)$.

由于我们是由上一个尽量大转移来的, 而我们上述讨论的 dp 过程, 需要非常注意 $dp(S - \{x\})$ 是否可以用来转移. 也就是说, $dp(S - \{x\})$ 在它自己的 dp 过程中, 有没有选最多的 $y$. 如果不是, 那么它用来转移, 可能会导致, 当前 dp 过程求得到最大数量更多, (或者位置更小), 导致错误.

所以在按 $|S|$ 从小到大枚举的过程中, 枚举完了某一个数量, 要记录这个字母选取的最大数量是多少. 然后下一次循环中, 要判断 $dp(S \{x\})$ 选取 $x$ 的数量是否是最多的. 如果不是, 则不能转移.

我写的代码是枚举完一个数量之后, 把不是最大数量的 dp 值设为不存在, 从而避免转移.

最后根据最优决策点随便处理答案即可.

复杂度 $O(|\Sigma|2^{|\Sigma|} + n|\Sigma|)$.

 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


int n, m, a[MAXN];
int sum[MAXA][MAXN], pos[MAXA][MAXN];
char str[MAXN];
int f[MAXS], dp[MAXS], path[MAXS], dpcnt[MAXS];
map<char, int> id;
VI S[MAXA];

int count(int s) {
  int res = 0;
  while (s)
    s ^= lowbit(s), res++;
  return res;
}

int cnt(int x, int l, int r) {
  if (l > r)
    return 0;
  return sum[x][r] - sum[x][l - 1];
}

int main() {
  scanf("%d%s", &n, str + 1);
  for (int i = 1; str[i]; i++)
    a[i] = (id[str[i]] ? id[str[i]] : id[str[i]] = ++m) - 1;
  for (int x = 0; x < m; x++)
    for (int i = 1; i <= n; i++)
      sum[x][i] += sum[x][i-1] + (a[i]==x);
  for (int x = 0; x < m; x++)
    for (int i = 1; i <= n; i++)
      pos[x][i] = a[i] == x ? i : pos[x][i-1];
  for (int s = 0; s < 1 << m; s++)
    S[count(s)].emplace_back(s);
  f[0] = n + 1;
  for (int s = 1; s < 1 << m; s++) {
    int cur = 0;
    for (int i = n; i; i--) {
      cur |= 1 << a[i];
      if ((s | cur) == cur) {
        f[s] = i;
        break;
      }
    }
  }
  memset(dp, INTINF, sizeof(dp));
  dp[0] = 0;
  for (int c = 1; c <= m; c++) {
    int mx = 0;
    for (int s : S[c]) {
      int mx_cnt = 0;
      int p = -1;
      for (int x = 0; x < m; x++) if (((1 << x) | s) == s) {
        int ss = s ^ (1 << x);
        if (dp[ss] >= INTINF)
          continue;
        int t = ((1 << m) - 1) ^ s;
        int l = dp[ss] + 1, r = f[t] - 1;
        if (pos[x][r] <= dp[ss])
          continue;
        int cur_cnt = cnt(x, l, r);
        if (cur_cnt > mx_cnt)
          dp[s] = pos[p = x][r], mx_cnt = cur_cnt;
        else if (cur_cnt == mx_cnt && dp[s] > pos[x][r])
          dp[s] = pos[p = x][r];
      }
      path[s] = p;
      dpcnt[s] = mx_cnt;
      mx = max(mx, dpcnt[s]);
    }
    for (int s : S[c])
      if (dpcnt[s] < mx)
        dp[s] = INTINF;
  }
  int s = (1 << m) - 1;
  int c = 'a';
  while (s) {
    int p = path[s];
    int ss = s ^ (1 << p);
    for (int i = dp[ss] + 1; i <= dp[s]; i++)
      a[i] = a[i] == p ? c : a[i];
    s = ss;
    c++;
  }
  for (int i = 1; i <= n; i++)
    if (islower(a[i]))
      printf("%c", a[i]);
  puts("");
  return 0;
}