题目描述

给定一个整数数组 $a_1, a_2, \dots, a_n$。

定义数组第 $i$ 位上的减操作：把 $a_i$ 和 $a_{i+1}$ 换成 $a_i - a_{i+1}$。

用 $\text{con}(a,i)$ 表示减操作，可以表示为：

$$\text{con}(a,i) = [a_1, a_2, \dots, a_{i-1}, a_i - a_{i+1}, a_{i+2}, \dots, a_n]$$

长度为 $n$ 的数组，经过 $n-1$ 次减操作后，就可以得到一个整数 $t$。

例如数组 $[12,10,4,3,5]$ 经过如下操作可得到整数 $4$：

$$\begin{aligned} &\text{con}([12,10,4,3,5],2) = [12,6,3,5] \\ &\text{con}([12,6,3,5],3) = [12,6,-2] \\ &\text{con}([12,6,-2],2) = [12,8] \\ &\text{con}([12,8],1) = [4] \end{aligned}$$

现在给定数组以及目标整数，求完整操作过程。

输入格式

第 1 行包含两个整数 $n$ 和 $t$。

第 2..n+1 行：第 $i$ 行包含数组中的第 $i$ 个整数 $a_i$。

输出格式

输出共 $n-1$ 行，每行包含一个整数，第 $i$ 行的整数表示第 $i$ 次减操作的操作位置。

如果方案不唯一，输出任意合理方案均可。

样例

5 4
12
10
4
3
5

2
3
2
1

样例解释

输入

$n = 5$, $t = 4$
数组：$[12, 10, 4, 3, 5]$

操作过程

如题目描述所示：

1. 第一次操作位置 2：$[12, 10-4=6, 3, 5]$ → $[12, 6, 3, 5]$
2. 第二次操作位置 3：$[12, 6, 3-5=-2]$ → $[12, 6, -2]$
3. 第三次操作位置 2：$[12, 6-(-2)=8]$ → $[12, 8]$
4. 第四次操作位置 1：$[12-8=4]$ → $[4]$

最终得到 $t=4$。

输出操作位置：2, 3, 2, 1。

数据范围

• $1 \le n \le 100$
• $-10000 \le t \le 10000$
• $1 \le a_i \le 100$

算法分析

这是一个表达式计算问题。经过 $n-1$ 次减操作后，最终结果可以看作是在原数组的每个元素前加上加号或减号（第一个元素前固定为加号），然后求和得到 $t$。

因为每次操作是 $a_i - a_{i+1}$，实际上相当于在表达式中的符号分配：
设最终表达式为：

$$s_1 a_1 + s_2 a_2 + \dots + s_n a_n = t$$

其中 $s_1 = 1$（第一个数前总是加号），$s_i \in \{+1, -1\}$ 对于 $i \ge 2$。

问题转化

我们需要给每个 $a_i$（$i \ge 2$）分配符号 $+$ 或 $-$，使得：

$$a_1 + \sum_{i=2}^n s_i a_i = t$$

即：

$$\sum_{i=2}^n s_i a_i = t - a_1$$

设 $b_i = a_i$（$i \ge 2$），$target = t - a_1$。

问题转化为：从 $b_2, b_3, \dots, b_n$ 中选取一些数前面放加号，其余放减号，使得总和为 $target$。

这是一个子集和问题的变种：设加号集合的和为 $sum_+$，减号集合的和为 $sum_-$，则 $sum_+ - sum_- = target$，且 $sum_+ + sum_- = S$，其中 $S = \sum_{i=2}^n b_i$。

解得：

$$sum_+ = \frac{target + S}{2}$$ $$sum_- = \frac{S - target}{2}$$

因此，我们需要判断 $\frac{target + S}{2}$ 是否为非负整数，并且能否从 $b_2 \dots b_n$ 中选出一些数，其和恰好为 $sum_+$。

动态规划

设 $dp[i][j]$ 表示从前 $i$ 个 $b$ 中（即 $a_2 \dots a_{i+1}$）选出若干个数，和为 $j$ 是否可行。

转移：

$$dp[i][j] = dp[i-1][j] \quad \text{或} \quad dp[i-1][j - b_i] \quad \text{如果 } j \ge b_i$$

初始化：$dp[0][0] = true$，其他为 false。

目标：$dp[n-1][sum_+]$ 是否为 true。

构造操作序列

如果存在解，我们需要构造出操作位置序列。

从最终表达式可以反推操作顺序：
表达式中相邻两项 $s_i a_i$ 和 $s_{i+1} a_{i+1}$，如果它们符号相同，那么它们可以通过一系列操作合并到同一项（最终合并时中间的符号不变）；如果符号不同，则它们不能直接合并，需要先与其他项合并。

实际上，操作位置的选择对应于表达式树的构建。我们可以采用以下策略构造：

1. 先处理所有符号为负的项：每次选择相邻两个负号项（或正负相邻），通过操作消去其中一个负号？但可能复杂。

更简单的方法：
由于 $s_1 = 1$ 固定，我们从左到右扫描 $s_2 \dots s_n$，如果 $s_i = 1$（加号），则我们可以将其与左边的项合并（操作位置为左边项的末尾）；如果 $s_i = -1$（减号），则我们需要先将其与右边项合并（但右边可能还未处理）。

实际上，可以这样构造操作序列：

• 将所有符号为正的项看作一组，符号为负的项看作另一组。
• 每次操作相当于将两个相邻的项合并，合并后的符号由左边的符号决定（因为操作是 $a_i - a_{i+1}$，合并后符号与 $a_i$ 相同？不对，操作后新值为 $a_i - a_{i+1}$，其符号不确定）。

但根据样例，$a_1=12(+), a_2=10(-), a_3=4(+), a_4=3(-), a_5=5(-)$，目标 $t=4$ 对应的符号分配为：$+12 -10 +4 -3 -5 = -2$，不等于 4，所以不对。

实际上，最终表达式并不是简单的给每个数分配符号，因为操作顺序会影响结果。例如 $((a - b) - c)$ 与 $(a - (b - c))$ 结果不同。

正确转化

考虑最终结果可以表示为：

$$t = a_1 \pm a_2 \pm a_3 \dots \pm a_n$$

但这里的 $\pm$ 不是独立的，因为括号会影响符号。实际上，最终结果可以写成：

$$t = a_1 - (a_2 - (a_3 - ( \dots - a_n) \dots ))$$

或者更一般的形式。

经过分析，实际上最终结果可以表示为：

$$t = a_1 - a_2 \pm a_3 \pm \dots \pm a_n$$

其中 $a_3$ 到 $a_n$ 前面的符号可以是加号或减号，但 $a_2$ 前面一定是减号。

为什么？因为第一次操作必然涉及 $a_1$ 和 $a_2$？不一定，第一次操作可以不是位置 1。但从操作定义看，每次操作将相邻两项 $a_i, a_{i+1}$ 替换为 $a_i - a_{i+1}$。最终结果可以看作是在原序列中插入括号和减号，形成一棵二叉树，其中每个内部节点代表一次减法。

可以证明，最终结果总可以写成：

$$t = a_1 - a_2 \pm a_3 \pm \dots \pm a_n$$

其中 $a_3 \dots a_n$ 的符号由它们所在的深度（括号嵌套）决定。

因此，问题转化为：确定 $a_3 \dots a_n$ 的符号，使得：

$$a_1 - a_2 \pm a_3 \pm \dots \pm a_n = t$$

即：

$$\pm a_3 \pm \dots \pm a_n = t - a_1 + a_2$$

设 $c_i = a_{i+2}$（$i=1 \dots n-2$），$target' = t - a_1 + a_2$。

则我们需要给每个 $c_i$ 分配符号 $+$ 或 $-$，使得总和为 $target'$。

这又是一个子集和问题。

构造操作序列

如果找到了符号分配，如何构造操作位置？

我们可以采用以下策略：

1. 将所有符号为正的 $c_i$（即 $a_{i+2}$）先与 $a_2$ 合并（通过操作位置 2 多次），使得 $a_2$ 变为 $a_2 - \sum (\text{正项})$。
2. 将所有符号为负的 $c_i$ 与 $a_1$ 合并（通过操作位置 1），使得 $a_1$ 变为 $a_1 + \sum (\text{负项的绝对值})$。
3. 最后合并 $a_1$ 和 $a_2$。

但具体操作顺序需要仔细设计，以保证最终符号正确。

由于 $n \le 100$，我们可以用搜索或动态规划直接记录操作路径。

动态规划记录路径

设 $dp[i][j]$ 表示考虑前 $i$ 个 $b$（这里 $b$ 指 $a_3 \dots a_n$），能否得到和 $j$，并记录选择方案（符号）。

然后从 $dp[n-2][target']$ 回溯，得到每个 $c_i$ 的符号。

然后构造操作序列：

• 从右向左，对于每个 $c_i$（即 $a_{i+2}$）：
  • 如果符号为正，则操作位置 2（与 $a_2$ 合并）。
  • 如果符号为负，则操作位置 1（与 $a_1$ 合并）。
• 最后操作位置 1（合并 $a_1$ 和 $a_2$）。

注意：操作后数组长度减少，位置编号会变化，但按上述策略操作位置始终是 1 或 2。

验证样例

$n=5, a=[12,10,4,3,5], t=4$ $a_1=12, a_2=10$ $c_1=4, c_2=3, c_3=5$ $target' = t - a_1 + a_2 = 4 - 12 + 10 = 2$

我们需要给 $4,3,5$ 分配符号，使得和为 2。

一种分配：$+4 +3 -5 = 2$。

因此符号：$a_3=4$（正），$a_4=3$（正），$a_5=5$（负）。

构造操作：

1. $a_5$ 为负，操作位置 1：将 $a_1$ 和 $a_2$ 合并？不对，应该先将 $a_5$ 与左边合并。但根据策略，符号为负的与 $a_1$ 合并，但 $a_5$ 左边是 $a_4$，需要先处理 $a_4$。

按照从右向左：

• $a_5$ 负 → 操作位置 1（但此时 $a_5$ 在位置 5，操作位置 1 是合并 $a_1$ 和 $a_2$，不合理）。所以需要调整。

实际上，我们可以在表达式树中考虑：最终表达式为 $a_1 - (a_2 - (a_3 + a_4 - a_5))$？展开：$a_1 - a_2 + a_3 + a_4 - a_5 = 12-10+4+3-5=4$。

对应的操作序列可以是：

• 先合并 $a_4$ 和 $a_5$：位置 4（数组长度 5）→ $[12,10,4,3-5=-2]$
• 然后合并 $a_3$ 和 $a_4$（现在是 -2）：位置 3 → $[12,10,4-(-2)=6]$
• 然后合并 $a_2$ 和 $a_3$（现在是 6）：位置 2 → $[12,10-6=4]$
• 最后合并 $a_1$ 和 $a_2$：位置 1 → $[12-4=8]$？不对，得到 8，不是 4。

所以这个操作序列不对。

实际上，样例的操作序列是 2,3,2,1，我们按这个符号分配能否得到？ 符号分配：$a_3=4$（正），$a_4=3$（正），$a_5=5$（负）。

对应的表达式：$a_1 - (a_2 - a_3 - a_4 + a_5)$？展开：$12 - (10 - 4 - 3 + 5) = 12 - 8 = 4$。

因此表达式为：$a_1 - (a_2 - a_3 - a_4 + a_5)$。

如何通过操作得到？操作序列 2,3,2,1：

1. 操作位置 2：$[12, 10-4=6, 3, 5]$ → $a_2$ 变为 $a_2 - a_3$
2. 操作位置 3：$[12, 6, 3-5=-2]$ → $a_4$ 变为 $a_4 - a_5$
3. 操作位置 2：$[12, 6-(-2)=8]$ → $a_2$ 变为 $(a_2 - a_3) - (a_4 - a_5)$
4. 操作位置 1：$[12-8=4]$ → $a_1 - [ (a_2 - a_3) - (a_4 - a_5) ] = a_1 - a_2 + a_3 + a_4 - a_5$

这正是我们想要的。

因此，给定符号分配后，我们可以通过类似样例的操作序列构造：先处理右边的项，逐步向左合并。

通用构造方法

对于符号分配 $s_3, s_4, \dots, s_n$（$s_i = +1$ 或 $-1$，表示 $a_i$ 在表达式中的符号），我们可以这样构造：

• 从 $i=n$ downto $3$：
  • 如果 $s_i = +1$，则操作位置 $i-1$（合并 $a_{i-1}$ 和 $a_i$）
  • 如果 $s_i = -1$，则操作位置 $i-2$？需要谨慎。

实际上，我们可以将表达式写成：

$$a_1 - (a_2 - (s_3 a_3 - (s_4 a_4 - (s_5 a_5 - \dots ))))$$

其中 $s_i = \pm 1$。

展开后，$a_i$ 的符号为 $(-1)^{i-1} s_i$？不完全是。

更系统的构造：
设最终表达式为 $a_1 - (a_2 - (a_3 - (a_4 - \dots - a_n) \dots ))$，但每个 $a_i$（$i\ge 3$）可以选择是否取反（即前面加负号变为加号）。

我们可以通过动态规划得到符号选择，然后按照从右向左的顺序，每次合并最右边两项，操作位置为当前数组的倒数第二个位置（即 $len-1$），但符号为正时合并方式不同？实际上，无论符号正负，操作都是 $a_i - a_{i+1}$，只是我们需要保证合并后的符号符合预期。

由于 $n$ 较小，我们可以使用深度优先搜索直接模拟所有操作顺序，找到一组解即可。复杂度 $O(n!)$ 太大，但可以剪枝。

更简单的算法：DP 记录操作

由于 $n \le 100$，但 $a_i \le 100$，$t$ 范围 $[-10000,10000]$，我们可以用 DP 记录所有可能得到的中间状态。

设 $dp[i][j]$ 表示前 $i$ 个数经过若干次操作后，能否得到值 $j$，并记录操作历史。但状态太多（$i$ 维，值范围大）。

实际上，我们可以用区间 DP：$dp[l][r][v]$ 表示区间 $[l,r]$ 经过一系列操作后能否得到值 $v$。转移时枚举分割点 $k$，$[l,k]$ 得到 $x$，$[k+1,r]$ 得到 $y$，则 $[l,r]$ 可以得到 $x - y$。

但这样状态数是 $O(n^2 \times M)$，其中 $M$ 是值范围，可能很大（$20000$）。但 $n \le 100$，$n^2 \times M \approx 100^2 \times 20000 = 2\times 10^8$，太大。

正解

由于题目要求输出任意一种方案，我们可以用记忆化搜索，搜索所有可能的操作序列，并利用值范围不大进行剪枝。

定义 $dfs(l, r, target)$ 表示区间 $[l,r]$ 能否通过一系列减操作得到 $target$，并记录操作序列。

转移：枚举最后一次操作的位置 $k$（$l \le k < r$），将区间分成 $[l,k]$ 和 $[k+1,r]$，设 $[l,k]$ 得到 $x$，$[k+1,r]$ 得到 $y$，则 $target = x - y$。递归求解 $dfs(l,k,x)$ 和 $dfs(k+1,r,y)$。

由于 $a_i \le 100$，$n \le 100$，可能的值范围有限，可以用 map 或 set 存储状态避免重复搜索。

最终从 $dfs(1,n,t)$ 得到操作序列。

输出时，注意操作位置是相对于当前数组长度的，我们需要记录每次操作后数组的变化，但输出的是原始数组中的操作位置编号（即第几次操作的位置）。实际上，我们可以记录每次操作合并了哪两个原始索引，然后输出左边索引的位置。

实现提示

• 使用记忆化搜索，状态为 $(l, r, target)$，存储是否可达。
• 由于 $target$ 范围 $[-10000,10000]$，状态数 $100^2 \times 20001 \approx 2\times 10^8$，可能太大，但实际可达状态较少，可以用 unordered_set 哈希状态。
• 输出操作位置时，需要记录操作顺序。

总结

本题的关键是将问题转化为符号分配问题，然后构造操作序列。由于 $n$ 较小，可以直接搜索或动态规划求解。