arrays - 在交换序列后查找每个节点占用的唯一位置的数量

Question

一条线上有 N (N <= 50000) 个节点，节点 i 位于线上的位置 i 上。给你一个 M 个不同交换的序列 (M <= 20000)，写在 from (a1, b1) (a2, b2) ... 中。(aM, bM)。在每个时间单位 i = 1…M 中，位置 ai 和 bi 处的节点交换。然后，相同的 M 交换在 M + 1….2M 分钟内再次发生，然后是 2M + 1…3M，依此类推，继续循环方式持续 K 个时间单位 (K < 10^18)。

例如，

在单位时间 1，位置 a1 和 b1 的节点交换。

在单位时间 2，位置 a2 和 b2 的节点交换。

…</p>

在单位时间 M 处，位于 aM 和 bM 位置的节点交换。

在时间单位 M + 1 处，位置 a1 和 b1 的节点交换。

在时间单位 M + 2 处，位置 a2 和 b2 的节点交换。

等等……</p>

对于每个节点，您被要求确定它将占据的唯一位置的数量。

例子：

6 个节点，M = 4（序列由 4 个交换组成），K = 7（总时间单位为 7）。

序列：

(1, 2) (2, 3) (3, 4) (4, 5)

模拟：

时间 0：{1、2、3、4、5、6}

时间 1：{2、1、3、4、5、6}

时间 2：{2、3、1、4、5、6}

时间 3：{2、3、4、1、5、6}

时间 4: {2, 3, 4, 5, 1, 6}

时间 5：{3、2、4、5、1、6}

时间 6：{3、4、2、5、1、6}

时间 7: {3, 4, 5, 2, 1, 6}

回答：

节点 1 到达位置 {1, 2, 3, 4, 5}，所以有 5 个位置。

节点 2 到达位置 {1, 2, 3, 4}，因此有 4 个位置。

节点 3 到达位置 {1, 2, 3}，所以 3 个位置。

节点 4 到达位置 {2, 3, 4}，所以 3 个位置。

节点 5 到达位置 {3, 4, 5}，所以 3 个位置。

节点 6 没有移动，所以它到达位置 {6}，所以是 1 个位置。

解决此问题的一种方法是将节点视为图形。然后，您可以将每个交换视为连接，然后使用图形算法来计算您在节点之间的移动方式。

我怎样才能成功地将图算法合并到这个问题中？

编辑：我花了几个小时思考这个问题，并希望将 Ehsan 的想法纳入解决方案。要找到可能位于每个位置的节点，您可以使用递归函数，例如 Ehsan 提出的那个 (F(F(...(F(original_order))))。然后，您可以在每个步骤中执行此操作K. 但是，这将是一个 NK 解决方案，因为我可以执行的最大操作数是 10^9，所以我太慢了。我该如何优化我当前的想法？

标签： arraysalgorithmoptimizationgraphlanguage-agnostic

Answer 1

你不需要这个图表。他们的关键点是减少 k

{n1,n2,n3,...,nN}引理：假设在一系列步骤之后从原始节点列表{s1,s2,.....,st}达到新的节点顺序，{n_i1,...,n_iN}并且每个节点都有一个唯一的访问列表{n1_v1,...,n1_vn1},...,{nN_v1,...,nN_vnN}

O(n)然后如果您再次执行相同的一系列步骤，您可以在上一步的帮助下找到新的节点顺序列表以及唯一访问列表。所以这是一种动态规划。通过这种方法，您的算法的复杂性可能为O(n*log(k/m)+m)