A

读取字符串后计算。注意到python可以一句写完。

B

定义1. 重量区间函数为 $f(i,j) = a_{i} +a_{i+1}+\cdots a_{j}$。

性质1. 区间和满足可拆分性，即 $f(i,j) = f(1, j) - f(1, i - 1)$。

题目要求 $f(i, j) = k,i \leq j$ 的个数，由性质1得 $f(1,j) = k + f(1, i-1)$；现有等价条件

$$\begin{cases} f(1,j) =f(1, i - 1) + k \\ i - 1 < j \end{cases}$$

因为直接枚举 $i,j$ 时间是 $O(n^2)$ 的，所以使用空间换时间。

该问题是求值问题，记录值的个数，即形如 $k + f(1, i)$ 的值个数。统计时还需满足下标关系，顺着记录正好满足所有条件。

综上所述，每个 $i$ 时先统计答案，后记录 $k + f(1,i)$ 满足题意。

注意！初始有一个 $k + f(1,0) = k$ 需记录。

小结：空间换时间，值域查询，可分离变量等式 $F(j)=G(i)$。

C

bfs模板题，按题意模拟。

注意！dfs的写法可能爆栈。

D

题意，求所有选法中 $S\times G$ 最大的情况，并求其值。

朴素写法：枚举所有选法，因为每种选或不选有两种状态，所以时间复杂度为 $O(n2^n)$；

优化思路：枚举所有 “极大” 的情况，因为最大值必然在边界情况或极大情况中取到，所以能确保答案正确。

本题的 “极大” 函数是关于 $S,G$ 的多元函数，先从从偏导数角度分析，易得

$$S' \times G \geq S \times G \implies G \mid S' - S$$

反之亦然，表明这是一个充要条件。即当 $G$ 不变时，$S$ 内的数字越多越好。

结合边界情况和上述 “极大” 情况可知，答案必然为 $\underset{1 \leq G\leq 1000}{\mathrm{max}} \displaystyle \sum_{G \mid a_{i}} a_{i}$。

小结：优化枚举，极值贪心。

E

显然胜负只与质因数个数的奇偶性有关。但直接进行试除法会TLE！如下科技可用：

1. 直接试除，即算 $\sqrt{ n }$ 次（也是TLE的做法）；
2. 预处理后试除，因为除数大于等于二，由 $n \leq 2^{\log_{2} n + 1}$，所以最多除 $\log_{2}n + 1$ 次（题解使用）；
3. Miller-Rabin 素性测试，纯科技略过。

小结：除法行为的特殊值域复杂度 —— 试除法复杂度优化。

F

注意到 $E$ 形式类似于 $\displaystyle \int F(x)g'(x) \mathrm{d}x$，即连续版本的求和、连续版本的差分。连续版本下使用分部积分法可得 $\displaystyle F(x)g(x) - \int f(x)g(x)\mathrm{d}x$，离散情况下计算可得：

$$\sum_{i=1}^{n-1} \left( \sum_{j=1}^i b_{j} \right)(a_{i} - a_{i+1}) = \sum_{i=1}^{n-1} b_{i}a_{i} - \left( \sum_{i=1}^{n-1} b_{i} \right) a_{n}$$

该式子不难维护。若不进行此转化，可以考虑树状数组进行计算。