4

问题如下。

  1. 关于“好”

    1）“ab”很好

    2) A 很好 => "a"+A+"b" 很好

    3) A 和 B 很好 => A+B 很好

  2. 关于“~”

    1) "ab"~"ab"

    2) A~B => "a"+A+"b"~"a"+B+"b"

    3) A~B 和 C~D => A+C~B+D 和 A+C~D+B

现在最多有 1000 串 'a' 和 'b' 形成一个集合 S，找到 S 的最大子集，其中每个元素都必须是好的，并且对 (A,B) 中的任何一个都不包含 A~B。输出基数。

与我之前看到的问题有些不同：A+B+C+D~A+C+B+D~B+D+A+C 但是 A+B+C+D~B+D+A+C不成立。

对我来说有两个困难：

  1. 如何检查S1~S2是否
  2. 如果我知道每一对的“~”，我怎么能找到基数

更多细节：https ://www.spoj.pl/problems/ABWORDS/

4

1 回答 1

1

构造好词的规则意味着每个好词都以“a”开头并以“b”结尾。因此，有一个独特的（直到排序 - 规则 3）将好词分解为好子词：找到所有“ab”，然后尝试使用规则 2 扩展它们，并使用规则 3 对它们进行排序。我们可以通过一棵树来表达这种分解（n 个分支，用于重复应用规则 3）。

在树的上下文中，我认为“~”关系只是表示同构树（分支顺序无关紧要）。

编辑：正如所指出的，分支顺序确实很重要。

我将尝试解决原始链接中所述的问题（“nice”的 2 个定义不一致）。

首先，两个词 X 和 Y 之间的相似度，使用 DP。

定义f(a, b, n)为表示X[a..a+2n-1]相似Y[b..b+2n-1]且两个子词都很好的函数。

f(a, b, 0) = 1.

对于 n > 0，

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n)
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1)
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k)
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k)

我认为这是 O(n^4) （呃）。

对于第二部分，如果您将单词表示为带有表示相似关系的边的图，我认为您实际上是在尝试找到最大独立集。如果是这样，祝你好运！在一般情况下，它是 NP 难的（即没有比尝试所有组合更好的解决方案），而且我没有看到任何属性可以使它更容易:(

编辑使相似性的定义自动检查niceness。这很容易。

由于我的愚蠢，再次编辑。

于 2010-12-11T02:17:36.753 回答