LibreOJ NOI Round #2 题解

cz_xuyixuan 2019-07-07 13:01:05 2019-07-15 21:48:50

Day 1

T1. 单枪匹马

By cz_xuyixuan,题解 By cz_xuyixuan

由于放在了第一题的位置,出题组没有刻意卡掉带 \log 的算法,相信本题应该能成为一道合格的送分题。

算法一

模拟题意,用 int/long long(32 位以上整数)计算出分子和分母的精确值,在进行约分后取模输出。

时间复杂度: O(NM)
预计得分: 5

算法二

仍然考虑计算出分子和分母的精确值,采用高精度实现算法一。

时间复杂度: O(N M (\log Ansx+\log Ansy))
预计得分: 20

算法三

考虑最简分数的如下性质:

  1. 如果 \frac{x}{y} 是最简分数,那么 \frac{y}{x} 也是最简分数。
  2. 如果 \frac{x}{y} 是最简分数,那么 a+\frac{x}{y}=\frac{x+ay}{y} 也是最简分数。

这是因为 \gcd(x,y)=1\Rightarrow \gcd(x+ay,y)=1

因此对于询问 [l,r] ,可以直接从 r 递推至 l ,得到对应的最简分数,而无需约分。

时间复杂度: O(N\times M)
预计得分: 35

算法四

不难发现算法三中在 f(a,\frac{x}{y}) 的分子和分母是由 x,y 经过线性变换得来的,可以直接用线段树维护线性变换的矩阵来实现快速查询。

时间复杂度: O(N+M\log N)
预计得分: 50 100

算法五

算法四中的矩阵都是可逆的,并且由算法三的性质可以归纳得出这些分子分母都是互质的,于是改用前缀积维护即可。

时间复杂度: O(N+M)
预计得分: 100

算法六

f([a_0;a_1,a_2,...,a_n]) \frac{p([a_0;a_1,a_2,...,a_n])}{q([a_0;a_1,a_2,...,a_n])} ,有

\frac{p([x;a_0,a_1,...,a_n])}{q([x;a_0;a_1,...,a_n])}=x+\frac{q([a_0;a_1,a_2,...,a_n])}{p([a_0;a_1,a_2,...,a_n])}=\frac{xp([a_0;a_1,a_2,...,a_n])+q([a_0;a_1,a_2,...,a_n])}{p([a_0;a_1,a_2,...,a_n])}

p([x;a_0,a_1,...,a_n])=xp([a_0;a_1,a_2,...,a_n])+q([a_0;a_1,a_2,...,a_n])

q([x;a_0;a_1,...,a_n])=p([a_0;a_1,a_2,...,a_n])

那么,将下式代入上式,可以得到

p([x;a_0,a_1,...,a_n])=xp([a_0;a_1,a_2,...,a_n])+p([a_1;a_2,a_3,...,a_n])

q([x;a_0,a_1,...,a_n])=xq([a_0;a_1,a_2,...,a_n])+q([a_1;a_2,a_3,...,a_n])

注意到我们在推导分子、分母的表达式时仅用到了求倒数、加常数两种操作,由算法三的观察,按照这样的表达式求解出的 p([x;a_0,a_1,...,a_n]),q([x;a_0,a_1,...,a_n]) 一定是互质的。

更进一步地考虑,上面的 p([a_0;a_1,...,a_n]) 给出了一个它很好的组合解释,一张 n+2 个点的有向图,标号为 0,1,2,...,n+1 i i+1 连边,边权为 a_i i i+2 连边,边权为 1 ,那么所有 0 n+1 的路径的边权积的和就是 p([a_0;a_1,...,a_n])

不难发现将所有边反向,所有 n+1 0 的路径的边权积的和同样也是 p([a_0;a_1,...,a_n]) ,因此有 p([a_0;a_1,...,a_n])=p([a_n;a_{n-1},...,a_0]) ,从而

p([a_0;a_1,...,a_n,x])=xp([a_0;a_1,a_2,...,a_n])+p([a_0;a_1,a_2,...,a_{n-1}])

类似地,可以得到

q([a_0;a_1,...,a_n,x])=xq([a_0;a_1,a_2,...,a_n])+q([a_0;a_1,a_2,...,a_{n-1}])

对于 l=1 的数据,我们只需要利用上述表达式递推即可得到询问每一个前缀的结果。

时间复杂度: O(N+M)
预计得分: 20
综合前述预计得分: 70

算法七

结合算法五的观察,类似于算法四,可以发现,在已有的序列 a_l,a_{l+1},\dots,a_r 后插入一个值 x ,得到的分子和分母都是序列 a_l,a_{l+1},\dots,a_r 和序列 a_l,a_{l+1},\dots,a_{r-1} 对应的分子分母经过线性变换得来的。

形式化地,记

mat_i=\begin{bmatrix} 0 & 1 \\ 1 & a_i \end{bmatrix},inv_i=\begin{bmatrix} -a_i & 1 \\ 1 & 0 \end{bmatrix}

序列 a_l,a_{l+1},\dots,a_r 所对应的分子 Ansx 即为

(\begin{bmatrix} 0\\ 1 \end{bmatrix}mat_lmat_{l+1}\dots mat_r)_{0,1}

对应的分母分子 Ansy 即为

(\begin{bmatrix} 1\\ 0 \end{bmatrix}mat_lmat_{l+1}\dots mat_r)_{0,1}

我们本质上希望快速求出 mat_lmat_{l+1}\dots mat_r

premat_0=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},premat_{i}=premat_{i-1}mat_i\\preinv_0=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},preinv_{i}=inv_ipreinv_{i-1}

那么 mat_lmat_{l+1}\dots mat_r=preinv_{l-1}premat_r

时间复杂度: O(N+M)
预计得分: 100

T2. 黄金矿工

By zx2003,题解 By zx2003

算法一

每次操作后 O(q!n) 暴力枚举每组合法匹配并且计算权值。

时间复杂度: O(q! qn)
预计得分: 4

算法二

定义状态 f_{i,j} 表示以 i 为根的子树中有 j 块黄金已经在匹配中。

每次操作后 O(q^2) 重新执行DP算法,即可获得答案。

时间复杂度: O(q^3)
预计得分: 8

算法三

我们可以建立费用流模型来解决本问题。

  1. 节点构造:

    • 新建源、汇节点;
    • 对与原树的每一个节点新建一个节点 v_i
  2. 边及流量(括号中的数字,前一个表示流量,后一个表示费用):

    • 对于一个点 i 上的,权为 w 的矿工 S \rightarrow v_i(1,w) ;
    • 对于一块点 i 上的,权为 w 的黄金 v_i\rightarrow T(1,w) ;
    • 对于一条原树上的边 (x,y,c) v_x\rightarrow v_y(+\infty,c) ;

时间复杂度: O(q \mathrm{MincostMaxflow}(N,N))
预计得分: 8

算法四

我们还可以使用反悔型贪心来解决本问题。

记节点 i 到根的距离为 d_i ,那么一组匹配 (a,b) 的收益可以表示为 (w_a-d_a)+(w_b+d_b)

由于我们关心的仅仅是数值而不是 a b 的位置,所以我们可以将 w_b 加上 d_b w_a 减去 d_b 后看做矿工和黄金的固有属性,不妨记为 value_a value_b

每当我们找到可以使当前总代价减小的匹配,即 value_a+value_b \gt 0 ,匹配之。

但这样找到的匹配很可能不是最终答案上的匹配,因此我们需要提供一个反悔的可能。考虑撤销本次匹配的代价,我们可以重新计算得到新的 value_b'=value_b-value_a

这样,我们自底向上使用可并堆维护可行的匹配集合即可。

这里的反悔实际上和网络流模型的反向增广同构。

时间复杂度: O(q^2\log q)
预计得分: 16

算法五

继续沿用算法三,我们需要考虑如何动态加边维护费用流。

众所周知,动态加边的费用流会有正环。所以我们需要使用消圈算法。

不过在本问题中,可以证明,每次增广前,至多只有一个正环需要消掉。

每次操作后,我们可以在原树上 BFS 来以单次 O(n) 的复杂度来寻找增广路或者正环。

但这样讨论量比较大,加老鼠操作引发的消圈以及增广,和加洞操作引发的消圈以及增广,都需要分别处理。具体细节可以见标准程序。

一个简化是在为矿工寻找增广的时候,已匹配的其他矿工和未匹配的黄金是等价的,可以一起处理。这也是赛场上大多数人的做法。

时间复杂度: O(qn)
预计得分: 52

(但很多人写了这个拿了 60 ,可能我数据造水了)

算法六

继续沿用算法四的分析,我们可以发现,一条增广路的权值可以拆成两端点的权值和。

对于特殊性质 1 的测试点,我们仅需维护某个特定的点 u 能到的所有点 v 中,权值最大的那一个。

显然,如果可以求得点 u 能到的深度最浅点 x ,那么所有点 u 能到的点 v ,就是点 x 的子树。

回忆一下我们需要哪些操作:增广的时候我们需要对树链流量进行加减;寻找增广路的时候,我们沿着有流量的边往上爬到一个最高点 w ,然后查询点 w 的子树最值即可。

使用数据结构简单维护即可,标准程序用的是树链剖分和线段树。

如果仅仅实现了线段树部分,可以获得链的部分分。

如果往上爬的时候使用暴力实现,可以获得二叉树的部分分。

时间复杂度: O(q \log n) O(q \log ^2 n)
预计得分: 48
综合算法五预计得分: 76

算法七

现在我们需要处理操作 2 所涉及的增广,我们仅需维护能到达某个特定的点 u 的所有点 v 中,权值最大的那一个。

考虑链分治,我们可以用堆来维护每个点的轻子树中,能到达这个点的最大权值。

寻找增广路的时候需要枚举点 u 和点 v 的 LCA 所在的重链,并使用线段树维护区间最值。

沿着路径增广的时候,需要维护树链前缀最值来更新链顶父亲的堆。

更多细节可以参考标准程序。

时间复杂度: O(q\log n) O(q \log^2 n)
预计得分:视实现常数 96 100 分。

T3. 不等关系

By 300iq,题解 By cz_xuyixuan

算法一

枚举所有排列,并验证是否合法。

时间复杂度: O(n! n)
预计得分: 5

算法二

状态压缩动态规划,记 dp_{S,i} 表示使用 S 中的所有元素,且最后一个元素为 i 的方案数。

时间复杂度: O(2^n n^2)
预计得分: 10

算法三

注意到对于一个前缀,我们实际关心的只是所有元素的相对大小关系。

在算法二的基础上,我们可以不将已经使用的元素集合计入状态,转而记录最后一个元素在已经使用的元素中的排名。即记 dp_{i,j} 表示 1\sim i 的满足前 i-1 个限制的排列中,有多少排列的末位元素排名为 j

转移时只需要枚举下一个元素的排名即可。

时间复杂度: O(n^3) ,可以用部分和优化至 O(n^2)
预计得分: 25 40

算法四

上述做法似乎已经没有什么优化的空间了,想要解决本题,我们必须另辟蹊径。

注意到如果不存在 s_i > 的限制,即 s_i > p_i,p_{i+1} 的大小关系任意,问题就等价于将 1\sim n 填入若干个递增序列的方案数。记各个序列的长度为 a_1,a_2,\dots,a_k ,则方案数应当为

\frac{n!}{\prod_{i=1}^{n}a_i!}

存在 s_i > 的限制的情况可以通过容斥原理计算。

dp_i 表示长度为 i 的前缀的合法排列数除以 i! 的结果, cnt_i 表示 s_1,s_2,\dots, s_i > 的数量,则有转移

dp_0=1\\dp_i=\sum_{j=0}^{i-1}[s_j\ne\mathtt{<}](-1)^{cnt_{i-1}-cnt_j}\times dp_j\times \frac{1}{(i-j)!}\ (i\geq1)

时间复杂度: O(n^2)
预计得分: 40

算法五

上述 DP 转移式是容易优化的卷积形式,可以使用分治 NTT 优化其时间复杂度。

时间复杂度: O(n\log^2 n)
预计得分: 100

Day 2

T1. 签到游戏

By Snakes & bzh,题解 By Snakes

文中我们默认 [x,y] 表示 l=x,r=y 的操作, (u,v) 表示一条 u v 之间的边。

算法一

S_n=\sum_{i=1}^n A_i ,特别地, S_0=0

那么 \{A_i\} \{S_i\} 一一对应,知道 \{A_i\} 等价于知道 \{S_i\}

询问 [l,r] 时得到的信息实际上是 S_r - S_{l-1} 。构造一个 n+1 个结点的图 G ,结点编号为 0 n ,分别表示 S_0, S_1, \dots , S_n 。询问 [l,r] 对应边 (l-1,r) ,边权为 \gcd_{i=l}^r B_i 。确定 S_i 的充要条件为 S_0(=0) S_i 通过询问的边连通,于是确定所有即等价于图 G 被询问连通。因此最优操作方案即为图 G 中的最小生成树。

n,q\leq 200 时,直接用 Prim,Kruskal 等算法求最小生成树即可。

时间复杂度: O(q n^2\log n )
预计得分: 12

算法二

我们有以下结论:

引理一 存在一个最优方案,使得每次操作 [l,r] 满足 l=1 r=n

证明 对于任意 G 中的生成树,我们均有方法在边权和不增的前提下,将其调整至每条边 (u,v) 满足 u=0 v=n 。具体地,我们令 0 为根,将每条边有向化,由子结点指向父节点。此时,对于任意一条边 u\rightarrow v ,若 u<v ,则调整为 u\rightarrow n ,否则调整为 u\rightarrow 0 。由于 n 的父结点必然小于 n ,故而调整后 n 的父节点为 0 n 0 联通,其它结点的父亲为 0 n ,因此调整后所有结点联通。由于 \gcd 随着元素增多而不增,调整后每条边对应操作区间均包含原边对应操作区间,故而边权和不增,证毕。

因此,我们可以将算法一中图 G 的边数减少到 O(n) 级别,求其最小生成树。

时间复杂度: O(q n\log n)
预计得分: 32

算法三

我们有一个更强的性质:

引理二 存在一个最优方案满足:存在 p 使得操作方案由以下三类操作构成:

  • [1,i]\,(p\leq i<n)
  • [j,n]\,(1<j\leq p)
  • [1,n]

证明 由引理一可知,图 G O(n) 条边的最小生成树即为答案,且必然存在一个最优操作方案包含 (0,n) 。容易发现,图 G 中每个环均是 (0,i),(i,n),(0,n) 的形式,且 (0,n) 必选,因此我们只需要选择 (0,i),(i,n) 中边权较小者即可,构成的生成树即为最优答案。对应回序列,由于前缀 \gcd 由前往后单调递减,后缀 \gcd 由前往后单调递增,因此存在转折点 p 使得,对于 1\leq j\leq p 由操作 [j,n] ,对于 p\leq i\leq n 有操作 [1,i]

由于不同的前缀 \gcd 只有 \log B_i 种,因此可以每次二分下一个前缀 \gcd 改变的位置,线段树维护区间 \gcd ,二分时在线段树上查询。对于后缀同理。

对于得到的前缀序列与后缀序列,由于其长度为 O(\log n) ,我们在其上暴力找出转折点 p 更新答案即可。

修改只需要在线段树上维护区间 \gcd 即可。

由于 B_i 随机,因此前缀序列与后缀序列的长度期望远小于 O(\log n) ,通过前三个子任务的程序应当可以通过第四个子任务。

时间复杂度: O(q\log^3 n)
预计得分: 65

算法四

对于第四个子任务,我们可以发现当 n 很小时答案波动较大,但当 n 很大时答案为 n 的概率较高,因此结合算法一或暴力可以通过第四个子任务。

时间复杂度: O(q)
预计得分: 10

算法五

在算法三的基础上,将二分下一个前缀 \gcd 改变的位置并在线段树上查询,改为在线段树上二分即可减少一个 \log 。(先序遍历线段树,查找对应区间内所有的 \gcd 改变位置,在区间内不存在改变位置时剪枝即可)

需要注意的是,在线段树上二分判断时应使用取模判断区间 \gcd 是否为上一个前缀 \gcd 的倍数,而非直接 O(\log B_i) \gcd

时间复杂度: O(q\log^2 n)
预计得分: 100

T2. 简单算术

By zx2003,题解 By zx2003

算法一

暴力预处理出该多项式的 m 次幂,每次询问直接输出答案。

时间复杂度: O(m^2n+T)
预计得分: 10

算法二

对于 n=1 p=2 的情况,利用二项式定理和卢卡斯定理可以 O(1) 回答询问。

时间复杂度: O(T)
预计得分: 5

算法三

我们暴力展开该多项式的 m 次幂。

i 次项在最后的结果中出现了 b_i 次。

那么有等式 \sum_{i=0}^{n} i b_i = k

并且一组 b_i 的贡献是 (\binom{m}{b_1}+\binom{m-b_1}{b_2}+\binom{m-b_1-b_2}{b_3}+...) \prod_{i=0}^{n}b_i^{a_i}

注意由卢卡斯定理,上式若不为 0 ,则 b_0+b_2+...+b_n p 进制下每一位均不发生进位,且每一位均对应小于 m 的位。

我们可以从低位到高位对前述式子进行数位 DP,记 g_{i,j} 表示做了前 i 位,并且对第 i+1 位的进位是 j

注意我们可能需要预处理一个数组 f 来计算转移时的系数。

其中 f _ {x,y} 表示做了前 x b_i (这里为了方便需保证 b_i<p ),并且 \sum_{x=0}^{n} i * b_i=y 的系数和,可以简单地预处理。

时间复杂度: O(n^2 p^3 + T n^2 \log_{p}{m})
预计得分: 100

算法四

考虑另外一种思路。

F(m,k) 表示询问 m,k 的答案。

可以证明如果 m p 的倍数,那么 F(m,k) = F(m/p,k/p) (若k/p不是整数则为0)。

根据这个性质, F(m,k) 可以有 F(m-1,k-n),...,F(m-1,k) (如果 m 不是 p 的倍数)或 F(m/p,k/p) 得到。

直接暴力递归并记忆化可以获得玄学分数。

考虑比暴力递归更优的一些做法。

我们可以预处理出原多项式的 0 p 次幂

并且递归的时候我们需要同时维护 F(m-1,k-n),...,F(m-1,k)

每次递归的时候可以以一次多项式乘法的复杂度由 F(m,k) 递归到 F(\lfloor \frac{m}{p}\rfloor,\lfloor \frac{k}{p} \rfloor)

时间复杂度: O(n^2 p^2 + T n^2 \log_{p} {m})
预计得分: 100

T3. 小球进洞

By yww & CommonAnts,题解 By CommonAnts

算法一

直接模拟题意。可以用链表维护可用 b 来加速。

时间复杂度: O(qn) O(qn^2)
预计得分: 10

算法二

注意到, \le n 的已被占用的 b_i 一定是连续的一段,可以同时处理。

相同的 a_i 也可以同时处理。

于是按 a_i 从小到大模拟,每次处理所有相同 a_i 即可。每次询问需要处理 50 a_i ,每次大于 n 的单独处理的 b_i 最多 50 个。

时间复杂度: O(q(\max a_i - n))
预计得分: 20

算法三

没有修改可以用链表维护,线性时间算出所有 [b_i,a_i] ,然后用区间数据结构维护。

时间复杂度: O(n+q \log n)
预计得分: 20 ,结合上述可得 40

算法四

可以注意到如果 a_i 的绝对值改变 1 ,最终只会有至多 2 [b_i,a_i] 发生变化。

证明:如果 a_i\gets a_i+1 ,不妨当作原来 b_i 最小的那个 a_i 被修改了(因为我们只关注 \{a_i\} 的无序集合),那么 \le a_i 的小球都不变; > a_i 的小球只有第一个 b \le a_i+1 的对应 b 会变化为 a_i 。(以上 a_i 均指修改前的);
类似地, a_i\gets a_i -1 也只会改变一个其它小球对应的区间。

于是用数据结构维护 [b_i,a_i] 的集合即可。

时间复杂度: O((n+q)\log n) O((n+q)\log^2 n)
预计得分: 70

算法五

性质 1 不同的 [b_i,a_i] 要么互不相交,要么互相包含。

证:如果 b_1<b_2<a_1<a_2