线性纪念碑统一为z的最短攻击策略求解（含数值循环规则）

核心思路 #

这个问题可以转化为模运算下的线性方程组求解，结合贪心策略找到最短攻击序列：

1. 数值转换：将每个纪念碑的初始值 x_j 转换为相对于目标值 z 的偏移量 b_j = (x_j - z) % y（结果为负时加 y 转为非负）。此时问题等价于通过攻击操作让所有 b_j 变为0（模 y 意义下）。

2. 建立攻击影响方程：设攻击第 i 个纪念碑（0-based）的次数为 x_i（0 ≤ x_i < y，攻击 y 次等价于无操作），根据攻击影响范围，每个位置 j 满足：

   • 首位置 j=0：x_0 + x_1 ≡ (-b_0) mod y，记 c_0 = (-b_0) % y
   • 尾位置 j=n-1：x_{n-2} + x_{n-1} ≡ (-b_{n-1}) mod y，记 c_{n-1} = (-b_{n-1}) % y
   • 中间位置 0<j<n-1：x_{j-1} + x_j + x_{j+1} ≡ (-b_j) mod y，记 c_j = (-b_j) % y

3. 递推求解攻击次数：从左到右递推 x_i 的表达式，以 x_0 为变量：

   • x_1 = (c_0 - x_0) % y
   • x_2 = (c_1 - c_0) % y
   • x_3 = (c_2 - c_1 + x_0) % y
   • 后续项交替包含 +x_0 或 -x_0，其余为 c 的线性组合

4. 验证解的存在性并优化：

   • 若 n 为偶数：代入尾位置方程可解出唯一 x_0，若方程无解则问题无解
   • 若 n 为奇数：尾位置方程会转化为不含 x_0 的等式，不成立则无解；成立则遍历 x_0 的所有可能值，选择总攻击次数最少的解

5. 生成步骤序列：根据最终的攻击次数序列，将0-based编号转为1-based，重复对应次数得到步骤列表。

代码实现（Python） #

import math

def solve_monument_puzzle(initial, y, z):
    n = len(initial)
    if n == 0:
        return []
    
    # 转换为目标为0的偏移量
    b = [(x - z) % y for x in initial]
    # 计算每个位置需要的总增量模y
    c = [(-num) % y for num in b]
    
    # 存储每个x_i的表达式：x_i = coeff[i] * x0 + const[i] (mod y)
    coeff = [0] * n
    const = [0] * n
    coeff[0] = 1  # x0 = 1*x0 + 0
    
    if n >= 2:
        coeff[1] = (-1) % y
        const[1] = c[0] % y
    
    # 递推计算coeff和const
    for i in range(2, n):
        # 基于j=i-1的方程推导：x_{i-2} + x_{i-1} + x_i = c[i-1]
        coeff[i] = (-coeff[i-2] - coeff[i-1]) % y
        const[i] = (c[i-1] - const[i-2] - const[i-1]) % y
    
    valid_x0 = []
    # 处理不同情况确定x0
    if n == 1:
        valid_x0 = [c[0] % y]
    elif n % 2 == 0:
        total_coeff = (coeff[n-2] + coeff[n-1]) % y
        total_const = (const[n-2] + const[n-1]) % y
        target = (c[-1] - total_const) % y
        
        if total_coeff == 0:
            if target != 0:
                return None
            # 遍历找总攻击次数最少的x0
            min_sum = float('inf')
            best_x0 = 0
            for x0_candidate in range(y):
                current_sum = sum((coeff[i]*x0_candidate + const[i])%y for i in range(n))
                if current_sum < min_sum:
                    min_sum = current_sum
                    best_x0 = x0_candidate
            valid_x0 = [best_x0]
        else:
            # 解同余方程
            g = math.gcd(total_coeff, y)
            if target % g != 0:
                return None
            inv = pow(total_coeff//g, -1, y//g)
            x0_base = ((target//g) * inv) % (y//g)
            # 遍历所有可能解找最优
            min_sum = float('inf')
            best_x0 = x0_base
            for k in range(g):
                x0_candidate = (x0_base + k*(y//g)) % y
                current_sum = sum((coeff[i]*x0_candidate + const[i])%y for i in range(n))
                if current_sum < min_sum:
                    min_sum = current_sum
                    best_x0 = x0_candidate
            valid_x0 = [best_x0]
    else:
        total_coeff = (coeff[n-2] + coeff[n-1]) % y
        total_const = (const[n-2] + const[n-1]) % y
        target = (c[-1] - total_const) % y
        
        if total_coeff == 0:
            if target != 0:
                return None
            # 遍历找最优x0
            min_sum = float('inf')
            best_x0 = 0
            for x0_candidate in range(y):
                current_sum = sum((coeff[i]*x0_candidate + const[i])%y for i in range(n))
                if current_sum < min_sum:
                    min_sum = current_sum
                    best_x0 = x0_candidate
            valid_x0 = [best_x0]
        else:
            # 解同余方程得唯一x0
            g = math.gcd(total_coeff, y)
            if target % g != 0:
                return None
            inv = pow(total_coeff//g, -1, y//g)
            x0 = ((target//g) * inv) % (y//g)
            valid_x0 = [x0]
    
    # 生成攻击步骤序列（1-based）
    x0 = valid_x0[0]
    attack_counts = [(coeff[i]*x0 + const[i])%y for i in range(n)]
    steps = []
    for idx, cnt in enumerate(attack_counts):
        steps.extend([idx+1]*cnt)
    return steps

# 测试题目示例
initial = [1,3,2,1]
y = 3
z = 3
result = solve_monument_puzzle(initial, y, z)
print("最短攻击步骤序列（1-based编号）：", result)

示例验证 #

题目示例中，初始值 [1,3,2,1]、y=3、z=3，运行代码得到步骤序列 [2,2,3,4]，验证过程：

1. 攻击2号两次：初始值变为 [3,2,1,1]
2. 攻击3号一次：变为 [3,3,2,2]
3. 攻击4号一次：变为 [3,3,3,3]，达成目标

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