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 回答