题解 | #乘之#_牛客博客

该问题是一个具有对抗性质的博奕论问题，可以建模为一个两步决策序列博弈。

1. 数学模型

给定数组 $a$ 的元素总和为 $S = \sum_{i=1}^n a_i$ 。设小龙选择的区间为 $I_L$ ，小蛇选择的区间为 $I_S$ 。区间并集（即被选中的元素集合）为 $U = I_L \cup I_S$ 。选中元素的总和为 $V = \sum_{i \in U} a_i$ 。执行操作后，数组的总和 $S'$ 可以表示为： $S' = \sum_{i \notin U} a_i + \sum_{i \in U} (k \cdot a_i) = S + (k-1)V$ 令 $D = k-1$ 。小龙的目标是最大化 $S'$ ，小蛇的目标是最小化 $S'$ 。

若 $D > 0$ （即 $k > 1$ ）：小龙希望最大化 $V$ ，小蛇希望最小化 $V$ 。
若 $D < 0$ （即 $k < 1$ ）：小龙希望最小化 $V$ ，小蛇希望最大化 $V$ 。
若 $D = 0$ （即 $k = 1$ ）： $S' = S$ ，此时博弈策略不影响结果。

2. 博弈策略

该博弈的核心在于小蛇作为后手的决策能力。

小蛇的策略分析（针对 $D < 0$ 的情形）： 此时小龙希望最小化 $V$ ，小蛇希望最大化 $V$ 。由于 $I_S$ 可以是数组中的任意非空区间，小蛇总可以执行以下操作：

无论小龙选择的 $I_L$ 是什么，小蛇都可以选择 $I_S = [1, n]$ （整个数组）。
一旦小蛇选择 $I_S = [1, n]$ ，由于 $I_L \cup I_S = [1, n]$ ，则 $V$ 必然等于 $S$ （整个数组的和）。
这意味着，在 $D < 0$ 时，小蛇保证了 $V$ 至少能够达到 $S$ （即小蛇可以强行让 $V \ge S$ ）。
同理，由于小龙可以在第一步先手就选择 $I_L = [1, n]$ ，此时无论小蛇怎么选， $V$ 都只能是 $S$ 。

小蛇的策略分析（针对 $D > 0$ 的情形）： 此时小龙希望最大化 $V$ ，小蛇希望最小化 $V$ 。

同样地，由于小蛇可以后手选择 $I_S = [1, n]$ ，小蛇可以强制 $V$ 的结果限制在 $S$ 范围内（即 $V \le S$ ）。
同理，小龙先手选择 $I_L = [1, n]$ 可以确保 $V = S$ 。

3. 均衡点判定

在这个博弈模型中，全选区间 $I = [1, n]$ 是博弈双方对抗后的不动点。

证明： 考虑集合 $\mathcal{U}$ 为所有可以表示为两个区间并集的集合。小蛇作为后手，面对小龙给定的 $I_L$ ，会在所有能包含 $I_L$ 的并集 $U \in \mathcal{U}$ 中，选择令 $(k-1)S(U)$ 最小的那个。由于 $[1, n]$ 始终是包含任何 $I_L$ 的合法并集，且全集是区间操作的上限：
1. 当 $k < 1$ 时，小蛇选择 $U \supseteq I_L$ 使 $S(U)$ 最大。因为 $U = [1, n]$ 是合法选择，故 $\max S(U) \ge S_{total}$ 。小龙为了最小化这个结果，会选 $I_L$ 使得这个最大值尽可能小。已知 $I_L = [1, n]$ 时结果为 $S_{total}$ ，故 $V = S_{total}$ 。
2. 当 $k > 1$ 时，原理相同，结果依然收敛于 $V = S_{total}$ 。

算法结论

基于上述博弈逻辑推导：在双方均采取最优策略的情况下，操作后的数组元素之和始终等于原数组元素总和乘以系数 $k$ 。