LibreOJ β Round #3 题解

liu_cheng_ao 于 2017-08-04 22:07:42 发表,2017-08-04 22:07:42 最后更新

T1.绯色 IOI(开端)spj

题解由 spj 提供。

算法一

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

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

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

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

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

算法二

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

f(S,i)f(S,i)f(S,i) 为从点 iii 出发且经过 SSS 中每个结点恰好一次最后到点 111 的路径长度最小值,其中 i∈Si\in SiS。当 iS 时,f(S,i)=+∞f(S,i)=+\inftyf(S,i)=+

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

否则,f(S,i)=minj{f(S−{i},j)+(wi−wj)2∣j∈V}f(S,i)=\min_j\{f(S-\{i\},j)+(w_i-w_j)^2|j\in V\}f(S,i)=minj{f(S{i},j)+(wiwj)2jV}

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

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

算法三

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

首先我们将点权排序。接下来不妨设 w1≤w2≤⋯≤wn−1≤wnw_1\le w_2\le\cdots\le w_{n-1}\le w_nw1w2wn1wn,则有以下性质:

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

证明 不妨设最优解 CCC 中从点 111 到点 nnn 的部分经过的点集为 A={v1,v2,⋯,vl}A=\{v_1,v_2,\cdots,v_l\}A={v1,v2,,vl},其中 v1=1v_1=1v1=1vl=nv_l=nvl=nv1<v2<⋯<vlv_1<v_2<\cdots<v_lv1<v2<<vl

考虑 1→n1\rightarrow n1n 只经过 AAA 中的点的最短路 PPP。对任意 i=2,3,⋯,vli=2,3,\cdots,v_li=2,3,,vl,考虑 PPP 中任意一条满足 p<i,q≥ip<i,q\ge ip<i,qi 的边 (vp,vq)(v_p,v_q)(vp,vq),假设 q>iq>iq>i,记 a=wvi−wvpa=w_{v_i}-w_{v_p}a=wviwvpb=wvq−wvib=w_{v_q}-w_{v_i}b=wvqwvi,将这条边拆成 (vp,vi),(vi,vq)(v_p,v_i),(v_i,v_q)(vp,vi),(vi,vq) 两边,由于 (a+b)2≥a2+b2(a+b)^2\ge a^2+b^2(a+b)2a2+b2,长度不会增加。因此总可以令 q=iq=iq=i。同理,总可以令 p=i−1p=i-1p=i1

于是 v1→v2→⋯→vlv_1\rightarrow v_2\rightarrow\cdots\rightarrow v_lv1v2vl 是一条最短路,性质得证。n→1n\rightarrow 1n1 部分同理。

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

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

j=nj=nj=n,则 f(i,j)=(wi−wj)2f(i,j)=(w_i-w_j)^2f(i,j)=(wiwj)2

否则,f(i,j)=min{f(i,j+1)+(wj−wj+1)2,f(j,j+1)+(wi−wj+1)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(i,j)=min{f(i,j+1)+(wjwj+1)2,f(j,j+1)+(wiwj+1)2}

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

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

算法四

仍假定 w1≤w2≤⋯≤wn−1≤wnw_1\le w_2\le\cdots\le w_{n-1}\le w_nw1w2wn1wn。不妨设最优解中两条 1→n1\rightarrow n1n 的路径为 AAABBB。事实上,这个问题有更强的性质:

性质2 存在最优解,对任意 i=2,3,⋯,n−2i=2,3,\cdots,n-2i=2,3,,n2,点 iiii+1i+1i+1 既不同时属于 AAA 也不同时属于 BBB

证明 假设 i,i+1i,i+1i,i+1 均属于 AAA,其中 2≤i≤n−22\le i\le n-22in2。设 (p,q)(p,q)(p,q)BBB 中任一满足 p<i,q>i+1p<i,q>i+1p<i,q>i+1 的边。删去边 (i,i+1),(p,q)(i,i+1),(p,q)(i,i+1),(p,q) 并加入边 (i,q),(p,i+1)(i,q),(p,i+1)(i,q),(p,i+1),设 a=wi−wpa=w_i-w_pa=wiwpb=wi+1−wpb=w_{i+1}-w_pb=wi+1wpc=wq−wpc=w_q-w_pc=wqwp,由于

b2+(c−a)2=a2+b2+c2−2ac≤a2+b2+c2−2ab=(b−a)2+c2b^2+(c-a)^2=a^2+b^2+c^2-2ac\le a^2+b^2+c^2-2ab=(b-a)^2+c^2b2+(ca)2=a2+b2+c22aca2+b2+c22ab=(ba)2+c2

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

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

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

看不出性质怎么办

我们可以打表找规律!

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

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

T2.绯色 IOI(抵达)mathematician

题解由 mathematicianCommonAnts 提供。

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

算法一

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

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

算法二

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

iii 的庇护所为 pip_ipi

性质1 pip_ipi 中所有环长为 222
(即 iiipip_ipi 构成完美匹配)

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

证明2 考虑任意一个叶结点 uuu,设与 uuu 相邻的点为 vvv,则 pu=vp_u=vpu=v。又由于 ppp 是排列,必有 pv=up_v=upv=u。删除 uuuvvv 并继续进行这个过程可以证明。

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

考虑到 nnn 较小,我们可以使用网络流或匈牙利算法(Ford–Fulkerson algo.)求出完美匹配。

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

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

算法三

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

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

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

算法四

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

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

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

T3.绯色 IOI(危机)CommonAnts

题解由 CommonAnts 提供。

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

算法一

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

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

期望得分:0∼100\sim 10010 分。

算法二

性质一告诉我这是个 DAG,求和式表明答案只和相邻两项有关,于是可以愉快地 DP 咯。
f(i)f(i)f(i) 表示以 iii 结尾的最大安全程度,于是有 f(i)=maxj                  if(j)+F(vj,vi)

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

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

期望得分:202020 分。

算法三

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

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

期望得分:20∼3020\sim 302030 分。

算法四

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

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

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

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

期望得分:30∼10030\sim 10030100 分。

算法五

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

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

期望得分:101010 分。结合前述算法可得 404040 分。

算法六

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

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

期望得分:252525 分。结合前述算法可得 555555 分。

算法七

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

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

其次我们可以证明 ∀i,j\forall i,ji,jd(i,j)≤O(logR)d(i,j)\leq O(\log R)d(i,j)O(logR)。考虑一条最长的引爆序列 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an,前一个能直接引爆后一个。那么在序列中必有 d(ai,aj)=∣i−j∣+1d(a_i,a_j)=|i-j|+1d(ai,aj)=ij+1

那么设势函数 ϕ(i)=Rai\phi(i)=R_{a_i}ϕ(i)=Rai。若 XaiX_{a_i}XaiXai−1X_{a_{i-1}}Xai1Xai−2X_{a_{i-2}}Xai2 之间,则由性质一 ϕ(i)≤⌊ϕ(i−2)2⌋\phi(i)\leq\lfloor\frac{\phi(i-2)}{2}\rfloorϕ(i)2ϕ(i2)

否则 Xai−1X_{a_{i-1}}Xai1 一定在 Xai−2X_{a_{i-2}}Xai2XaiX_{a_i}Xai 之间。则由性质二 Rai+Rai−1≤Rai−2R_{a_i}+R_{a_{i-1}}\leq R_{a_{i-2}}Rai+Rai1Rai2,再由性质一 Rai<Rai−1R_{a_i}<R_{a_{i-1}}Rai<Rai1,仍然有 ϕ(i)≤⌊ϕ(i−2)2⌋\phi(i)\leq\lfloor\frac{\phi(i-2)}{2}\rfloorϕ(i)2ϕ(i2)

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

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

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

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

期望得分:100100100 分。

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

T4.绯色 IOI(悬念)CommonAnts

题解由 immortalCO 提供。

算法一

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

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

时间复杂度 O(qn3)O(qn^3)O(qn3)O(qn4)O(qn^4)O(qn4),期望得分 0∼490\sim 49049

算法二

首先,从加边条件可以得出,当且仅当 j=(ai+bi)(modn)j=(aibi)(modn)XiX_iXiYjY_jYj 之间有连边。那么对于每一个 XiX_iXi,它只和一个或两个 YjY_jYj 连边。我们将和一个 YjY_jYj 连边的情况视为连了两条重边,那么一个 XiX_iXi一定和两个 YjY_jYj 连边

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

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

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

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

算法四

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

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

算法五

我们还需要更多的性质。

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

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

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

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

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

必须离线的算法

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

共 4 条回复

xjr

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

WAAutoMaton

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

zx2003

“符合NOIP难度”

Goseqh

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