T1

100%

根据题目描述，及格、良好、优秀的成绩区间分别为 $[60, 79]$，$[80, 89]$，$[90, 100]$。

要使总分最大，我们需要让每个科目的分数尽可能高。因此，假设所有及格的科目都是 $79$ 分，良好的科目都是 $89$ 分，优秀的科目都是 $100$ 分。总分的最大值即为 $a \times 79 + b \times 89 + c \times 100$。

同理，要使总分最小，我们需要让每个科目的分数尽可能低。假设所有及格的科目都是 $60$ 分，良好的科目都是 $80$ 分，优秀的科目都是 $90$ 分。总分最小值即为 $a \times 60 + b \times 80 + c \times 90$。

时间复杂度 $O(1)$。

T2

100%

设按 $A$ 按钮的次数为 $x$，则按 $B$ 按钮的次数为 $n - x$。

我们需要在 $0 \sim n$ 的范围内找出一个整数 $x$，使得总得分满足 $x \times a + (n - x) \times b = k$ 成立。

由于 $n \leq 1000$，我们可以直接使用一层循环，枚举 $x$ 从 $0$ 到 $n$。对于每个枚举到的 $x$，如果上式等号成立，说明存在这种按键组合，输出 YES 即可。

如果在循环结束后依然没有找到任何满足条件的 $x$，说明无论如何组合也无法得到恰好 $k$ 分，输出 NO。

单组数据时间复杂度 $O(n)$，对于 $T$ 组数据总时间复杂度为 $O(Tn)$。

T3

40%

根据题意，我们需要找出满足条件的三元组 $(i, j, k)$。对于较小的数据范围，可以直接使用三重循环枚举 $i, j, k$（其中 $1 \leq i < j < k \leq n$），然后判断是否满足 $\min(A_i, A_k) \leq |A_i - A_k|$。如果满足则将答案加一。

时间复杂度 $O(n^3)$。

100%

我们观察到题目中的条件 $\min(A_i, A_k) \leq |A_i - A_k|$ 完全与 $j$ 以及 $A_j$ 无关。

不妨假设 $A_i \leq A_k$，则 $\min(A_i, A_k) = A_i$ 且 $|A_i - A_k| = A_k - A_i$。代入条件可得 $A_i \leq A_k - A_i$，化简即 $2 \times A_i \leq A_k$。 综合可能的大小关系，该条件在所有情况下都等价于 $\max(A_i, A_k) \ge 2 \times \min(A_i, A_k)$。

由于条件是否成立只与 $i$ 和 $k$ 有关，因此只要固定了 $i$ 和 $k$ 且两者满足上述条件，所有处于 $i$ 和 $k$ 之间（即 $i < j < k$）的 $j$ 都是合法的。这样的 $j$ 共有 $k - i - 1$ 个。

于是，我们只需两重循环枚举 $i$ 和 $k$（$1 \leq i < k \leq n$），如果满足 $\max(A_i, A_k) \geq 2 \times \min(A_i, A_k)$，就将总方案数加上 $k - i - 1$。

另外，满足条件的三元组数量最大可能达到 $\approx n^3 / 6 \approx 2 \times 10^{10}$，所以累加答案的变量必须使用 long long 以避免溢出。

时间复杂度 $O(n^2)$。

T4

30%

当 $n, a_i, b_i \leq 100$ 时，所需要的最小初始能量非常小。可以直接从 $1$ 递增枚举初始能量，并在内层循环中模拟依次闯关的过程。如果枚举到的能量能保证全流程不出现能量 $<a_i$ 的情况，则输出该能量并结束。

时间复杂度 $O(n \times ans)$。

100%

解法一：二分答案

假设面对第 $i$ 个关卡时有 $x$ 点能量，通关后能量变为 $f(x) = x - a_i + \min(x - a_i, b_i)$。 因为随着 $x$ 的增加，$x - a_i$ 严格增加，所以 $f(x)$ 显然是关于 $x$ 的单调递增函数。这说明如果初始能量 $X$ 能够顺利通关，那么大于 $X$ 的初始能量也一定能通关。既然具有单调性，我们可以采用二分搜索的方法求解最小初始能量。

二分的上限可以设为所有 $a_i$ 的总和（最大可达到 $10^{14}$ 级别）。每次二分出一个 $X$ 后，通过 $O(n)$ 模拟判断是否会出现失败即可。

时间复杂度 $O(n \log(\sum a_i))$。

解法二：倒推法

定义 $E_i$ 为通过第 $i \sim n$ 关所需要的最小能量。通关所有关卡后剩余能量至少为 $0$，因此初始有 $E_{n+1} = 0$。我们需要倒推求 $E_1$。 假设已知通过后续关卡所需的最小能量为 $E_{i+1}$。在面对第 $i$ 个关卡时，我们具有的能量为 $x$（必须满足 $x \ge a_i$）。设消耗 $a_i$ 后剩余的能量为 $y = x - a_i \ge 0$。 那么通过第 $i$ 个关卡后的能量就变为了 $y + \min(y, b_i)$，要使后续关卡顺利通过，我们需要满足 $y + \min(y, b_i) \geq E_{i+1}$。 考虑求出满足该式的最小的非负整数 $y$：

• 如果 $E_{i+1} \leq 2b_i$，此时 $y \leq b_i$，方程化为 $2y \geq E_{i+1}$，可得最小的 $y = \lceil E_{i+1} / 2 \rceil = \lfloor(E_{i+1} + 1) / 2\rfloor$；
• 如果 $E_{i+1} > 2b_i$，此时必有 $y > b_i$，方程化为 $y + b_i \geq E_{i+1}$，可得最小的 $y = E_{i+1} - b_i$。

求出最小的 $y$ 后，便能得到 $E_i = y + a_i$。从 $i=n$ 倒序递推到 $i=1$，便可一次性在线性时间求出 $E_1$。

时间复杂度 $O(n)$。

T5

40%

当 $m \leq 100$ 时，可以直接使用三维动态规划 $dp[i][j][k]$ 表示已经确定了前 $i$ 个数字，且第 $i$ 个数字为 $j$，前 $i$ 个数字的总和为 $k$ 的合法方案数。状态转移时枚举下一个数字即可。

时间复杂度约 $O(n m^2 / 2)$。

100%

实际上本题是在求 $m$ 的 $n$ 分拆，具体可以参考 分拆数 这个链接。

可以使用动态规划。设 $dp[i][j]$ 表示将整数 $j$ 划分为 $i$ 个正整数的方案数。

转移方程可以通过两种情况讨论：

1. 划分中包含至少一个 $1$：等价于将 $j-1$ 划分为 $i-1$ 个正整数（即 $dp[i-1][j-1]$，可以理解成所有满足 $j - 1$ 划分为 $i - 1$ 个整数的方案的末尾放了一个 $1$ ）。
2. 划分中所有数都大于 $1$：我们可以将所有 $i$ 个数都减去 $1$，对应的方案数为将 $j-i$ 划分为 $i$ 个正整数（即 $dp[i][j-i]$，可以理解成所有满足 $j - i$ 划分为 $i$ 个整数的方案中所有数字都加了 $1$）。

故状态转移方程为：

$$dp[i][j] = (dp[i-1][j-1] + dp[i][j-i])$$

边界状态为 $dp[0][0] = 1$。记得要对 $998244353$ 取模。

在处理每个查询时，只需 $O(1)$ 输出 $dp[n][m]$ 即可。时间复杂度 $O(nm + T)$。

T6

10%

对于 $n \leq 10$，题目中的前置知识点关系构成了一个小规模的有向树林。

我们可以通过递归或 next_permutation 暴力生成该依赖图的所有合法的拓扑排序方案。将这些序列生成完毕后按字典序排序，并直接查找有几个序列比给定的方案 $A$ 字典序更小。

时间复杂度 $O(n!)$ 。

100%

在 知识点学习2 中，已经学习过给定一个森林（树）求其拓扑排序的方案数。这里不再赘述。可以简单化简 [知识点学习2] 中的状态转移方程，可以得到：

$$dp[u] = \frac{(sz[u] - 1)!}{\prod_{i=1}^k (sz[v_i]!)} \times \prod_{i=1}^k dp[v_i] $$

其中 $v_i$ 指的是 $u$ 的子节点。

现在回到原问题：求字典序小于 $A$ 的拓扑排序方案数。

求字典序更小的排列的经典做法是：枚举序列在哪一位（设为第 $i$ 位）“首次偏小”。

首先在 $i$ 从小变大的过程中，我们维护一个集合 $S$，表示当前所有“前置知识点已经学习完毕，可以立刻学习”的知识点（即当前森林的所有树根）。同时我们记 $S_i$ 表示按照前 $i$ 个点填之后的可以立即学习的知识点集合。初始时，$S$ 包含所有 $p_j = 0$ 的节点。

假设前 $i-1$ 位我们都紧跟着原排列 $A$，在第 $i$ 位我们选择了一个不同的、且编号小于 $A_i$ 的合法节点 $v$（即 $v \in S_{i - 1}$）。那么接下来还剩下 $n-i$ 个位置需要排。

为了之后计算的方便，我们记 $base$ 为：把当前集合 $S_{i - 1}$ 中的所有子树直接混合排列，总的组合方案：

$$base = \frac{(n - i + 1)!}{\prod_{r \in S_{i - 1}} (sz[r]!)} \times \prod_{r \in S_{i - 1}} dp[r] $$

但是，因为我们强制选了 $v$ 排在当前位，这相当于剥离了 $v$ 作为树根的限制，同时多了 $v$ 的子节点构成的树，即此时剩余未排节点构成的森林根节点集合恰好是 $(S_{i - 1} \setminus \{v\}) \cup \{v \text{的子节点} \}$。此时的方案为：

$$\begin{aligned} \frac{(n - i)!}{\prod_{r \in S_{i - 1} \cap r \not = v } sz[r]! \times {\prod_{c \in \text{children}(v) }sz[c]!} } \times \big( \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \times \prod_{c \in \text{children}(v) }dp[c] \big) \end{aligned} $$

其中 $\text{children}(v)$ 表示 $v$ 的子节点构成的集合。

考虑对上述式子进行化简：

$$\begin{aligned} & \frac{(n - i)!}{\prod_{r \in S_{i - 1} \cap r \not = v } sz[r]! \times {\prod_{c \in \text{children}(v) }sz[c]!} } \times \big( \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \times \prod_{c \in \text{children}(v) }dp[c] \big)\\ = & \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1} \cap r \not = v } sz[r]! } \times \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \big) \times \big( \frac{1 }{\prod_{c \in \text{children}(v) }sz[c]!} \times \prod_{c \in \text{children}(v) }dp[c] \big) \\ = & \big( \frac{(n - i)! \times sz[v]! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \big) \times \big( \frac{1 }{\prod_{c \in \text{children}(v) }sz[c]!} \times \prod_{c \in \text{children}(v) }dp[c] \big) \\ = & \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \big) \times \big( \frac{sz[v]! }{\prod_{c \in \text{children}(v) }sz[c]!} \times \prod_{c \in \text{children}(v) }dp[c] \big) \\ = & \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \big) \times \big( \frac{(sz[v] - 1)! }{\prod_{c \in \text{children}(v) }sz[c]!} \times \prod_{c \in \text{children}(v) }dp[c] \big) \times sz[v] \\ = & \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} \cap r \not = v }dp[r] \big) \times dp[v] \times sz[v] \\ = & \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} }dp[r] \big) \times sz[v] \\ = & (\frac{base}{n - i + 1}) \times sz[v] \end{aligned} $$

也就是说，如果我们第 $i$ 个位置选了 $v$，那么此时对答案的贡献便是 $(\frac{base}{n - i + 1}) \times sz[v]$，故如果是在第 $i$ 个位置开始与 $A$ 不同，它的方案数是：

$$\frac{base}{n - i + 1} \times (\sum_{v \in S_{i - 1} \cap v < A_i} sz[v]) $$

可以发现，$(\sum_{v \in S_{i - 1} \cap v < A_i} sz[v])$ 这一步我们可以很方便的用树状数组或者线段树进行维护，只需要加入节点 $x$ 时在树状数组对应位置加 $sz[x]$，移除时减 $sz[x]$。而$\frac{base}{n - i + 1} = \big( \frac{(n - i)! }{\prod_{r \in S_{i - 1}} sz[r]! } \times \prod_{r \in S_{i - 1} }dp[r] \big)$ 可以在维护 $S_{i - 1}$ 的时候顺便计算出来。

时间复杂度为 $O(n \log n)$。