7299 字

36 分钟

【ACM 算法随笔】枚举技巧与枚举优化

2026-01-15

ACM Note

Algorithm

/

Trick

/

Note

/

ACM

基础枚举技巧论#

在算法实现中，枚举是极为常见且基础的一类操作 。无论是遍历状态空间、构造候选方案，还是对中间结果进行验证，枚举都承担着将抽象问题转化为具体计算过程的作用。由于其形式直接、逻辑清晰，枚举往往是解题过程中最早被采用的手段之一，也常常作为更复杂算法的出发点或验证手段。在许多问题中，即便最终解法并非暴力枚举，枚举仍然在思路推导与结构分析阶段发挥着重要作用 。

然而，枚举的实现方式并非只有简单的多重循环这一种选择。通过合理的 状态表示、遍历顺序以及构造方式 ，可以使枚举过程更贴合问题的结构特征，从而在表达上更加简洁、逻辑上更加清晰。这类技巧主要关注的是 枚举过程的组织方式本身 ，虽然不一定改变问题的规模或复杂度，但往往能够降低实现难度，并为后续的推导与改写提供更稳定的基础。

子集的枚举技巧#

在算法竞赛中，子集枚举 是解决诸多问题的基础。对于一个含有 $n$ 个元素的集合，其子集的总数为 $2^n$ 。当 $n$ 的规模较小时，通过遍历所有可能的组合来寻找最优解或统计合法方案是一种极具通用性的策略。高效且正确地写出子集枚举逻辑，是深入学习状态压缩动态规划等进阶算法的先决条件。

最直观的子集枚举方式，是按照元素顺序，对每一个元素依次做 “选或不选” 的决策。这种思路与人类思考子集的方式完全一致，其自然实现形式就是深度优先搜索。设集合大小为 $n$ ，我们从第 $0$ 个元素开始处理，在递归的第 $i$ 层决定元素 $a_i$ 是否被加入当前子集。当所有元素都被处理完时，就得到了一个完整子集。整个搜索树是一棵深度为 $n$ 的二叉树，总共包含 $2^n$ 个叶子节点。

1
vector<int> a;    // 原集合
2
vector<int> cur;  // 当前子集
3
int n;
4

5
void dfs(int i) {
6
    if (i == n) {
7
        // 此时 cur 就是一个子集
8
        // 在这里处理 cur
9
        return;
10
    }
11

12
    // 不选 a[i]
13
    dfs(i + 1);
14

15
    // 选 a[i]
16
    cur.push_back(a[i]);
17
    dfs(i + 1);
18
    cur.pop_back();
19
}

这种 DFS 枚举方式的特点在于结构非常清晰，递归层数与元素个数一一对应，并且在枚举过程中可以自然地加入剪枝条件或提前返回的逻辑。因此，当题目需要在枚举过程中动态维护信息、或根据部分选择判断可行性时，这种写法往往最容易控制和修改。

另一种同样基础的非迭代方法是 使用二进制掩码枚举子集 。其核心思想是用一个整数的二进制表示来刻画子集状态：第 $i$ 位为 1 表示选择第 $i$ 个元素，为 0 表示不选择。这样，从 0 到 (1<<n)-1 的所有整数，恰好一一对应集合的所有子集。对每一个状态，只需检查每一位是否为 1 即可还原当前子集包含哪些元素。

1
vector<int> a;
2
int n;
3

4
for (int mask = 0; mask < (1 << n); mask++) {
5
    vector<int> subset;
6
    for (int i = 0; i < n; i++) {
7
        if (mask & (1 << i)) {
8
            subset.push_back(a[i]);
9
        }
10
    }
11
    // subset 即为当前子集
12
}

这种枚举方式的优势在于状态表示极为紧凑，判断元素是否被选只需一次位运算，并且非常适合与状态压缩动态规划等算法结合使用。从本质上看，它与 DFS 枚举并没有任何区别，只是将 “选或不选” 的递归决策过程，直接编码进了二进制表示中。

在位掩码表示的基础上，存在一种在 状态压缩动态规划 中极为关键且高频使用的技巧：在给定一个特定集合 $S$ 的前提下，枚举它的所有子集 。在处理如子集 DP 或需要遍历 “某个状态的所有子状态” 的场景时，我们并不需要从 $0$ 盲目枚举到 $2^n-1$ ，而是仅需聚焦于那些满足 “属于 $S$ 的子集” 的状态。为了追求极致的执行效率，通常采用如下经典循环结构：

1
for (int j = S; j; j = (j - 1) & S) {
2
    // j 是 S 的一个非空子集，在这里执行逻辑
3
}

这段简洁的代码能够 不重不漏 地按照递减顺序枚举出 $S$ 的所有非空子集。其核心原理在于利用了二进制减法的特性：当我们对当前子集 $j$ 执行 j - 1 操作时，会将 $j$ 最右侧的 1 变为 0 ，并将其右侧所有的位翻转为 1 ；随后通过与原集合 $S$ 进行 按位与 运算，系统会自动抹除掉不属于 $S$ 的多余位。这一过程精准地锁定了在数值上 严格小于 $j$ 且仍属于 $S$ 子集 的最大整数，从而实现了对子集空间的高效遍历。

这种写法在解决划分型动态规划等高级算法问题时具有无可替代的地位。相比于先枚举所有掩码再进行逻辑判断的朴素做法，该技巧通过直接操作二进制位，将总的时间复杂度优化至 $O(3^n)$ ，远优于 $O(4^n)$ 的常规实现。该算法从位运算的底层逻辑出发，通过消除无效状态的冗余迭代，使代码逻辑与集合论的数学结构达成了深度契合。

排列的枚举技巧#

在排列问题中，枚举的核心不再是选择，而是 在不重复使用元素的前提下，确定每一个位置放什么 。因此，最自然的建模方式是：把排列看成一个长度为 $n$ 的序列，枚举第 $0$ 位、第 $1$ 位直到第 $n-1$ 位依次放入的元素。这种视角下，排列枚举几乎可以直接套用 DFS 的框架。

最基础的做法是 DFS 按位置填数 。递归深度表示当前已经确定了多少个位置，在第 pos 层，从所有尚未使用过的元素中任选一个放到当前位置即可。为了保证每个元素只使用一次，通常会维护一个 used 数组，用来标记哪些元素已经被选过。递归到深度为 $n$ 时，当前序列就是一个完整排列。

1
vector<int> a;      // 原始元素
2
vector<int> perm;   // 当前构造中的排列
3
vector<bool> used;
4
int n;
5

6
void dfs(int pos) {
7
    if (pos == n) {
8
        // perm 是一个完整排列
9
        return;
10
    }
11
    for (int i = 0; i < n; i++) {
12
        if (used[i]) continue;
13
        used[i] = true;
14
        perm.push_back(a[i]);
15
        dfs(pos + 1);
16
        perm.pop_back();
17
        used[i] = false;
18
    }
19
}

这种基于位置填充的递归模式，在逻辑上直接映射了排列定义的构造过程。这种写法的核心优势在于其具备极高的扩展性：由于每一层递归都明确对应序列中的一个具体位置，可以在枚举过程中直接注入约束条件或维护动态信息，例如在当前层执行剪枝以跳过不符合要求的搜索分支。代价是需要显式维护使用状态，代码略显冗长。

如果换一个角度看待排列，其实也可以认为排列就是对数组进行一系列交换的结果。基于这种理解，可以得到 原地交换枚举排列 的写法。具体思路是在递归的第 pos 层，决定哪个元素最终放在位置 pos ，于是从区间 [pos, n) 中任选一个元素，与 a[pos] 交换，然后递归处理下一位。回溯时再交换回来，保证数组状态不被破坏。

1
vector<int> a;
2
int n;
3

4
void dfs(int pos) {
5
    if (pos == n) {
6
        // 当前 a 即为一个排列
7
        return;
8
    }
9
    for (int i = pos; i < n; i++) {
10
        swap(a[pos], a[i]);
11
        dfs(pos + 1);
12
        swap(a[pos], a[i]);
13
    }
14
}

这种交换式的构造逻辑，实质上是将待处理的数组划分为已确定和待选择两个动态区间。在每一层递归中，算法通过将后端的一个候选元素交换至当前索引位，隐式地完成了元素的选择与去重，从而避免了维护额外布尔数组的空间开销。从逻辑上看，该方法与显式使用 used 数组的 DFS 具有对称性：前者通过全局标记锁定可用元素，而此处则通过原地交换改变搜索空间，将所有状态演化直接体现在数组本身的排列组合中。

除了基于 DFS 的构造型枚举，还有一种常用的方法是 直接按字典序枚举排列 。这种方法并不关心排列是如何构造出来的，而是把排列本身当作一个状态，通过确定的规则在状态之间跳转。只要从字典序最小的排列开始，不断生成下一个排列，就可以在不重复、不遗漏的情况下遍历全部结果。在 C++ 中，这一过程由 next_permutation 封装完成。只要先对数组排序，然后反复调用该函数即可。

1
sort(a.begin(), a.end());
2
do {
3
    // 当前 a 是一个排列
4
} while (next_permutation(a.begin(), a.end()));

理解 next_permutation 的核心在于：该算法并非任意构造一个新的排列，而是 在全体排列的字典序序列中，严格生成当前排列的直接后继 。为实现这一目标，算法对排列结构进行了精确分析，并通过一组确定性的操作，在保证字典序连续性的同时完成状态转移。其具体过程可以分解为以下三个步骤：

从右向左确定首个上升点：从序列末尾向左扫描，找到第一个满足 $a[i] < a[i+1]$ 的位置 $i$ 。该位置的存在表明：区间 [i+1, n) 已经处于在固定前缀 a[0..i] 条件下的最大排列状态，若要获得字典序更大的排列，唯一可能的修改位置只能位于 $i$ 及其左侧。若不存在这样的 $i$ ，则说明整个序列为非递增序列。
在后缀中选择最小的可替换元素交换：在区间 [i+1, n) 中，从右向左查找第一个满足 $a[j] > a[i]$ 的位置 $j$ ，并交换 a[i] 与 a[j] 。这一操作的作用在于：在第 $i$ 位对排列进行 最小幅度的增大 ，从而保证新排列严格大于原排列，同时又尽可能接近原排列的字典序位置。
将后缀重排为字典序最小形式：交换完成后，区间 [i+1, n) 仍保持非递增状态。为了使整体排列在所有可能的后继中达到字典序最小，只需将该区间反转，使其变为递增序列。此操作确保后缀部分在当前前缀固定的条件下取到最小可能值。

正是由于上述三步分别在 修改位置的选择、增量大小的控制以及后缀排列的最小化 三个层面进行了严格约束，next_permutation 才能够在不依赖递归或额外状态记录的前提下，按照字典序序完整无重复地遍历所有排列。

贡献法优化枚举#

在算法设计中，许多问题表面上需要对海量的子集或区间进行穷举，但直接枚举往往会产生极高的计算开销。尤其是在涉及 组合计数 或 序列特征 的复杂问题中，由于不同对象之间存在大量的重叠部分，简单的遍历会导致算法的时间复杂度迅速失控。如何在确保结果准确的前提下，通过转变观察维度来消除原本重复的计算逻辑，是我们优化算法效率的核心课题。

贡献法 正是应对此类挑战的一种核心思想。其底层逻辑在于 逆转对答案构成的观察视角：我们不再从宏观层面去逐一处理每一个复杂的整体组合，而是转而统计 单个元素 、特定操作 或 局部结构 在所有合法情形中对最终结果所产生的影响。通过这种 化整为零 的策略，我们将全局的加和问题转化为对各局部元素出现次数的计数问题。

局部变化贡献法#

局部变化贡献法是一种专门处理 修改为单点操作、查询为全局统计 的算法技巧。由于单点修改对整体答案的影响范围非常有限，且目标始终是获取全局统计量，因此我们无需在每次变动后重算全局，而是通过维护一个实时的全局答案来解决。其核心逻辑在于将修改前后的状态差异视为增量修正，通过精准捕捉局部范围内的变化，实现对全局结果的同步更新。

这种方法的核心在于构建一种 差分修正 的思维范式。它主张放弃对整个序列或集合的重复扫描，转而聚焦于单次修改所引发的 净变化 。在具体实现中，我们通过维护一个全局变量来实时记录答案，根据单点由旧元素变为新元素而产生的贡献差异，直接在全局变量上进行补偿。该策略有效地规避了对恒定状态的冗余计算，使原本耗时的频繁全局统计操作变得极其轻量。

最小值之和查询#

题目链接

Problem Statement#

给定两个长度为 $N$ 的整数序列

A = (A_1, A_2, \ldots, A_N) \quad B = (B_1, B_2, \ldots, B_N)

以及一个整数 $Q$ 表示查询数量。每个查询会描述如下操作：

输入一个字符 $c_i$ 和两个整数 $X_i, V_i$ ：
- 若 $c_i =$ "A" ，则将 $A_{X_i}$ 修改为 $V_i$
- 若 $c_i =$ "B" ，则将 $B_{X_i}$ 修改为 $V_i$

在执行完该修改之后，计算并输出：

\sum_{k=1}^N \min(A_k, B_k)

即序列 $A$ 与序列 $B$ 的对应元素最小值之和。

Constraints#

$1 \leq N, Q \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq 10^9$
$c_i$ 只能是字符 "A" 或 "B"
$1 \leq X_i \leq N$
$1 \leq V_i \leq 10^9$
所有输入均为整数

Input#

输入包含多行：

第一行包含两个整数 $N$ 和 $Q$ 。
第二行包含 $N$ 个整数，表示序列 $A$ 。
第三行包含 $N$ 个整数，表示序列 $B$ 。
接下来的 $Q$ 行中，每行包含一个字符与两个整数，表示一次查询。

$N \quad Q$

$A_1 \quad A_2 \quad \ldots A_N$

$B_1 \quad B_2 \quad \ldots B_N$

$c_1 \quad X_1 \quad V_1$

$c_2 \quad X_2 \quad V_2$

$\ldots$

$c_Q \quad X_Q \quad V_Q$

Output#

输出 $Q$ 行，每行对应一个查询的结果，即执行修改并计算最小值之和后的输出。

Sample Input 1#

Sample Output 1#

7
9
9

Sample Input 2#

Sample Output 2#

1
1
1

Sample Input 3#

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3#

421
420
420

题目要点解析#

对象交换贡献法#

对象交换贡献法适用于答案由大量子结构累加而成的情境。其核心逻辑在于 逆向重构问题维度：与其机械地枚举所有可能的整体组合，不如转而分析每一个独立元素、边或子项在最终结果中的 贡献频次 。通过这种从全局搜索向局部统计的视角切换，我们能够将复杂的枚举过程转化为对单个对象映射关系的量化累加，从而在逻辑底层消除冗余判定，大幅压缩计算开销。

这种 按位统计贡献 的思想在多类算法场景中具有普适性，其精髓在于 由元素属性倒推全局答案 。通过明确单个对象对最终指标的影响量，并将其量化后进行线性加权，该方法能使复杂的逻辑结构变得层次分明。这种分析范式不仅显著提升了执行效率，更是处理高阶组合计数与序列特征问题时，实现计算复杂度量级跨越的核心手段。

滑动窗口最大值#

题目链接

Problem Statement#

给定一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。对于每一个 $k = 1, 2, \ldots, N$ ，我们考虑所有长度为 $k$ 的 连续子数组（滑动窗口）。对于每一个这样的子数组，求它的最大值，然后将这些最大值求和。

具体来说，长度为 $k$ 的连续子数组共有 $N-k+1$ 个，它们分别是：

(A_1, A_2, \ldots, A_k), (A_2, A_3, \ldots, A_{k+1}), \ldots, (A_{N-k+1}, \ldots, A_N)

我们需要计算这些窗口最大值的总和，并按顺序输出 $k = 1$ 到 $k = N$ 的结果。

Constraints#

$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i \leq 10^7$
所有输入均为整数

Input#

输入包含两行：

第一行包含一个整数 $N$ ，表示序列长度。
第二行包含 $N$ 个整数，表示序列的各个元素。

$N$

$A_1 \quad A_2 \quad \ldots \quad A_N$

Output#

输出 $N$ 行，第 $i$ 行输出当 $k=i$ 时所有长度为 $k$ 连续子数组最大值之和。

Sample Input 1#

4
5 3 4 2

Sample Output 1#

Sample Input 2#

8
2 0 2 5 0 5 2 4

Sample Output 2#

Sample Input 3#

11
9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010

Sample Output 3#

题目要点解析#

序列数对的权重#

题目链接

Problem Statement#

给定一个整数序列 $a = (a_1, a_2, \ldots, a_n)$ 定义此序列的 权重（weight） 为所有满足 $i < j$ 且 $a_i = a_j$ 的 无序下标对 的数量。例如序列 $[1,1,2,2,1]$ 的权重为 $4$ ，因为满足条件的下标对为 $(1,2), (1,5), (2,5), (3,4)$ 。

给你一个长度为 $n$ 的整数序列 $a$ ，对于该序列的所有子段（即连续区间） $b = (a_l, a_{l+1}, \ldots, a_r)$ ，计算这些子段的权重之和，并输出最终结果。

注意，子段定义为从原序列左右两端删除若干（可以为 $0$ 或全部）元素得到的连续区间。输入包含多个测试用例，所有测试用例中所有 $n$ 的总和不超过 $10^5$ 。

Constraints#

$1 \leq t \leq 10^5$
$1 \leq n \leq 10^5$
$1 \leq a_i \leq 10^9$

Input#

输入包含两行：

第一行包含一个整数 $n$ ，表示序列长度。
第二行包含 $n$ 个整数，表示序列元素。

$n$

$a_1 \quad a_2 \quad \ldots \quad a_n$

Output#

对于每个测试用例输出一个整数表示所有连续子段权重之和。

Sample Input#

Sample Output#

6
0

题目要点解析#

预处理优化枚举#

在算法设计中，尤其是面对涉及高频查询的场景，若每次请求都从头执行完整的枚举或扫描，往往会导致巨大的计算开销。核心的优化思路在于：通过预处理机制将计算压力前移 ，提前处理与具体查询参数无关的公共部分。其本质是将重复性劳动转化为一次性投入，通过利用基础数据中静态不变的属性，构建出高效的辅助逻辑，从而在查询阶段直接调取预存的中间状态，实现对冗余遍历过程的规避。

在具体实现中，预处理将复杂的逻辑推导简化为 快速状态合并或直接查表 的操作模式。通过将原本随查询波动的动态计算，转化为对预处理结果的常数级调用，系统能够显著压缩查询路径并消除计算冗余。这种策略不仅在静态场景下表现卓越，在配合动态维护结构时同样能维持极高的响应效率，是打破大规模数据处理性能瓶颈、实现极速状态转移的关键手段。

选数异或和问题#

题目链接

Problem Statement#

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ ，以及一个整数 $x$ 。

现在有 $q$ 次询问，每次询问给定一个区间 $[l,r]$ 。你需要判断是否存在两个不同的下标 $i,j$ ，满足：

$l \leq i < j \leq r$
$a_i \oplus a_j = x$

如果存在这样的两个数，则输出 yes ，否则输出 no 。

Constraints#

$1 \leq n,q \leq 10^5$
$0 \leq a_i < 2^{20}$
$0 \leq x < 2^{20}$
$1 \leq l \leq r \leq n$

Input#

输入包含多行：

第一行包含三个整数 $n$ 、 $q$ 和 $x$ 。
第二行包含 $n$ 个整数 $a_i$ 。
接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$ 。

$n \quad q \quad x$

$a_1 \quad a_2 \quad \ldots \quad a_n$

$l_1 \quad r_1$

$l_2 \quad r_2$

$\ldots$

$l_q \quad r_q$

Output#

对于每个询问输出 yes 或 no 。

Sample Input#

Sample Output#

yes
no
yes
no

题目要点解析#

针对区间范围内查询某个点对或子区间是否存在，也就是 区间查区间 的问题，一种行之有效的策略是为每个可能的右端点 $r$ 寻找其对应的 最优左端点 l 。我们据此构建出一个 左端点数组 L ，其中 $L[i]$ 记录了以 $i$ 为右端点时，合法结构所能达到的最大左边界下标。由此，判断一个给定区间 $[l, r]$ 是否包含合法结构的准则便可以转化为：

\max(L_l, \ldots, L_r) \geq l

这一公式说明了只要区间内存在至少一个右端点对应的 最佳左端点并未越过询问区间的左边界 ，则该区间判定为有效。进一步观察可以发现，由于在逻辑构造上每个位置 $i$ 的最优左端点 $L[i]$ 必然满足 $L[i] \leq i$ ，这意味着对于任何 $k < l$ 的位置，其 $L[k]$ 必然也小于 $l$ ，对最终判定的贡献为负。这一关键性质允许我们将区间最值查询进一步简化，即上述公式等价于：

\max(L_l, \ldots, L_r) = \max(L_0, L_1, \ldots, L_r) \geq l

通过这一步转化，原本需要使用线段树或 RMQ 维护的区间最值问题，被成功转化成了简单的 前缀最大值 问题。我们仅需在线性时间内预处理出 前缀最大值数组 ，即可在 $O(1)$ 的时间内完成任何关于区间合法性的询问。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int MAX = 2e5 + 7;
5
const int VAL = 1 << 20;
6
int n, q, x;
7
int a[MAX], L[MAX];
8
int preMax[MAX];
9
int lastPos[VAL];
10

11
int main() {
12
    cin >> n >> q >> x;
13
    for (int i = 1; i <= n; i++) {
14
        cin >> a[i];
15
    }
16

17
    memset(lastPos, 0, sizeof(lastPos));
18
    for (int i = 1; i <= n; i++) {
19
        int target = a[i] ^ x;
20
        L[i] = lastPos[target];
21

22
        lastPos[a[i]] = i;
23
    }
24

25
    preMax[0] = 0;
26
    for (int i = 1; i <= n; i++) {
27
        preMax[i] = max(preMax[i - 1], L[i]);
28
    }
29

30
    for (int i = 0; i < q; i++) {
31
        int l, r;
32
        cin >> l >> r;
33
        if (preMax[r] >= l) {
34
            cout << "yes" << endl;
35
        } else {
36
            cout << "no" << endl;
37
        }
38
    }
39
}

高桥的心情期望#

题目链接

Problem Statement#

高桥君将会收到 $N$ 个礼物。高桥君有一个名为 “情绪” 的参数，这是一个非负整数，每当他收到一个礼物时，情绪值就会发生变动。每个礼物都有三个参数：价值 $P$ 、情绪增加量 $A$ 、情绪减少量 $B$ 。

根据这些参数，他的情绪变动规则如下：

如果收到的礼物价值 $P$ 大于或等于 他当前的情绪值，他会对礼物感到高兴，情绪值增加 $A$ 。
如果收到的礼物价值 $P$ 小于他当前的情绪值，他会对礼物感到失望，情绪值减少 $B$ 。但是，如果减完后的情绪值小于 0，则情绪值变为 0。

现在给定 $Q$ 个询问，请回答所有询问。在第 $i$ 个询问中，给定一个初始情绪值 $X_i$ ，请计算：如果高桥君的初始情绪值为 $X_i$ ，在按顺序收到全部 $N$ 个礼物后，他最终的情绪值是多少？

Constraints#

$1 \leq N \leq 10000$
$1 \leq P_i \leq 500$
$1 \leq A_i \leq 500$
$1 \leq B_i \leq 500$
$1 \leq Q \leq 5 \times 10^5$
$0 \leq X_i \leq 10^9$

Input#

输入包含多行：

第一行包含一个整数 $N$ 。
接下来的 $N$ 行，每行包含三个整数 $P_i$ 、 $A_i$ 和 $B_i$ 。
接下来一行包含一个整数 $Q$ 。
接下来 $Q$ 行，每行包含一个整数 $X_i$ 。

$N$

$P_1 \quad A_1 \quad B_1$

$P_2 \quad A_2 \quad B_2$

$\ldots$

$P_N \quad A_N \quad B_N$

$Q$

$X_1$

$X_2$

$\ldots$

$X_Q$

Output#

输出 $Q$ 行，每行包含一个整数，表示对应询问的最终情绪值。

Sample Input#

Sample Output#

题目要点解析#

本题的核心挑战在于处理极大量的询问 $Q = 5 \times 10^5$ ，这使得常规的 $O(NQ)$ 模拟无法在时限内完成。解题的关键突破口在于挖掘题目给出的参数限制：由于礼物的价值 $P_i$ 、情绪增加量 $A_i$ 和减少量 $B_i$ 均不超过 $500$ ，高桥君的情绪值在变化过程中表现出明显的收敛特性。当初始情绪值 $X$ 远大于 $500$ 时，他会因为眼光过高而对收到的礼物持续感到失望，导致情绪值呈线性下降趋势。这种下降会一直持续，直到情绪值跌入特定的波动区间 。

我们可以定义一个临界值 $M = 1000$ 。只要当前情绪值高于这个临界值，由于 $P_i \leq 500$ 的限制，高桥君必然会触发 情绪减少 $B_i$ 的逻辑。只有当情绪值降低到 $500$ 以下时，才可能因为 $X \leq P_i$ 而触发 情绪增加 $A_i$ 的逻辑。这里有一个非常重要的性质：情绪值一旦进入 $[0, 1000]$ 区间，就永远不会再超过 $1000$ 。这是因为触发增加逻辑的前提是 $j \leq P_i \leq 500$ ，即便加上最大的增加量 $A_i \leq 500$ ，结果也恰好维持在 $1000$ 。

针对临界区间内的变动，我们利用动态规划进行预处理。设 $dp[i][j]$ 表示在处理第 $i$ 个礼物前，当前情绪值为 $j$ ，在处理完剩余所有礼物后最终的情绪值。我们可以通过逆向推导来填充这个动态规划表：从最后一个礼物 $N$ 开始往前考虑，根据当前礼物 $i$ 的参数计算出处理完该礼物后的新情绪值 $j'$ 。

j' = \begin{cases} j + A_i & \text{if } j \leq P_i \\ \max(0, j - B_i) & \text{if } j > P_i \end{cases}

由于上述性质保证了 $j' \leq 1000$ ，状态转移可以简单地写为：

dp[i][j] = dp[i+1][j']

对于每个具体的询问 $X_i$ ，我们可以通过二分查找快速定位满足如下约束条件的最小下标 $k$ ：

X_i - sumB[k] \leq 1000

若在处理完所有礼物前找到了这个 $k$ ，则说明情绪值在第 $k$ 个礼物处跌入了预处理区间。此时，该询问的最终答案直接由 $dp[k+1][\max(0, X_i - sumB[k])]$ 给出。如果直到最后礼物领完，情绪值依然高于 $1000$ ，答案则是 $X_i - sumB[N]$ 。这种方法将查询复杂度降至 $O(\log N)$ ，能够完美解决大规模询问下的时限挑战。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
int N, Q;
5
int dp[10005][1005];
6
int P[10005], A[10005], B[10005];
7
long long preB[10005];
8

9
int main() {
10
    cin >> N;
11
    for (int i = 0; i < N; i++) {
12
        cin >> P[i] >> A[i] >> B[i];
13
        preB[i + 1] = preB[i] + B[i];
14
    }
15

16
    // 逆向 DP 预处理
17
    for (int j = 0; j <= 1000; j++) {
18
        dp[N][j] = j;
19
    }
20
    for (int i = N - 1; i >= 0; i--) {
21
        for (int j = 0; j <= 1000; j++) {
22
            int next_j;
23
            if (P[i] >= j) {
24
                next_j = j + A[i];
25
            } else {
26
                next_j = max(0, j - B[i]);
27
            }
28
            dp[i][j] = dp[i + 1][next_j];
29
        }
30
    }
31

32
    cin >> Q;
33
    while (Q--) {
34
        ll x; cin >> x;
35
        int k = lower_bound(preB, preB + N + 1, x - 1000) - preB;
36

37
        if (k > N) {
38
            cout << x - preB[N] << endl;
39
        } else {
40
            ll val = max(0LL, x - preB[k]);
41
            cout << dp[k][(int)val] << endl;
42
        }
43
    }
44
}