algorithm - Marathon24 比赛资格 : DNA -TLE

Question

我正在重新尝试这个 problem statement , now that the contest is all over (所以这不是作弊或任何东西，只是想学习，因为答案没有公布，只有给定测试用例输入文件的正确输出)。

有 10 个给定的测试用例输入，将为其提交相关的输出文件。我最初提交的是一个简单的嵌套 for 循环(开始，结束)对的实现，回答了这个问题:What is the volatility measure of the substring starting at (0-based) index start, and结束于end(含)。

很明显，对于 10⁶ 的最大问题限制，O(N²) 是不可行的，所以我只有 5/10 个测试用例是正确的(第一个 - 更简单 - 当然是 5)。

因此，我在这里写信是为了寻求关于如何改进我的算法的人群智慧，即我怀疑嵌套的 for 循环(开始，结束)是优化的主要瓶颈(当然!)所以到目前为止，我已经尝试将其表述为关于字符串/子字符串问题的动态规划 (DP)，但在提出状态表示和转换位以实现 DP 方面没有取得太大成功。

为了方便引用，也为了表明这不是作业，我已经诚实地尝试过了，我的原始提交可用here .

非常感谢任何帮助，甚至是指向类似问题的链接，我可以通过谷歌搜索这些问题以获取教程博客文章/示例解决方案/赛后编辑分析。

Answer 1

你尝试过分而治之吗？

如果我理解正确的话，给定一条长度为 n 的 DNA 链 S，我们将 S 分成两半，S_left 和 S_right，其中 S_left 由 S[i] 组成，其中 0 <= i < n/2，和 S_right由 S[j] 组成，其中 (n/2)+1 <= j < n。最不稳定的片段要么完全出现在 S_left 内，要么完全出现在 S_right 内，或者跨越 S_left 和 S_right 的边界。

要找到 S_left 和 S_right 中最不稳定的片段，我们只需使用递归。棘手的一点是找到跨越 S_left 和 S_right 边界的片段的波动率度量。这里有一个正整数分数的数学性质:给定四个正(非零)整数 a、b、c 和 d，(a + c)/(b + d) 永远不会大于两者 (a/b) 和 (c/d)。这里 a 和 b 是 S_left 中从边界开始的嘌呤和嘧啶的累积计数，而 c 和 d 是从边界开始的 S_right 中嘌呤和嘧啶的累积计数。这个数学属性意味着我们不需要检查 a = 0 或 c = 0 之外的交叉片段的波动率度量，因为它保证小于 S_left 或 S_right 的最大波动率。这种搜索的时间复杂度可以在交叉片段的 O(n) 和整个算法的 O(n lg n) 中完成。

希望这有效，因为我还没有编写算法代码。也许它有一个 O(n) 时间的 DP 算法来解决这个问题，但这就是我现在所拥有的。