0%

题解 09

耶。

2021 CCPC 网络赛 重赛 1005 Monopoly

大富翁棋盘,一圈一共 $n$ 个数 $a$,代表走到此格时获得的分数(可以是负数)。初始分数为 $0$,从第一个格子开始走,一次走一格。给定 $m$ 次询问 $x$,输出最少几步恰好能获得 $x$ 分,不能则输出 $-1$。走 $0$ 步即可得到 $0$ 分。
$1\le T \le 20, 1\le n, m\le 10^5, -10^9\le a_i\le 10^9, -10^{12}\le x\le 10^{12}, \sum n \le 5\times 10^5, \sum m \le 5\times 10^5$

类似 CF 上的这道题,都需要把整体的前缀和作为走一趟下来的变化量。

有了前缀和 $p_i$,我们的问题就变成了:针对每个询问 $x$,在 $p$ 里寻找下标 $i$,使

  1. $p_i + k\cdot p_n = x, k\in N$
  2. $i + k \cdot n$ 最小

显然符合条件的 $p_i$ 必须与 $x$ 对变化量同余。如果变化量为正,我们需要找到不大于 $x$ 的最大 $p_i$,多个符合条件的 $p_i$ 中取最小下标;如果变化量为负,将所有的 $p_i$ 以及 $x$ 变号,转化处理;变化量为 $0$ 时,在 $p_i$ 里找第一个出现的 $x$ 即可。注意,因为存在负数,取余的时候需要修正到正数。

于是我们可以把所有的 $p_i$ 都对变化量取余,结果相同的下标存在一起,其中如果有多个 $p_i$ 值相同,只有最小下标是我们需要的。这是一个 map 套 map,由余数可以查到所有的 $p_i$ 值,由 $p_i$ 值又可以查到第一次出现位置。最后用 map 的 lower_bound 就能做了。不用哈希的话复杂度 $O(n\log^2 n)$。

要特别注意的地方是在 map 里面查找的方式。如果直接用它重载过的下标去看有没有存值,会让 map 新建值容器,可能炸空间。另外,记下所有的 $p_i$ 位置不会炸空间,但是后面为二分做排序时要枚举 map 里面已经存好的键值对,枚举所有余数会超时,同时二分之后的逻辑也比较麻烦,一定要考虑全。

牛客 19483 B 智乃酱的子集与超集

定义一个集合的价值为其所有元素的异或和。长度为 $N$ 的一列数 $a$, 给定一组下标,表示数列的一个子集 $U$,输出 $U$ 所有子集的价值之和,以及所有超集的价值之和。全集为数列 $a$。
$1\le N\le 20, 1\le M\le 10^5, 1\le a_i\le 10^6$

只是记一个比较巧的东西。

二进制枚举所有可能的组合,对于一种组合 $j$ 枚举每个位,算出它这个集合的价值。

现在我们有各个子集的价值了,接着做子集或者超集价值和。以子集为例,枚举每个下标,对于一个下标 $i$,枚举所有组合的第 $i$ 位,如果为 $1$,则这一位变成 $0$ 可以得到一个子集,那么加上它。虽然加上的下标只去掉了一个元素,但是其中的内容已经包含了前几个元素去掉没去掉的所有组合。

CF 1459 C Row GCD

两个正整数序列 $a_i$,$b_j$,分别长 $n$ 和 $m$。对于每个 $j\in [1, m]$,输出 $a_1 + b_j, a_2 + b_j, \cdots , a_n + b_j$ 的最大公因数。
$1\le n, m\le 2\times 10^5, 1\le a_i, b_j\le 10^{18}$

这里需要一个从辗转相除法看出的结论:

从后面的所有项里减去第一项,结论不变,但是不再需要考虑 $b_j$ 和 $a_i$ 的组合。预处理一下然后对于每个 $a_1 - b_j$ 做一次 $\gcd$ 即可。

CF 1398 C Good Subarrays

只有 $0$ 到 $9$ 的数列 $a_i$,找出所有的数对 $(l, r)(l\le r)$,使得 $\sum_l^r a_i = r - l + 1$。求数对数量。
$1\le t\le 1000, 1\le n \le 10^5, \sum n \le 10^5$

对原来的式子变形:

于是我们只需要寻找两个下标 $i$,$j$,$presum_i - i = presum_j - j$。注意 $i < j$,因为 $r$ 与 $l$ 可能相等。

做完前缀和之后处理一下,用 map 对相同差计数,算一下就好了。

CF 1349 A Orac and LCM

一个数列 $a_i$,求出其中所有数对最小公倍数的最大公约数,即 $gcd(\{lcm(a_i, a_j) | i < j\})$。
$2\le n\le 10^5, 1\le a_i\le 2\times 10^5$

固定 $i$ 去枚举所有的 $j$,得到 $n - i$ 个数对,那么只要快速算出 $\gcd (\mathrm{lcm} (a_i, a_{i + 1}), \mathrm{lcm} (a_i, a_{i + 2}), \cdots, \mathrm{lcm} (a_i, a_{n}))$,然后对于每个 $i$,把算出的 gcd 一起求一个 gcd 就是答案。

这里用到一套结论性的东西,就是 $\gcd$ 和 $\mathrm{lcm}$ 的分配律:

这个可以从数论角度证明,但是这个知乎回答好像有点问题。可以分解质因数再从幂次上去证,比较丑。应该也能从代数系统证,和 $\max$、$\min$ 应该是“同构”的。加引号是因为较大较小操作都不是群,没有逆元。

那就把

化成了

然后就很好做了。结论题。