有一类问题，要求我们从给定数组中随机选择两个元素，对这些元素执行操作，将结果添加到“答案”中，然后删除其中任何一个元素并放入另一个元素元素放回到数组中。
最近，我遇到了这个 - 给定一个数组，选择两个元素 a 和 b，将 (a XOR b) 添加到“答案”。然后删除 a 或 b 并将另一个放回数组中。重复这些操作，直到数组中只剩下一个元素。您可以获得的“答案”的最大值是多少(参见问题 here)
示例 I/O:-
arr = [3,2,1]
输出 = 5；
可能的运算 - 2 ^ 1 (= 3) -> Drop 2 -> 3 ^ 1 (= 2) -> Drop 3。将 3+2=5 相加，即为答案的最终值。
现在，考虑到这个问题，我可以编写一个递归+回溯代码来处理这个问题，但是时间复杂度当然是 N! 的数量级。我一直在阅读这一点，似乎可以通过最小/最大生成树来处理。我根本不明白为什么最大生成树在这里起作用。我放了一个comment在问题线索上。在下面粘贴部分评论。
运行场景 - 当遵循 Prim 的 MaxST 算法时，假设我们选择的第一条边是 (A,B)。现在我们选择的下一条边应该是附加到 A 或 B 的边，并且应该具有最大权重。假设我们选择 (A,C)。同样，现在我们需要选择一条连接到 A 或 B 或 C 且具有最大权重的边。它可能是一条边 (B,D)。现在在这种情况下，我们选择 (A,C) 和 (B,D) 作为 MaxST 的一部分。然而，根据问题，当我们选择第一条边 (A.B) 时，我们应该从数组中删除 A 或 B，这意味着一旦我们选择 (A,B)，我们现在只能选择 (A,C) { IE。删除 B，因此在未来的任何步骤中都不能选择 (B,D) 或连接到 B 的任何其他边}或选择 (B,D) {即删除 A，因此在未来的任何步骤中都不能选择 (A,C) 或连接到 A 的任何其他边}，但理想情况下不能同时选择 (A,C) 和 (B,D) 澄清一下，选择任何边作为 MaxST 的一部分意味着我们要对答案中的这两个元素进行异或，即如果我们选择一条边 (A,B)，则意味着我们要添加 A^答案为 B(因此必须放弃 A 或 B)。考虑到上述情况，MaxST 在这里如何工作是没有意义的。您能解释一下吗？
最佳答案
为了了解如何使用 MST 解决这些问题，您需要了解两件事:
每个有效的对序列都会创建一个生成树。您可以使用以下方法归纳证明这一点:
- 在每次选择之前和之后，每个剩余的顶点都连接到一棵树；和
- 对于每棵树，仅剩下一个个顶点。
对于每个生成树，都有一个创建该树的对序列。通过重复选择叶子及其父代，然后删除叶子，可以轻松构建此序列。当 parent 的 child 全部被丢弃时， parent 本身就会变成一片叶子。
因此对于每个序列都有一个生成树，并且对于每个生成树都有一个序列。要解决该问题，请找到最大生成树，然后选择创建它的任何序列，如下(2)。
关于algorithm - 对数组中的一对元素进行操作并删除一个，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/76353589/