题解：P12990 [GCJ 2022 #1C] Letter Blocks

· · 题解

考试题，写一篇题解加深印象。

思路

这题的关键是：最终超级塔里，每种字母必须连续出现。所以一个塔如果压缩相邻相同字母后，同一个字母出现了两次，那这个塔自己就废了，直接 IMPOSSIBLE。

把每个字符串压缩成“相邻去重”的序列，比如 AABBA 变成 ABA。压缩后长度只有 1 的塔，叫纯字母塔，它只含一种字母，可以塞到该字母所在组的任意位置。

对于压缩后长度 \ge 2 的塔，它规定了字母之间的先后关系。比如 CODE 压缩后是 CODE，就说明 C 后面必须接 O，O 后面接 D，等等。于是我们建一张字母图：相邻字母连边。因为最终每种字母只能有一个连续段，所以每个字母的出边、入边都最多只能有一个，否则就冲突。

同时统计每个字母作为“首字母”“尾字母”“中间字母”的次数。一个字母不能既当中间字母又当端点或纯字母；首字母和尾字母也各自最多出现一次。这些检查代码里都做了。

建完图后，合法的图应该是一堆链，不能有环。代码从没有前驱的字母出发沿出边走并标记，最后如果还有带出边却没被标记的字母，说明存在独立环，判无解。

最后拼接答案：对每条链，从起点一路走，每到一个字母，先把该字母的所有纯字母塔拼上，再补上这个字母在非纯塔里出现的总次数。纯链（整条链上的字母都没在非纯塔里出现过）放前面，其余链放后面，直接拼起来就是答案。

复杂度是 O(\sum |s| + V) 其中 V = 26，非常小。

核心代码

拼接部分就是：

for (int st : sts) {
  string pt;
  int cur = st;
  while (true) {
    for (auto &t : pur[cur]) pt += t;
    pt += string(oc[cur], 'A' + cur);
    if (nx[cur] == -1) break;
    cur = nx[cur];
  }
  if (ipc(st)) pp.push_back(pt);
  else oth.push_back(pt);
}