abc361 D - Go Stone Puzzle

AI 给出的解法，以下是它的解释。

问一下这是怎么过的？

这个问题可以看作是一个排列问题，其中我们需要通过移动石头来将初始排列 $S$ 转换为目标排列 $T$。我们可以通过以下步骤来解决这个问题：

1. 确定初始状态和目标状态的排列：

   • 初始状态 $S$ 是一个长度为 $N$ 的字符串，表示从左到右每个单元格中的石头颜色。
   • 目标状态 $T$ 也是一个长度为 $N$ 的字符串，表示我们希望达到的石头颜色排列。

2. 计算初始排列和目标排列的逆序数：

   • 逆序数是一个排列中逆序对的个数。逆序对是指在一个排列中，如果 $i < j$ 但 $S_i > S_j$，则 $(S_i, S_j)$ 是一个逆序对。
   • 逆序数的奇偶性决定了排列是否可以通过交换相邻元素来达到另一个排列。

3. 判断是否可能达到目标状态：

   • 如果初始排列 $S$ 和目标排列 $T$ 的逆序数的奇偶性不同，则不可能通过交换相邻元素来达到目标排列。
   • 如果逆序数的奇偶性相同，则可以通过交换相邻元素来达到目标排列。

4. 计算最小操作次数：

   • 如果可能达到目标状态，我们需要计算从初始排列 $S$ 到目标排列 $T$ 的最小交换次数。
   • 这可以通过计算两个排列之间的汉明距离（即不同位置的数量）来实现。

代码实现

def count_inversions(s):
    count = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] > s[j]:
                count += 1
    return count

def min_operations(N, S, T):
    # 计算初始排列和目标排列的逆序数
    inversions_S = count_inversions(S)
    inversions_T = count_inversions(T)
    
    # 如果逆序数的奇偶性不同，则不可能达到目标状态
    if (inversions_S % 2) != (inversions_T % 2):
        return -1
    
    # 计算汉明距离
    hamming_distance = sum(1 for i in range(N) if S[i] != T[i])
    
    # 最小操作次数是汉明距离的一半
    return (hamming_distance + 1) // 2

# 读取输入
N = int(input())
S = input()
T = input()

# 输出结果
print(min_operations(N, S, T))

解释

1. 逆序数计算：

   • count_inversions 函数计算一个排列的逆序数。

2. 判断是否可能达到目标状态：

   • 通过比较初始排列 $S$ 和目标排列 $T$ 的逆序数的奇偶性来判断是否可能达到目标状态。

3. 计算最小操作次数：

   • 通过计算汉明距离来确定从初始排列 $S$ 到目标排列 $T$ 的最小交换次数。

这个方法确保了我们能够有效地判断是否可能达到目标状态，并在可能的情况下计算出最小的操作次数。