LibreOJ β Round 题解

liu_cheng_ao 2017-06-16 22:24:50 2017-06-17 15:04:17

A. ZQC 的拼图(CommonAnts)

题解由 CommonAnts 提供。

可能有人卡题意 …… 我已经尽力写清楚了 …… QWQ …… 就是用拼图板把左下角和右上角连起来 …… 可以给所有拼图边长同时扩大一个整数倍,求最小的倍数。

初看此题可能会被 \frac{1}{a_i} \frac{1}{b_i} 坑一下……不过一定要相信 CommonAnts 是个良心出题人。

只需 Y(推)Y(推)一(式)下(子)就会发现其实不同拼图板的顺序是没有影响的,只要把它们的顺序换一下,保持每块拼图板右上角和上一块的右上角相对位移不变即可。一定存在一个最优解是用了所有的拼图板,并且拼图板的直角顶点在两个方向上都是非递减的。

为了叙述方便,我们设拼图板下边沿为 x 轴,左边沿为 y 轴,左下角为原点 (0, 0) ,第 i 块拼图板直角顶点为 (x_i, y_i) ,特别地,规定 x_0 = y_0 = 0

于是我们不妨假设

\begin{cases} x_i\leq x_{i+1} \\ y_i\leq y_{i+1} \end{cases} \quad i \in [0, n)

则存在一条从左下到右上的路径的充要条件为

\begin{cases} x_n = y_n = m & \\ a_{i + 1} (x_{i + 1} - x_i) + b_{i + 1} (y_{i + 1} - y_i) \leq k & \quad 1 \leq i < n \end{cases}

\forall i, f(i) \leq k 的形式,显然可以二分 k

判定的时候有多种方法,例如令 f(i, j, k) 表示考虑前 i 块拼图,能否到达 (j, k) ,最后判定结果为 f(n, m, m) 。一种朴素转移是 f(i, j, k) = \mathop{\text{or}} \limits_{[f(i - 1, x, y) = 1]} a_i(x_i - x) + b_i (y_i - y) \leq k ,时间复杂度 O(nm ^ 4 \log a) ,其中 a 表示权值范围。
稍加优化的转移是 f(i, j, k) = [a_i x_i + b_i y_i - k \leq \mathop{\max} \limits_{[f(i - 1, x, y) = 1]} a_i x + b_i y]
用前缀最值实现,此方法时间复杂度为 O(nm ^ 2 \log a)

另一种判定方法是令 f(i,j) 表示考虑前 i 块拼图,横坐标到达 j 时纵坐标的最大值,这样可以直接用 f(i,j)=\mathop{\max} \limits_{l=j-\lfloor \frac{k}{a_i} \rfloor}^j f(i-1,l)+\lfloor \frac{k-a_il}{b_i} \rfloor 转移,最后看 f(n,m) 是否不小于 m 即可。时间复杂度仍然是 O(nm ^ 2 \log a)


原题其实是一道经典调度问题,如果是这道题的话,相信各位都能秒掉:

有两种任务,每种 m 个;有 n 台机器,第 i 台机器完成第一种任务需要 a_i 时间,完成第二种任务需要 b_i 时间。
每台机器在同一时刻只能做一个任务,一个任务只能由一台机器独立完成。一台机器完成一个任务以后可以接着做任何一个任务。求完成所有任务需要的最短时间。

参见:https://loj.ac/submission/4190

B. ZQC 的树列(Menci)

题解由 Menci 提供。

首先,我们考虑如果给出了序列 A ,要如何求出它的特征值。

对于一个序列 A ,其本身一定是其美观度最大的子序列,所以问题转化为 —— 求有多少子序列的美观度等于 A 本身的美观度,换一种说法,有多少种方法去掉零个或多个数,使得其特征值不变。

为了方便,我们将相邻的相等的数合并,设转化后的第 i 的数为 a_i ,出现了 b_i 次。考虑相邻的三个数,如果这三个数组成一个单调序列,则中间的数可以被删除(若 a_{i} < a_{i + 1} < a_{i + 2} a_{i} > a_{i + 1} > a_{i + 2} ,则 |a_{i} - a_{i + 1}| + |a_{i + 1} - a_{i + 2}| = |a_{i} - a_{i + 2}| ),这样可以标记出所有「可被删除」的数。而第一个数和最后一个数应为「不可被删除」的数。对于「可被删除」的数, b_i 个数都能被删除或不删除,答案乘上 2 ^ {b_i} ,对于其它的数, b_i 个数中有 b_i - 1 个数可以被删除或不删除,答案乘上 2 ^ {b_i - 1}

回到构造问题上来,我们知道一个序列的特征值一定是 2 ^ k 乘上若干个 2 ^ k - 1 的形式,使用记忆化搜索的方法将其这些 2 ^ k - 1(k > 1) 分解出来,如果无法分解,则无解。

考虑如何构造「可被删除」的数和「不可被删除」的数,这里给出一种构造方法:

  1. 如果没有「不可被删除」的数(实际上,这种情况为,只有第一个数和最后一个数是「不可被删除」的数,并且它们都只有一个),则先输出一个 1 ,然后输出若干个 2 ,数量等同于 2 ^ k 中的 k ,最后输出一个 3
  2. 否则,交替输出等同于 2 ^ k - 1 的数量的若干组 1 3 ,每组 1 3 的数量等同于每个 2 ^ k - 1 中的 k ,在第一组 1 之后输出若干个 2 ,数量等同于 2 ^ k 中的 k

可能会有人使用从大到小贪心分解的做法,然而不幸的是,当 2^k-1 能整除 \prod_{i=1}^{k-1}(2^i-1) 时,不难构造出一个选取 2^k-1 就会导致输出无解的反例。一个反例是 315=63\times 5=3\times 7\times 15

采用记忆化搜索的话,时间复杂度为 O(\tau (n)\log n)

参见:https://loj.ac/submission/4186

C. ZQC 的截图(CommonAnts)

题解由 CommonAnts 提供。

一句话题意:给一棵有根树,每个节点一种颜色,支持动态加叶子,并且在线回答加入的叶子到根路径上出现次数不是 3 的倍数的颜色有 0 个、 1 个还是多个,并要求在答案是 1 个时输出该颜色。

如果不要求在线,有一个简单的做法:DFS 一遍,并维护当前到根路径上每种颜色的出现次数,时间复杂度 O(m) ,空间复杂度 O(n+m)
那么一种想法是将这个做法改造成在线版本,然而这样就需要使用完全可持久化数组了。如果用可持久化线段树、可持久化二叉索引树或可持久化平衡树实现的话,时间复杂度 O(m \log n) ,空间复杂度 O(n + m \log n) ,都不够。

确定性算法看起来无法轻易做到更优的时空复杂度了。考虑一下蒙特卡洛算法。

我们可以在模 3 意义下给每个颜色(人)一个随机权值,然后如此判断(以下运算均在模 3 意义下进行):

  1. 到根路径权和为 0 时,答案为 -1
  2. 到根路径权和不为 0 时,若存在一个颜色的权值的 1 倍或 2 倍和这个值相等,就认为这个颜色是答案。
  3. 否则答案为 -2

然而由于模 3 意义下只有 3 种权值,这个算法很容易出错。

不过没有关系!我们可以给每个颜色一堆随机权值(一个随机向量),然后捆绑在一起判断就可以提升正确率辣!
假设我们用了 w 个随机权值(即一个长为 w 的随机向量)。

由于加法运算的均匀性,任意有限多个互相独立的均匀随机的向量的和还是一个均匀随机的向量。同时由于 3 是质数,向量的数乘也拥有同样性质。
因此,每个点的到根路径上如果至少有一种颜色出现次数不是 3 的倍数,则到根路径上的权和可以看成一个均匀随机的向量。它恰好等于 \mathbf{0} 的概率为 \frac{1}{3^w}

运用同样的方法,可以证明如果发现到根路径权和与某个向量的 1 倍或 2 倍相等,判断错误的概率为 1-(1-\frac{1}{3^w})^n ,当 w 很大时,这个值趋近 \frac{n}{3^w} 。这比上面那个错误的概率高得多,因而可以近似认为一次的错误率为 \frac{n}{3^w}

因而 m 次中至少出错一次的概率为 1-(1-\frac{n}{3^w})^m ,当 w 很大时,它趋近 \frac{nm}{3^w}
只要选取一个合适的 w ,并用散列表(Hash 表)维护权值到编号的映射就可以在(将 w 看成常数) O(n+m) 时间和 O(n+m) 空间内解决问题了。
标准程序中 w=40 ,大约只有千万分之一的概率出错。

实现时建议使用 64 位无符号整数以三进制数的形式来存储,并对按位加法压位(标准程序中预处理了 3^7=2187 以内的运算结果)。

参见:https://loj.ac/submission/4194

D. ZQC 的课堂(MedalPluS)

题解由 CommonAnts 和 MedalPluS 提供。

首先 x y 的贡献是独立的。于是乎问题转化成了:一个序列 a ,四种操作:

  1. 指针左移;
  2. 指针右移;
  3. 修改指针位置的值;
  4. 询问有多少个位置 i 满足 (\sum\limits_{j = 1} ^ i a_j + 1)(\sum\limits_{j = 1} ^ {i - 1} a_j + 1) < 0

那么我们设 s_i = s_{i - 1} + a_i, s_0 = 1 (即 s_i 表示按前 i 个向量移动后的位置),于是乎问题转化成了:一个序列 s ,四种操作:

  1. 指针左移;
  2. 指针右移;
  3. 给指针位置之后的所有数加上某个值;
  4. 询问有多少个位置 i 满足 s_i s_{i - 1} < 0

可以发现: s_i s_{i - 1} < 0 等价于 \max (s_i, s_{i - 1}) > 0 \min(s_i, s_{i - 1}) < 0 。我们可以容斥求数量,也即总数减去 \max(s_i, s_{i - 1}) \leq 0 的数目再减去 \min(s_i, s_{i - 1}) \geq 0 的数目(题目保证不会有 0 )。
指针前面的部分是不受修改影响的,直接维护即可。
于是我们发现其实是分别维护两个集合 \{\max(s_i, s_{i - 1})\} \{\min(s_i, s_{i - 1})\} ,四种操作:

  1. 插入一个数;
  2. 删除一个数;
  3. 给所有数加上某个值;
  4. 询问不小(大)于 0 的数有多少个。

于是记下全局偏移量,随便写个平衡树就解决了。

参见:https://loj.ac/submission/4197


另外一种理解是:从 s_i s_{i+1} 连一线段。

我们先考虑这道题的一个简化版本:没有 B,F 操作。

那么其实就是:有 n 个数,要求支持:

  1. 全局加某个值。
  2. 查询有多少次 s_i s_j 的符号不同。即对应的线段覆盖了 0。

那么对于修改操作 1 的话,我们可以直接维护每个值被多少条线段覆盖了,并维护全局增量,然后查询的时候查 0 平移到的位置。

现在考虑存在 B,F 操作的情况。

对于指针的左边,它们不受修改操作的影响,直接维护即可。

对于指针的右边,可以用线段树维护每个值被多少条线段覆盖了,这样插入和删除线段是区间加减 1 操作。

时间复杂度 O(n\log n)

参见:https://loj.ac/submission/4200 (原作者 mps2000

E. ZQC 的手办(Dicint)

题解由 Menci 和 CommonAnts 提供。

正解是线段树+堆。
具体而言,就是用一棵线段树维护区间最小值及其位置,这个可以在单次 O(\log n) 时间内维护。
每次查询时,用一个堆查询区间最小的 x 个值,具体做法是:用一个四元组 (l,r,p,v) 表示区间 [l,r] 内, p 这个位置的值最小,值为 v ,以 v 作为比较的关键字维护一个最小堆。初始时把整个询问区间的查询结果放入堆中,然后重复以下操作 x 次:

  • 取出堆顶元素并加入答案
  • 如果 l<p ,把 [l,p-1] 的查询结果加入堆中
  • 如果 r>p ,把 [p+1,r] 的查询结果加入堆中

如果 v\geq x 或区间元素个数不足则答案为 -1
否则按顺序输出即可。

时间复杂度 O((n+\sum x)\log n) ,空间复杂度 O(n)

参见:https://loj.ac/submission/4202


以下是非正解但复杂度比暴力优秀的几个做法:


分块,用一个有序的数组维护每个块内的数,对每个块记录一个 k_i 表示小于等于 k_i 的都将变为 k_i ,整块的修改可以直接更新 k_i ,块内的修改 O(n \log n) 重构整个块。

查询时,将对于块外的数和每个块的第一个数放进堆中,从小到大从堆中取数,从堆中取出一个块中的数后,将该块中的下一个数放进堆中,直到取完或最小的数不够小为止。

总时间复杂度 O(x \sqrt {n \log n})

参见:https://loj.ac/submission/4204 (原作者 fjzzq2002


用吉司机在 Segment Tree Beats 中(参见 2016 年吉如一的国家集训队论文)开篇的方法,使用线段树套平衡树在 O((n+\text{output})\log ^3n) 时间, O(n\log n) 空间内解决本题, \sum x 无关是不是十分资磁。(三个 \log n 分别来自外层线段树的势能,每次修改 O(\log n) 个祖先以及每次修改平衡树的 O(\log n)

参见:https://loj.ac/submission/4218 (MLE)

F. ZQC 的游戏(Rapiz)

题解由 Menci 提供。

首先,求出所有能被 ZQC 吃掉的食物球,将它们的质量加入到 ZQC 的质量中;然后从剩余的食物球内标记出能被任意一个人吃掉的食物球,设这些球的质量总和为 s

建立网络,对(除 ZQC 外的)每个玩家和每个标记出来的(能被其它人吃掉的)食物球建点,另外加入源点 S 和汇点 T

  • S 到每个玩家连边,容量为 ZQC 的质量减去它的质量(表示这个玩家最多还能吃多少;如果为负,则方案不存在);
  • 从每个玩家到它能吃到的每个食物球连边,容量为正无穷大;
  • 从每个食物球到汇点连边,容量为它的质量。

如果网络的最大流等于 s ,则方案存在,否则方案不存在。

时间复杂度 O(\mathrm{Maxflow}(n+m,nm))

参见:https://loj.ac/submission/4187

G. ZQC 的作业(ZQC)

题解由 LWR 提供。

我们假设读者有基本的代数知识,包括群、环的定义,循环群。
需要用到进一步代数知识的地方都做了标注并将这部分的证明放在附录。
我们总是假设以字母 p q 代表的数是素数。

假设 k 是定值,记 f(m) 是模 m 意义下不同的 x^k 的数量。

首先,由中国剩余定理 f 是积性的,于是只需要计算 m=p^n 的情况(见附录 1)。下面假设 m=p^n

b p 互素,注意到 bp^k m 下是一个 k 次方幂当且仅当 b 是一个模 p^{n-k} 下的 k 次方幂。(对于「当」,设 b=x^k+tp^{n-k},\gcd(t,p)=1 ,则 (px)^k=p^kx^k+tp^{n-k}p^k ,在模 m 下它就是 b ,「仅当」是类似的。)

于是 f(p^n)=\sum\limits_{i=1}^{ik\le n} \psi(p^{n-ik}) ,其中 \psi(x) 指的是模 x 下与 x 互素的 k 次方幂数量。这个和式来自于分不同的 c 对形如 (xp^c)^k,\gcd(x,m)=1 k 次幂的统计。

问题归结于计算 \sum\limits_{i} \psi(p^{n-ik}) ,对 p\ne 2 ,熟知 Z_{p^{n-ik}} 的乘法群是循环的,于是它同构于 Z_{\phi(p_{n-ik})} ,计算 Z_{p^{n-ik}} 中的 k 次幂也就是计算 Z_{\phi(p_{n-ik})} k 的倍数,由此可以知道 \psi(p^{n-ik})=\frac{\phi(p^{n-ik})}{\gcd(\phi(p^{n-ik}),k)} (见附录 2)。对 p = 2 ,情况类似。

注意到 \phi(p^{n-ik})=p\phi(p^{n-(i+1)k}) ,从而数列 a_i=\frac{\phi(p^{n-ik})}{\gcd(\phi(p^{n-ik}),k)} 对前几项是常数列,对之后的项是等比数列,它的和不难求出。

时间复杂度 O(\mathrm{PrimeFactorization}(n)) 。如果用朴素算法,就是 O(\sqrt n)

参见:https://loj.ac/submission/4153


  1. m=\prod_{i}p_i^{r_i} ,中国剩余定理断言 Z_{m}\cong \prod Z_{p_i^{r_i}} (环同构),它们的乘法群也同构,从而 Z_{m} 上的 k 次幂就是(精确到同构) Z_{p_i^{r_i}} 上的 k 次幂之间的乘积。
  2. 考虑 Z_{\phi(p_{n-ik})} 上的自同态 f(x)=kx ,它的象就是那些被 k 整除的数,于是这些数的个数就是 \frac{\phi(p_{n-ik})}{|\ker f|} ,不难证明 \ker f 就是那些阶整除 k 的元素的集合,熟知这样的元素的个数是 \gcd(\phi(p^{n-ik}),k)

参见:http://hxlib.njnu.edu.cn/nsxr/Text%2F2009-10-10-10-12-00eqzg2dirgqldic55ra22ta55_模m的k次剩余个数.pdf

共 3 条回复

liu_runda

这个B题,因为可行的拆分也不是很少,其实可以随机化拆分一波. https://loj.ac/submission/6926

spj

考场上B题看出分解2^n和2^n-1出来,一开始想从大到小分解2^n-1,发现63炸了,就直接把63特判掉了 然后过了……

ceerrep

前排zici LOJ