LibreOJ NOIP Round #1 题解

liu_cheng_ao 2017-11-05 12:28:06 2017-11-26 21:29:47

Day 1

T1. DNA 序列

By HeRaNO,题解 By HeRaNO

  • 考察选手的基础算法知识和字符串处理。
  • 模拟、枚举或二进制散列
  • 思维难度:提高-
  • 实现难度:提高-

算法一

注意到一些特殊数据可以特判:

第 1,4 组数据满足 DNA 序列中所有碱基都相同,所以只有 1 种连续的 k 个碱基,手算答案即为 n-k+1 ,期望得分为 20 分;
第 2,3 组数据满足 k=1 ,即需要统计 A,G,C,T 四种碱基出现最多的次数,直接统计每个碱基出现次数,答案为其最大值,期望得分 20 分。

综合起来可获得 40 分。

时间复杂度: O(n)

空间复杂度: O(n)

预计得分: 40

参考程序

算法二

统计每种连续 k 个碱基的出现次数,这是个经典问题,有很多统计方法,例如:

  • 用 map 来维护。这个可能会超时。参考程序
  • 随便找个字符串散列算法。这个可能会碰撞然后答案错误。比如双模数的高进制数取模(推荐采用孪生素数作为两个模数)。参考程序
  • 用字典树维护。这个可能会超时或者超内存(如果你的实现很差)。参考程序
  • 建后缀树、后缀数组或者后缀自动机,然后按序遍历长为 k 的子串。

时间复杂度: O(n)\sim O(nk)

空间复杂度: O(n)\sim O(\min(nk,4^k))

预计得分: 80\sim 100

算法三

什么 map 啊字典树啊后缀数据结构我都不会!有没有符合 NOIP T1 的做法啊?当然有啊。

发现 k 很小,并且每一位状态只有 4 种,所以本质不同的串最多有 4^k 个,于是我们可以用 4 进制数表示。注意到 4^{10}=2^{20} ,因此可以直接将这些状态出现的次数存起来。

这里计算一个串的 Hash 值有两种方法,第一种是每个串都重新计算一遍,时间复杂度为 O(nk) 参考程序),第二种是利用位运算将无用状态取出,并加入新状态,时间复杂度为 O(n) 参考程序)。这两个复杂度的代码均可通过。

时间复杂度: O(n+4^k)\sim O(nk+4^k)

空间复杂度: O(n+4^k)

预计得分: 100

T2. 递推数列

By sosusosu,题解 By CommonAnts

  • 考察选手的递推数列基本知识,分析规律的能力以及复杂度分析知识。
  • 枚举或二分
  • 思维难度:提高
  • 实现难度:提高

算法一

s_m\le 10 ,我们可以每次暴力算出 a_0\sim a_{10} ,比较后取最值即可。

时间复杂度: O(n s_m)

空间复杂度: O(m)

预计得分: 15

算法二

a_0\cdot a_1\ge 0 时,序列每项同号。

可以发现,若有连续两个 a_i 同号且不全为 0 则从下一项起必定严格单调。

那么对于不小于 2 s_i ,利用单调性只需判断其中最大和最小的。而且我们可以得到 |a_4|>|a_0| ,故只需暴力处理 s_i=0,1,2,3 的情况,后面利用单调性讨论即可。

另外要注意特判 a_0=a_1=0 的情况。

时间复杂度: O(m+n)

空间复杂度: O(m)

预计得分: 5 ,结合前述可得 20

算法三

|a_1|\ge |a_0| 时,由于 k\ge 1 a_2 必定和 a_1 同号。于是转为算法二解决。

时间复杂度: O(m+n)

空间复杂度: O(m)

预计得分: 5 ,结合前述可得 25

算法四

以下我们默认 a_0 a_1 不同时为 0。

考虑扩展算法二。我们观察几个数列的性质,可以发现:序列到了某个位置就会开始单调。

于是,我们可以预处理前若干项直到序列严格单调(就是相邻两项同号且严格单调),且绝对值严格大于之前的项。然后暴力讨论前面这些项,后面用单调性判断即可。

然后就获得了满分!但此时我们还不会证明复杂度。

时间复杂度: O(?) (见后文)

空间复杂度: O(m)

预计得分: 100

算法五

我不知道算法四能满分,还是想想部分分吧。

因为连续两项同号或者一项的绝对值大于前一项都会导致序列开始单调,故我们可以把序列分成两部分:设 M 是最小的使得序列下标在 [0,M) 的部分满足相邻项乘积为负且绝对值严格单调递减,在 [M,+\infty) 的部分满足相邻项乘积非负。除非 a_0=a_1=0 [M+3,\infty) 这部分一定不含有 0 且严格单调。

由于 [0,M) 这部分相邻项符号不同且绝对值单调递减, [M,+\infty) 这部分符号都相同,再对 [M,M+3) 这一段的单调性讨论后,综合可得:序列 a 的奇数项和偶数项一个单调另一个单峰

对于 s_i 全为偶数的情况,我们可以判出偶数位置成的是单调函数还是单峰函数,然后判断即可。判断要么用处理前若干项……要么……数列学的好可以特征根……(细节很麻烦)

时间复杂度: O(m+n)

空间复杂度: O(m)

预计得分: 25 ,结合前述(不包括算法四)可得 50

算法四(证明)

现在证明算法四的复杂度。

b_i=|a_i| ,由正负交错有 \forall i\in[2,M), b_i=-k b_{i-1}+b_{i-2} ,移项得 b_{i-2}=k b_{i-1}+b_i

那么 b_{i-2}=k b_{i-1}+b_i\ge (k+1)b_i ,可得 M\le 2\log_{k+1} a_0

那么变成单调的项数是 O(\log a) 。与之类似,我们也可证明变成单调之后绝对值超过前面项之前的项数也是 O(\log a)

于是我们证明了算法四的时间复杂度为 O(n\log a)

不会爆 64 位整数吧?当然不会,因为 [0,M-1) 中的元素绝对值必定单调递减,后面那部分绝对值超过 \max{|a_0|,|a_1|} 之后至多再增长一次。于是计算中用到的最大的绝对值不会超过 ak^2 ,不会爆。

算法六

我觉得 \log a 做法不够优秀!一秒 3\times 10^5 是卡常数卡常数卡常数!有没有更快的做法?有。

算法四的瓶颈在于计算 \log a 项。我们可以利用算法五的方法把原序列分成三个单调序列分别讨论。我们预处理每种 k \log_{k+1} a 项的转移系数,强行二分找出 M ,然后分类讨论即可。按照算法五实现,这个过程中最大涉及的绝对值为 ak^3 ,不会爆 64 位整数。

实现起来细节十分麻烦,参考程序。(所以还是 \log a 暴力好啊)

时间复杂度: O(m+\frac{k\log \max(a,k)}{\log k}+n\log\log a)

空间复杂度: O(\frac{k\log \max(a,k)}{\log k}+m)

预计得分: 100

扩展

其实这题为了符合 NOIP 是弱化过的,原来是这样的:递推式是 a_{i+2}=k_1 a_{i+1}+k_2 a_{i} ,保证 1\le k_2\le k_1 。这时我们的证明得到的复杂度降到了 O(n k \log_a) ,但其实单调前的项数还是 O(\log a) 的。

以下证明超过 NOIP,属于扩展内容,与本场比赛难度无关:

\Delta=k_1^2+4 k_2,\delta=\sqrt{\Delta} 正负特征根分别为 \beta=\frac{1}{2}(k_1+\delta),\alpha=\frac{1}{2}(k_1-\delta)

k_1<\delta<k_1+2 可得 -1<\alpha<0<1\le k_1<\beta<k_1+1 。另外,由于 \Delta (k_1+1)^2 奇偶性不同,可得 \Delta 不是完全平方数,故 \delta,\alpha,\beta 都是无理数。

考虑通项公式 a_n=(a_0-\frac{a_1-\alpha a_0}{\beta-\alpha})\alpha^n+\frac{a_1-\alpha a_0}{\beta-\alpha}\beta^n ,有两项,并且后一项单调且绝对值单调递增,前一项振荡且绝对值单调递减。故存在 M 使得 \forall n\ge M,|\frac{a_1-\alpha a_0}{\beta-\alpha}\beta^n|\ge|(a_0-\frac{a_1-\alpha a_0}{\beta-\alpha})\alpha^n| ,之后序列单调(因为符号总是和绝对值较大的一项相同)。

M-1\le \log_{|\frac{\beta}{\alpha}|}|\frac{a_0(\beta-\alpha)-(a_1-\alpha a_0)}{a_1-\alpha a_0}|\le \log_{|\frac{\beta}{\alpha}|}(|\frac{a_0(\beta-\alpha)}{a_1-\alpha a_0}|+1)=U

又因为:

  • |a_0(\beta-\alpha)|=|a_0|\delta
  • \begin{align} |a_1-\alpha a_0| & =|a_1-\frac{1}{2}(k_1-\delta)a_0|\\ & = \frac{1}{2}|2 a_1-a_0 k_1+\sqrt{a_0^2 \Delta}|\\ & \ge \frac{1}{2}|\sqrt{a_0^2 \Delta+4}-\sqrt{a_0^2 \Delta}|\\ \end{align}
    (这里是 4 是因为 (2 a_1-a_0 k_1)^2-a_0^2 \Delta 4 的整数倍)

故:

|\frac{a_0(\beta-\alpha)}{a_1-\alpha a_0}| \le 2|a_0|(\sqrt{a_0^2+4\Delta^{-1}}-|a_0|)^{-1}

则:

U \le\log_{1+\frac{2 k_1}{\delta-k_1}}2|a_0|(\sqrt{a_0^2+4\Delta^{-1}}-|a_0|)^{-1}+1

k_1 一定时随 \delta 单调递增。故取得最大值时必有 k_1=k_2 。设 k_1=k_2=k ,则。

\begin{align} U & \le\log_{1+\frac{2 k}{\delta-k}}2|a_0|(\sqrt{a_0^2+4\Delta^{-1}}-|a_0|)^{-1}+1 \end{align}

通过某些方式(Wolfram Alpha)算出这个函数在正整数内关于 k 单调递减, |a_0| 单调递增 …… 于是此上界 k_1=k_2=1,|a_0|=10^7 时取得最大值,约为 35.19 。本题数据范围内实际最大的解为斐波那契数的相邻两项 a_0=9227465,a_1=-5702887,k_1=k_2=1 ,其中 M-1=35,M=36

T3. 旅游路线

By spj,题解 By spj

算法一

暴搜,每次枚举下一步到达的景点以及是否加油,视实现优劣,期望得分 30 50 分。

算法二

我们可以把暴搜的过程记忆化,以设计DP。

f(i,c,s) 表示当前位于景点 i ,汽车油量为 c ,目标总路程为 s 时,到结束时花费的钱的最小值。

显然当 s\le 0 f(i,c,s)=0 。当 s>0 时,枚举下一步的决策,有

f(i,c,s)=\min\begin{cases}f(b_j,c-1,s-l_j),&a_j=i,&\mathrm{if\ }c>0,\\f(i,\min\{c_i,C\},s)+p_i,&&\mathrm{if\ }c < c_i\end{cases}

时间复杂度 O(mC\max\{d_i\}) ,期望得分 35 分。

算法三

我们发现钱的范围 q_i\le n^2 ,而路程的范围 d_i 很大,考虑改变DP的状态设计。

f(i,c,q) 表示当前位于景点 i ,汽车油量为 c ,剩余钱数为 q 时,之后的最大路程。

类似地,可以得到

f(i,c,q)=\max\begin{cases}f(b_j,c-1,q)+l_j,&a_j=i,&\mathrm{if\ }c>0\\f(i,\min\{c_i,C\},q-p_i),&&\mathrm{if\ }c<c_i\land q\ge p_i\end{cases}

在无法转移时 f(i,c,q)=0

询问时,只需枚举最小的 q\le q_i 使得 f(s_i,0,q)\ge d_i 即可。

时间复杂度 O(mC\max\{q_i\}+Tq_i) ,期望得分 60 分。

算法四

上述DP的瓶颈在于状态数,考虑优化状态。注意到每次加油以后,油量的状态和之前无关,所以考虑以每次加油的位置为状态进行DP。

f(i,q) 表示当前位于景点 i ,下次在 i 位置加油,剩余钱数为 q 时,之后的最大路程。

q<p_i 时, f(i,q)=0 ,否则,转移时枚举第二次加油的位置 j ,得到

f(i,q)=\max\{f(j,q-p_i)+w(i,j,\min\{c_i,C\})\}

其中 w(i,j,c) 为从 i j 经过不超过 c 条道路的最大路程。这可以用DP预处理,枚举 i 出发的第一条路 e ,得

w(i,j,c)=\max_{a_e=i}\{w(b_e,j,c-1)+l_e\}

边界是 w(i,i,0)=0 w(i,j,0)=-\infty i\ne j )。

询问时,只需枚举最小的 q\le q_i 使得 f(s_i,q)\ge d_i 即可。

时间复杂度 O(n^2\max\{q_i\}+nmC+Tq_i)=O(n^4+nmC+Tn^2) ,期望得分 75 分。

算法五

现在的瓶颈在于预处理 w(i,j,c) ,我们发现每次 c 只会减少 1 ,于是可以用倍增预处理。

g(i,j,k) 为从 i j 经过不超过 2^k 条道路的最大路程,则当 k>0 时:

g(i,j,k)=\max_x\{g(i,x,k-1)+g(x,j,k-1)\}

注意到我们只要对所有 i,j 处理出 w(i,j,\min\{c_i,C\}) ,令 c=\min\{c_i,C\} ,那么每次提取 c 的一个二进制位 2^k ,可得

w(i,j,c)=\max_x\{w(i,x,c-2^k)+g(x,j,k)\}

只需倍增 O(\log C) 轮即可。

时间复杂度 O(n^2\max\{q_i\}+n^3\log C+Tq_i)=O(n^4+n^3\log C+Tn^2) ,期望得分 95 分。

算法六

只要把上述算法中,询问时枚举最小的 q 使得 f(s_i,q)\ge d_i 这一步的枚举换成二分,就能把最后一步的 O(Tq_i) 优化到 O(T\log q_i)

时间复杂度 O(n^2\max\{q_i\}+n^3\log C+T\log q_i)=O(n^4+n^3\log C+T\log n) ,期望得分 100 分。

Day 2

T1. 游戏

By qmqmqm ,题解 By CommonAnts

  • 考察选手图论基本知识和简单的构造。
  • 完全图贪心或完全三部图+调整法或随机背包等
  • 思维难度:提高
  • 实现难度:提高-

以下时空复杂度若未标明,均为 O(x^2) ,不再赘述。

\sim 记号表示 x\rightarrow +\infty 时的等价无穷大,即二者都无穷增长且比值的极限为 1

算法一

从小到大暴力枚举所有无向图。

x\sim (6n)^{1/3}

时间复杂度: O(\omega(\mathrm{poly}(x)))

预计得分: 5\sim 15

算法二

直接用 3n 个点拼成 n 个互相独立的三元环即可。

x\sim 3n

预计得分: 25

算法三

考虑三角网格图。我们可以拼成长条,平面或空间四面体网格等。此做法可以扩展至高维并解决此题,但由于较复杂不在此详叙。

x\sim 2n (长条)或 x\sim n (平面三角网格)或 x\sim n/3 (空间四面体网格)

预计得分: 30\sim 45

算法四

随机一堆接近完全图的图然后求三元环个数并背包。

x\sim ?

时间复杂度: O(?)

预计得分: 0\sim 100

算法五

两个特殊数据: n 是正整数的立方可以用完全三部图构造,存在完全图满足条件则可以枚举 x 并计算 \binom{x}{3} 验证。

x\sim 3 n^{1/3} x\sim (6n)^{1/3}

预计得分: 10

算法六

我们可以每次贪心取一个三元环个数最接近 n 的不超过 n 的完全图。 n\le 2\times 10^6 时此种方法构造出的 x\le 331

x\sim kn^{1/3} k 是某个介于 6^{1/3} 3 之间的常数)

预计得分: 100

算法七

三部图的思路:先构造一个 3\lfloor n^{1/3} \rfloor 个点的完全三部图,然后加点并和原来的点连边。

x\sim 3n^{1/3}

预计得分: 100

T2. 七曜圣贤

By WerKeyTom_FTD ,题解 By WerKeyTom_FTD

  • 考察选手对题目所要求维护信息的分析能力及基于单调性的数据结构的应用能力。
  • 一道定位上略像但简单于NOIP2016 D2T2 蚯蚓的题目
  • 思维难度:提高
  • 实现难度:提高

算法一

记一个数组来表示每种编号的红茶的情况( 1 、初始不在卡车上也从没通过第一种事件买过。 2 、现在在卡车上的。 3 、飞出去的。)。

然后按题意模拟即可,每次询问按题意所说枚举找到最小的未出现编号的红茶。

时间复杂度: O(m^2)

空间复杂度: O(m)

预计得分: 30

算法二

观察题意,我们可以认为这是一个集合,支持插入、删除、求mex(你可以把捡回来也看做是一种插入)。

可以开一颗权值线段树,每个节点存一个布尔变量表示这个区间的编号是否全都在卡车上。

查询时可以二分答案并用线段树查询。

时间复杂度: O(m\log^2\ m)

空间复杂度: O(m)

预计得分: 40

实际上可以利用线段树性质在线段树上二分,也可以直接在线段树叶子节点上存编号表示未出现,否则存inf表示出现,那么每次相当于求最小值,直接利用根节点信息即可。

时间复杂度: O(m\log\ m)

空间复杂度: O(m)

预计得分: 60

算法三

考虑 d=1 怎么做,相当于一个集合,只有加入和求mex。

不妨同样维护一个桶表示每个编号是否出现。发现答案是单调不降的,可以维护一个指针,每次加入后尝试更改这个指针即可。

答案不会超过 a b 的较大值,因此指针的移动是线性的。

时间复杂度: O(m)

空间复杂度: O(m)

预计得分: 10

结合前面的算法可以获得 40 70 分不等。

算法四

不妨考虑如何在算法三的基础上维护出删除、恢复两种操作。

我们同样维护出只考虑加入操作的答案 x ,然后记被删除的元素的最小值为 y ,容易发现mex为 min(x,y)

因此我们可以写一个复杂度与被删除元素个数有关的支持插入、删除、查询最值的数据结构如堆、平衡树。

时间复杂度: O(m\log\ m)

空间复杂度: O(m)

预计得分: 70\sim 80

算法五

我们可以对于每个编号处理出它的若干段不存在时间。

现在我们从小到大枚举编号,然后去覆盖对应时间区间还未被覆盖的位置(显然这个编号就是这些时间的答案)。

可以使用并查集来精确且快速的找到一个区间所有未被覆盖的位置(可以令每个位置getfather后得到从其开始往右第一个未被覆盖的位置,当覆盖一个位置 i 后将其父亲指针连向 i+1 )。

时间复杂度: O(m\alpha(m))

空间复杂度: O(m)

预计得分: 70\sim 80

算法六

在算法四的基础上,我们现在主要需要优化找到被删除的最小元素这部分的复杂度,加入部分基于算法三是线性的。

之前描述的模型并没有用到本题的重要性质,即被恢复的是删除最早的,因此要获得满分,并不能简单的把恢复看成一种插入。

如果一个元素的删除时间比另一个元素的删除时间早,但是这个元素更大,显然它是冗余的,即它不可能成为最小值。

显然这里已经能看出是单调队列的模型了,按删除时间递增,队列内元素递增,来维护一个单调队列即可。

时间复杂度: O(m)

空间复杂度: O(m)

预计得分: 100

T3. 序列划分

By cyand1317 & CommonAnts,题解 By CommonAnts

  • 考察选手的思维、数学建模能力和贪心等算法的应用。
  • 分类讨论或枚举后贪心
  • 思维难度:NOI
  • 实现难度:提高

注意,本题解内介绍了两种思路,如果你想看简单的解法,请跳过算法五至十。

为了方便,首先将序列内 k 的倍数设为 0,其余的数设为 1。

首先我们可以发现如果有解, n 必定是 k 的倍数,且 n\ge k^2 ,且 a_1=a_n=0 。以下算法均在判断这几个条件之后应用,不再特别说明。

为了方便,我们约定以下记号:

  • 序列的下标同时也指该位置的元素。
  • 用大写字母表示子序列。
  • 设含 a_1 的子序列为 P ,含 a_n 的子序列为 S ,含 a_i 的子序列为 Q(i)
  • l(Q) r(Q) 分别表示子序列 Q 的左右端点。
  • 设状态函数 e(i) 表示点 i 是否是某个子序列的端点,若是左端点则 e(i)=1 ,右端点则 e(i)=2 ,否则 e(i)=0 。另外,规定集合 T_k=\{i|e(i)=k\} ,即 T_1\cup T_2 表示子序列的端点集合, T_0 表示非端点的集合。

证明过程中主要应用调整法,为了简便省略了证明调整法必定在有限步内结束的过程。

算法一

n k 都很小,暴搜,手玩,打表皆宜。

时间复杂度: \mathrm{N/A}

空间复杂度: \mathrm{N/A}

预计得分: 5

算法二

n k 较小,暴力枚举划分方案即可。实现可能比较复杂。

时间复杂度: \omega(\mathrm{poly}(n))

空间复杂度: \mathrm{N/A}

预计得分: 15

算法三

k=2 时只要满足 0 不小于 4 个即有解。方案是:找出任意两个除 a_1,a_n 外的 0 组成一个子序列,其余元素组成一个子序列。

时间复杂度: O(n)

空间复杂度: O(n)

预计得分: 15 ,结合前述可得 25

算法四

n\le 100,k\le 3 时,考虑 DP。

f(i,c_0,c_1,\cdots ,c_{k-1}) 表示考虑前 i 个,当前长度模 k 0,1,\cdots ,k-1 的个数分别为 c_0,c_1,\cdots ,c_{k-1} 时是否存在方案及任意一个上一步决策。进行 DP 即可。在 k=3 时要优化内存使用。

这部分也可以暴力讨论 k=3 的情况。首先可以发现几个明显的性质:

引理 0 若存在合法方案,一定存在恰好分成 k 个子序列的方案。
证:两个合法子序列的并显然合法。故若不考虑子序列个数的合法性,将分成 i 个的方案中任意两个子序列合并即可得到分成 i-1 个的方案。归纳可得分成任意小于 i 个的方案。又由于 k 是最小的 k 的正整数倍,若存在方案一定可以分成 k 个。

引理 1 若存在符合以上引理的方案,一定存在方案使得 T_0 中点都在 T_1 中的左侧。
证:否则交换两点即可。

引理 2 若存在符合以上引理的方案,一定存在方案使得 T_1 是前 k