A. Add and Divide

首先最优解一定是 ++b 若干次(可能为 $0$ ),然后再一直做 a=a/b 直到符合条件。

考虑最差的情况:$a=10^9,b=1$ ,至多只需 $1+\lceil \log_2{10^9}\rceil = 31$ 次,所以所有答案都 $\le 31$。

因此枚举++b 的操作次数 $k\ (0\le k\le 31)$ ,然后暴力计算答案即可,复杂度 $\text O(t\log^2 a)$ 。

B. Replace and Keep Sorted

考虑 $b_i\not =a_i$ ,那么考虑 $b_i$ 的取值范围:

  • 对于 $i=l$ 的情况, $1\le b_i<a_{i+1}$ ,与 $a_i$ 不同的方案有 $a_{i + 1} - 2$ 个。

  • 对于 $i=r$ 的情况, $a_{i-1}<b_i\le k$ ,与 $a_i$ 不同的方案有 $k - a_{i-1} - 1$ 个。

  • 对于 $l<i<r$ 的情况, $a_{i-1}<b_i<a_{i+1}$ ,与 $a_i$ 不同的方案有 $a_{i+1}-a_{i-1}-2$ 个。

$i$ 不同的贡献是独立的,所以用前缀和优化一下第三部分的计算,各个位置的方案数求和即可。

C. Floor and Mod

设 $\lfloor a/b\rfloor=a\ \text{mod}\ b=k$ ,根据整除理论,有 $a=k *b+k$ ,且 $k < b$ 。

考虑枚举 $k$ ,去数可行的 $b$ ,那么限制条件有:$1\le b \le y\ ,\ 1\le k*b+b=a\le x$

移项,得 $1\le b\le \min(y,\ x / k - 1)$ ,即 $k$ 的贡献为 $\min(y,\ x/k - 1)$ 。

又由 $k\le b$ 得 $k ^2 < k * b+k = a\le x$ ,得 $k\le \sqrt x$ ,因此 $O(t\sqrt x)$ 枚举 $k$ 直接计算即可。


比赛时用的另一种做法,复杂度也是 $\text O(t\sqrt x)$ :

考虑枚举 $b$ ,由上知可行的 $a = k *(b+1)$ 且 $1\le k\le b-1$ 。

考虑枚举 $b$ ,则贡献为 $\min(b-1,\lfloor x/(b + 1)\rfloor)$ ,具体的:

  • 当 $(b+1)(b-1)\le x$ 时,即 $b \le \sqrt{x + 1}$ 时,贡献为 $b-1$ ,可以等差数列求和。

  • 否则贡献取 $\lfloor x /(b + 1)\rfloor$ ,整除分块计算即可。

D. Multiples and Power Differences

数据范围 $1\le a_{i,j}\le 16$ ,观察:

  • $\text{lcm}(1,2,\cdots,16)=720720\le 10^6 - 10^5$

  • $16^4 = 65536\le 10^5$

将矩阵黑白染色,黑色变为 $720720$ , 白色变为 $720720+x^4$ 即可 ( $x$ 为原矩阵对应位置的数)

E. Move and Swap

设 $f[u]$ 表示红点在 $u$ 时,$u$ 及其子树的最大得分。

若红蓝不交换,假设红色在 $u$ ,则最优解本质上是 $u$ 儿子最大得分 + 同深度点与 $u$ 点权最大差值。

若红蓝交换,则本质是任选同深度节点 $v$ 的最优儿子,及 $v$ 与 $u$ 点权差值。

那么转移方程具体的(设 $d[u]$ 表示节点 $u$ 的深度):
$$
f[u] = \max \bigg \{ \max_{s\in son[u]} f[s] + \max_{d[v] = d[u]} | a_u - a_v |\ ,\ \max_{d[v]=d[u]}\bigg(|a_u-a_v| + \max_{s\in son[v]} f[s]\bigg)\bigg \}
$$
可以发现转移是从深到浅转移的。第一部分直接枚举儿子转移即可,第二部分维护:

$$
mxp[d] = \max_{d[v]=d}\bigg(a_v + \max_{s\in son[v]} f[s]\bigg)\ ,\ mxm[d] = \max_{d[v]=d}\bigg(-a_v + \max_{s\in son[v]} f[s]\bigg)
$$

则第二部分的转移就可以表示为 $f[u] = \max\{mxp[d[u]] - a[u],mxm[d[u]]+a[u]\}$ 。

F. Copy or Prefix Sum

假设当前处理到第 $i$ 位,前 $i-1$ 位的和为 $S$ ,那么 $a_i=b_i$ 或者 $a_i=b_i-S$ 都是可以的。

那么答案为什么不是 $2^n$ 呢?因为 $S=0$ 时会重复计数。

设 $f_{i,S}$ 表示前 $i$ 位填完,前缀和为 $S$ 的方案数,那么转移为:

  • $a_i=b_i$ : $\forall S\ ,\ f_{i+1,S+b_i} += f_{i,S}$

  • $a_i = b_i -S$ : $\forall S\ ,\ f_{i+1,b_i}+=f_{i,S}$ ,即 $f_{i+1,b_i}=\sum_{\forall S} f_{i,S}$

  • $S=0$ 去重:$f_{i+1,b_i} -= f_{i,0}$

综上,$i\to i+1$ 转移的过程即为:所有的 $f$ 整体向右偏移 $b_i$ ,然后对 $f_{b_i}$ 单独赋值。

因此省略第一维,使用 map 维护第二维,用记录整体偏移量的方法优化。

记录 $tot=\sum_{k=1}^ib_k\ ,\ ans=\sum_{\forall S} f_S$ ,递推即可,实现见 代码