LibreOJ β Round #3 题解

liu_cheng_ao 2017-08-04 22:07:42 2017-11-06 9:05:21

T1.绯色 IOI(开端)spj

题解由 spj 提供。

算法一

暴力枚举所有回路,即枚举点集 V 的一个环排列,计算回路的长度更新答案。

直接枚举 V 的排列得到回路 C O(n) 计算回路长度,时间复杂度 O(n!\cdot n)

如果用回溯法在枚举排列的同时计算路径长度,或者注意到总可以只考虑以 1 为起点和终点的回路(即固定排列的首项为 1 ),时间复杂度为 O(n!)

如果同时加入这两个优化,时间复杂度为 O((n-1)!)

这三种复杂度均可通过子任务1,期望得分10分。

算法二

枚举排列太暴力了,考虑用状压DP。

f(S,i) 为从点 i 出发且经过 S 中每个结点恰好一次最后到点 1 的路径长度最小值,其中 i\in S 。当 i\not\in S 时, f(S,i)=+\infty

S=\{i\} 时, f(S,i)=(w_i-w_1)^2

否则, f(S,i)=\min_j\{f(S-\{i\},j)+(w_i-w_j)^2|j\in V\}

答案为 f(V,1) 。时间复杂度 O(2^nn^2) ,空间复杂度 O(2^nn) ,可以通过子任务1,2,3,期望得分30分。

如果你的程序常数太大,可能只能通过子任务1,2 得到20分。

算法三

旅行商问题是 NP-Hard 的,上述算法没有什么优化余地了,我们需要分析图的性质。

首先我们将点权排序。接下来不妨设 w_1\le w_2\le\cdots\le w_{n-1}\le w_n ,则有以下性质:

性质1 存在最优解 C ,使得 C 中从点 1 到点 n 的部分经过的点编号递增,从点 n 到点 1 的部分经过的点编号递减。

证明 不妨设最优解 C 中从点 1 到点 n 的部分经过的点集为 A=\{v_1,v_2,\cdots,v_l\} ,其中 v_1=1 v_l=n v_1<v_2<\cdots<v_l

考虑 1\rightarrow n 只经过 A 中的点的最短路 P 。对任意 i=2,3,\cdots,v_l ,考虑 P 中任意一条满足 p<i,q\ge i 的边 (v_p,v_q) ,假设 q>i ,记 a=w_{v_i}-w_{v_p} b=w_{v_q}-w_{v_i} ,将这条边拆成 (v_p,v_i),(v_i,v_q) 两边,由于 (a+b)^2\ge a^2+b^2 ,长度不会增加。因此总可以令 q=i 。同理,总可以令 p=i-1

于是 v_1\rightarrow v_2\rightarrow\cdots\rightarrow v_l 是一条最短路,性质得证。 n\rightarrow 1 部分同理。

根据性质1,回路 C 实际上由两条 1 n 的递增路径构成,要求除 1 n 外的每个点恰好属于一条路径。

这样,可以设计多线程DP解决这个问题; f(i,j) 表示确定点 1,2,\cdots,j 所属的路径,两条路径已确定的编号最大的点分别是 i,j ,确定剩下部分的最小路径长度,其中 i<j 。转移如下:

j=n ,则 f(i,j)=(w_i-w_j)^2

否则, f(i,j)=\min\{f(i,j+1)+(w_j-w_{j+1})^2,f(j,j+1)+(w_i-w_{j+1})^2\}

答案为 f(1,2)+(w_1-w_2)^2 。时间复杂度 O(n^2) ,空间复杂度 O(n^2) (可以用滚动数组优化到 O(n) ),可以通过子任务1,2,3,4,5,期望得分70分。

如果设计的DP复杂度多了一个 n ,或者没有注意到答案可能超过32位整数范围,则只能通过子任务1,2,3,4得到50分。

算法四

仍假定 w_1\le w_2\le\cdots\le w_{n-1}\le w_n 。不妨设最优解中两条 1\rightarrow n 的路径为 A B 。事实上,这个问题有更强的性质:

性质2 存在最优解,对任意 i=2,3,\cdots,n-2 ,点 i i+1 既不同时属于 A 也不同时属于 B

证明 假设 i,i+1 均属于 A ,其中 2\le i\le n-2 。设 (p,q) B 中任一满足 p<i,q>i+1 的边。删去边 (i,i+1),(p,q) 并加入边 (i,q),(p,i+1) ,设 a=w_i-w_p b=w_{i+1}-w_p c=w_q-w_p ,由于

b^2+(c-a)^2=a^2+b^2+c^2-2ac\le a^2+b^2+c^2-2ab=(b-a)^2+c^2

长度不会增加。 B 同理。于是性质得证。

这样我们就能直接构造出最优解了:连边 (1,2),(n-1,n) 以及所有边 (i,i+2) i=1,2,\cdots,n-2 ),构成的回路 C 即为最优解,直接计算其长度即可。

时间复杂度 O(n\log n) ,空间复杂度 O(n) ,期望得分100分。

看不出性质怎么办

我们可以打表找规律!

随机生成大量 n 较小的数据,然后用算法一或算法二求最优回路并输出方案。

然后,你就会发现最优回路十分有规律,就能AC啦!

T2.绯色 IOI(抵达)mathematician

题解由 mathematicianCommonAnts 提供。

前面很啰嗦,如果想看标准算法,请跳到算法四。

算法一

直接按照题意模拟即可。枚举每个排列,求出每个城市的庇护所,并加以判断。

时间复杂度 O(n!n) ,期望得分 15 分。

算法二

为了得到多项式算法,我们需要得到一些性质。

i 的庇护所为 p_i

性质1 p_i 中所有环长为 2
(即 i p_i 构成完美匹配)

证明1 考虑从每个城市 i p_i 连边。那么由于 p 是排列,这必定形成若干个环。
由于庇护所的定义,这些环上相邻的点在原图中一定也相邻。又由于原图是树,环长都不超过 2 ,又由定义 i\neq p_i ,这只能是若干个匹配。

证明2 考虑任意一个叶结点 u ,设与 u 相邻的点为 v ,则 p_u=v 。又由于 p 是排列,必有 p_v=u 。删除 u v 并继续进行这个过程可以证明。

另外,任意一颗树的完美匹配是唯一的。

考虑到 n 较小,我们可以使用网络流或匈牙利算法求出完美匹配。

随后,转换为拓扑排序问题。对于每个城市,由于庇护所危险程度最小的性质,将它的庇护所向与它连边的非庇护所的城市连一条有向边。使用拓扑排序可以通过这一部分数据。

时间复杂度 O(n^2) O(n^3) 不等,期望得分 35 分。

算法三

性质太神,推不出来怎么办。干脆打个表吧!对于该图退化为链的情况,我们打表发现:

  • n 为奇数时,这样的情况不存在。
  • n 为偶数时,这东西长这样:前面一部分为连续上升的奇数,后面一部分为连续下降的偶数。

时间复杂度 O(n) ,期望得分 10 分,结合算法二可得 55 分。

算法四

借助树的特殊性,我们可以使用树形动态规划等算法在线性时间内求出它的完美匹配。

然后用优先队列维护拓扑排序(注意拓扑排序的图的基图是两棵树)。

时间复杂度 O(n\log n) ,期望得分 100 分。

T3.绯色 IOI(危机)CommonAnts

题解由 CommonAnts 提供。

这是一道有理有据的暴力题。

算法一

哇这性质好复杂根本看不懂!写个暴搜爽一爽吧。

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

期望得分: 0\sim 10 分。

算法二

性质一告诉我这是个 DAG,求和式表明答案只和相邻两项有关,于是可以愉快地 DP 咯。
f(i) 表示以 i 结尾的最大安全程度,于是有 f(i)=\mathop{\max}\limits _{j~~能~~直~~接~~或~~间~~接~~引~~爆~~i}f(j)+F(v_j,v_i)

啊为什么我 WrongAnswer 爆零了?
注意直接或间接,间接也是要算的,于是可以先建出能否到达的图,然后求传递闭包。用 floyd 是 O(N^3) 的。

时间复杂度: O(N^3)

期望得分: 20 分。

算法三

这是 DAG!我会压位!
使用 O(\frac{Nm}{w}) 的算法求传递闭包。

时间复杂度: O(N^2+\frac{Nm}{w})

期望得分: 20\sim 30 分。

算法四

把所有能直接引爆的关系都连成边太浪费了,要是只连 d(A,B)=2 的边就好了!
可以发现对于每个 i 满足 d(j,i)=2 j 左右两侧各不超过一个。
证明:设对于 i ,存在不同的 j k 满足 d(j,i)=d(k,i)=2 ,且 X_j<X_k<X_i (重合的炸弹必定互相引爆,违反性质 1,故不可能重合)。
那么由于 X_j+R_j\geq X_i ,有 X_j+R_j>X_k ,即 j 能直接引爆 k 。那么 j,k,i 是一个合法序列,由此有 d(j,i)\geq 3 ,与假设矛盾。

于是只要求出每个炸弹左右两侧最接近的能引爆它的炸弹。两边分别扫一遍,维护 X+R X-R 的单调栈,在栈中二分即可。

那么 m=O(N) 。于是直接用 O(Nm) 的算法求传递闭包。如果你用了其它方法(比如直接搜索能到达的节点来转移)可能有更高的分数。

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

期望得分: 30\sim 100 分。

算法五

v=1 ,那么 F(1,1)=1 ,就成了求以每个点结尾的最长链长。
注意到每个点能到达的范围是一个区间,于是大力用线段树维护区间最值即可。

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

期望得分: 10 分。结合前述算法可得 40 分。

算法六

v\in\{0,1\} ,注意到 F(0,0)=0 而其余结果都是 1
于是大力用两棵线段树分别维护 v=0 v=1 的点的区间最值即可。转移时分别讨论一下。

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

期望得分: 25 分。结合前述算法可得 55 分。

算法七

为啥我写了算法四却 AC 了呀?hahah.gif

这是因为我们可以证明:能够直接或间接到达一个炸弹的炸弹数不超过 O(\log R) 个。
证明方法如下:首先可以证明 \forall x,i ,满足 d(j,i)=x j 左右各不超过一个。
证法类似算法四中的引理。如果一侧有两个,离 i 较远的一个炸弹 k 在炸到 i 的过程中必定可以炸到较近的一个 j ,于是 d(k,i)>d(j,i) 矛盾了。

其次我们可以证明 \forall i,j d(i,j)\leq O(\log R) 。考虑一条最长的引爆序列 a_1,a_2,...,a_n ,前一个能直接引爆后一个。那么在序列中必有 d(a_i,a_j)=|i-j|+1

那么设势函数 \phi(i)=R_{a_i} 。若 X_{a_i} X_{a_{i-1}} X_{a_{i-2}} 之间,则由性质一 \phi(i)\leq\lfloor\frac{\phi(i-2)}{2}\rfloor

否则 X_{a_{i-1}} 一定在 X_{a_{i-2}} X_{a_i} 之间。则由性质二 R_{a_i}+R_{a_{i-1}}\leq R_{a_{i-2}} ,再由性质一 R_{a_i}<R_{a_{i-1}} ,仍然有 \phi(i)\leq\lfloor\frac{\phi(i-2)}{2}\rfloor

那么 \phi 会在不超过 2\log_2 R 长度之内衰减到 0。显然 R=0 的炸弹无法引爆任何其它炸弹。故有 n=O(\log R)

两个结论合在一起可得能直接或间接引爆一个炸弹的炸弹数不超过 4\log_2 R 。证毕。

那么按照算法四的方法暴力枚举上一个点转移即可。

时间复杂度: O(N\log R)

期望得分: 100 分。

如果你常数太大或者写挂了导致复杂度多了若干个 \log 的话你只能得到 70 分部分分了。

T4.绯色 IOI(悬念)CommonAnts

题解由 immortalCO 提供。

算法一

暴力 O(n^2) 建图,每次修改后暴力求匹配。

注意这里可以证明边数是 O(n) 级别(后面证明),

时间复杂度 O(qn^3) O(qn^4) ,期望得分 0\sim 49

算法二

首先,从加边条件可以得出,当且仅当 j=(a_i+b_i)\pmod n j=(a_i-b_i)\pmod n X_i Y_j 之间有连边。那么对于每一个 X_i ,它只和一个或两个 Y_j 连边。我们将和一个 Y_j 连边的情况视为连了两条重边,那么一个 X_i 一定和两个 Y_j 连边

接下来我们来分析一下题目给出的特殊性质:保证所有 X_{ * } 都在匹配中,即二分图匹配数为 m=|X|

考虑满足这个条件的图具有什么性质。根据 Hall 定理,对于任意的 X 的子集 s ,与其相邻的 Y 中的节点集合 t_s 的大小一定不小于 s 。由于每一个 X_i 都和两个 Y_j (记为 a_i b_i )连边,那么我们可以将一个 X_i 视为在新图 H 中一条连接 a_i b_i 的双向边(暂时忽略边权)。这样 Hall 定理就能解释为:对于任意大小为 k Y 点集,其 H 中生成子图的边数不超过 k 。这样就可以得出结论: H 中的每个连通块都是树或环套树(即每个连通块简单环不超过一个),并且也不难看出原图也满足这个条件(即在每条边中间加一个附加点)。

得出这个结论后,我们就可以用 DP 代替匹配算法求答案了。对于树的情况,记录 f(i,k=\{0,1\}) 表示在 k=[i 在子树中被匹配 ] i 子树中的节点的答案。对于环套树的情况,破环为链即可。

时间复杂度 O(nq) ,期望得分 49

算法四

既然是带单点修改的 DP,那大家都知道如何优化了。根据 #511 的经验( 10^6 2\times 10^6 修改)是可以过的,但比较难写。

时间复杂度 O(n+q\log^2n) ,期望得分 73\sim 100

算法五

我们还需要更多的性质。

在前面的分析过程中,加上对边权的考虑。我们可以将问题转化为这样:要求对 H 中每一条无向边进行定向,其中对于每一条边 (a_i,b_i) ,若定向为 a_i\rightarrow b_i 则收益为 X_i a_i 的边权,否则收益为 X_i b_i 的边权,要求满足定向后每条边的入度不超过 1(有一条入边相当于这条边对应的 X_i 匹配了这个点,因此不能超过 1 个),最大化收益。

对每个连通块分情况考虑。如果这个连通块是一棵树,那么定向后一定是一棵有根有向树(入边即为父亲),我们需要决定的是哪个点为根;如果是环套树,那么定向后一定是基环外向树(树边指向环外),但环上的边可以自由决定方向是顺时针还是逆时针。

这样,我们就能很方便的资磁修改了。如果修改的是树中的边,在 DFS 序上建立线段树以维护每个点为根的收益,单次修改 O(\log n) ;如果是环套树的边,若修改的是树边,则判断是否为外向,是则答案加上差值,否则答案不变,如果是环边,则判断它是顺时针还是逆时针,修改对应的答案即可。

这个算法比算法四好写的多,符合 NOIP 的难度限制。

时间复杂度 O(n+q\log n) ,期望得分 100

必须离线的算法

我也不知道有什么必须离线的算法 ……

共 4 条回复

xjr

话说 T2 subtask#1 的测试点 #7 和 #8 为什么完全一样啊?

WAAutoMaton

t1的算法3的dp方程可以四边形不等式优化到nlogn

zx2003

“符合NOIP难度”

Goseqh

题解这么快就发了。。。滋磁一发