USACO 2020年2月铜组第3题Swapity Swap Python优化求助

题目描述 #

农夫约翰的N头奶牛（1≤N≤100）排成一列，从左数第i头奶牛的编号为i（1≤i≤N）。他为奶牛设计了一套晨练流程，要求奶牛重复执行下述两步操作恰好K次（1≤K≤1000000000）：

1. 反转当前处于位置A₁到A₂的奶牛的顺序（1≤A₁<A₂≤N）
2. 反转当前处于位置B₁到B₂的奶牛的顺序（1≤B₁<B₂≤N）
   请你输出K次操作结束后，从左数第i头奶牛的编号（1≤i≤N）。

评分规则 #

• 测试用例2-3满足K≤100
• 测试用例4-13无额外约束

输入格式 #

（文件swap.in）：

• 第一行包含N和K
• 第二行包含A₁和A₂
• 第三行包含B₁和B₂

输出格式 #

（文件swap.out）：第i行输出最终从左数第i头奶牛的编号。

样例输入 #

7 2
2 5
3 7

样例输出 #

1
2
4
3
5
7
6

样例说明 #

初始奶牛顺序为[1,2,3,4,5,6,7]，第一次执行第一步后顺序为[1,5,4,3,2,6,7]，执行第二步后顺序为[1,5,7,6,2,3,4]，重复执行一次完整流程后得到上述样例输出。

问题现状 #

理论上可以通过找周期的方法求解：先找到状态重复的周期frequency，只需模拟k % frequency次操作即可。但当输入为：

100 1000000000
1 94
2 98

时，原程序运行时间超过100秒，该用例的周期frequency极高，迭代次数达到上限导致超时。

原代码 #

fin = open("swap.in", 'r')
line = fin.readline().strip().split()
n = int(line[0])
k = int(line[1])
nums = [[int(x)-1 for x in fin.readline().strip().split()]for i in range(2)]
fin.close()
repeated = []
cows = [i for i in range(1, n+1)]
repeat = False
while not repeat:
    for i in nums:
        cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1])
        if cows[i[0]:i[1]+1] in repeated :
            frequency = len(repeated)-1
            repeat = True
        repeated.append(cows[i[0]:i[1]+1])

cows = [i for i in range(1, n+1)]
for _ in range(k%frequency):
    for i in nums:
        cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1])

fout = open("swap.out", 'w')
for i in cows:
    fout.write(str(i) + "\n")
fout.close()

原代码问题分析 #

• 周期判断逻辑错误：仅以局部子序列重复判定全局周期到达，和实际全局周期不符，计算出的frequency本身就是错误的
• 性能开销极高：频繁切片、列表反转、in查询操作都是O(n)复杂度，遇到大周期时迭代次数过多直接超时

最优解法思路 #

利用置换循环分解的方法，时间复杂度稳定为O(n)，完全不受K的大小影响：

1. 先预处理得到**一轮完整操作（反转A段+反转B段）**的置换映射next_pos：next_pos[i]表示初始位置i经过一轮完整操作后会移动到的新位置
2. 对每个位置i，单独查找它所在的循环链，例如循环链为i → p1 → p2 → ... → i，周期长度为L，那么经过K轮操作后，最终位置i对应的奶牛编号就是初始序列中该循环链里往前数K % L位的数值

优化后代码 #

def main():
    # 读入数据
    with open("swap.in", 'r') as fin:
        n, k = map(int, fin.readline().split())
        a1, a2 = map(lambda x: int(x)-1, fin.readline().split())
        b1, b2 = map(lambda x: int(x)-1, fin.readline().split())
    
    # 预处理一轮操作的置换映射next_pos
    next_pos = [0]*n
    for i in range(n):
        # 先算反转A段后的位置
        if a1 <= i <= a2:
            cur = a1 + a2 - i
        else:
            cur = i
        # 再算反转B段后的位置
        if b1 <= cur <= b2:
            cur = b1 + b2 - cur
        next_pos[i] = cur
    
    res = [0]*n
    visited = [False]*n
    for i in range(n):
        if not visited[i]:
            # 找当前位置所在的循环
            cycle = []
            cur = i
            while not visited[cur]:
                visited[cur] = True
                cycle.append(cur)
                cur = next_pos[cur]
            # 计算每个位置K步后的结果
            L = len(cycle)
            for idx in range(L):
                final_idx = cycle[(idx + k) % L]
                res[final_idx] = cycle[idx] + 1  # 加1转回1-based编号
    
    # 输出结果
    with open("swap.out", 'w') as fout:
        for num in res:
            fout.write(f"{num}\n")
if __name__ == "__main__":
    main()

方案优势 #

• 完全不需要迭代K次或者找全局大周期，最多只需要遍历100个位置，即使K是1e9也可以在毫秒级完成计算
• 没有频繁的列表反转、切片操作，所有计算都是O(1)的位置映射，性能拉满

内容的提问来源于stack exchange，提问作者CoderTang