[CF1616G] Just Add an Edge 题解

本文主要是介绍[CF1616G] Just Add an Edge 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF link

你谷 link

又是一道神仙题，G 比 H 难，思路非常非常高妙。

首先挖掘这道题的性质，由于每个点只能走到比它大的点，所以如果没有新加的那条边，我们就只能一步一步走，即路径为 \(1\to2\to\cdots\to n\)，所以如果开始就有如此的一条路径我们就可以随意加边，答案直接特判。

考虑没有这样一条路径，则当我们加入一条边 \(\langle x,y\rangle\) 时路径形如 \(1\to2\to\cdots\to y-1\to\overset{S_1}\cdots\to x\to y\to\overset{S_2}\cdots\to x+1\to\cdots\to n\)，其中 \(S_1\) 和 \(S_2\) 是路径经过的点构成的点集，需要满足 \(S_1\cup S_2=[y+1,x-1]\land S_1\cap S_2=\varnothing\)。

发现整条路径可以根据 \(y-1\)，\(y\) 和 \(x\)，\(x+1\) 分成三段，前面一段 \(y\) 前面和 \(x\) 后面都必须是连续的，而中间那段则是由 \(y-1\) 到 \(x\) 和 \(y\) 到 \(x+1\) 的条路径不重不漏覆盖。

前后两段可以直接从 \(1\) 向后走和从 \(n\) 向前走得到范围，最棘手的显然是中间那段，我们要考虑如何找到每一组 \((x,y)\) 满足 \((y-1,x)\) 和 \((y,x+1)\) 两条路径满足上述条件，为方便我们写成 \((y,x)\) 和 \((y+1,x+1)\)。

一种暴力的想法是枚举 \(y\)，然后去找满足的 \(x\)，我们可以用 dp 的思想。

本着求什么设什么的思想我们首先考虑一种简单的想法，就是设 \(f_i\) 表示 \(i\) 能不能作为满足 \(y\) 的那个 \(x\)，我们发现根本没法转移，所以我们考虑先想想看转移是什么样子的，再来思考怎么做。

我们称经过连接相邻的两点的边为爬，经过其它边为跳，那么我们可以以每一次跳为一次转移，我们发现从一组 \((i,i+1)\) 出发如果能只跳一次完全覆盖 \([i,j]\)，只可能是一条路径从 \(i\) 跳到 \(j\)，另一条路径从 \(i+1\) 爬到 \(j-1\)，两条路径端点的前后关系发生了反转。

所以我们可以多设一维 \(0/1\) 状态，表示从 \((y,y+1)\) 能否不重不漏地走到 \((i,i+1)/(i+1,i)\)，转移就直接互相转移。

这样我们就得到了一个 \(\mathcal O(nm)\) 的 dp，我们可以对其进行优化。

我们发现我们为什么时间复杂度会劣，是因为反复转移，即我们在转移的过程中因为先前枚举了 \(y\)，所以对于每个 \(y\) 我们可能会做一样的转移，我们必须减少这些无用的转移，所以我们要试图不去枚举 \(y\)，一个想法是我们找到一个点 \(p\)，使得任意一组 \(y\) 都要到达 \(p\)，然后再到达 \(x\)。

我们可以找到这样一个 \(p\)，事实上相当好找，就是任意一个满足边 \(\langle i,i+1\rangle\) 不存在的 \(i\) 都是满足条件的 \(p\)，方便起见我们可以使用最靠前的一个 \(i\)。

接下来结果就一目了然了，设 \(f_{i,0/1,0/1}\) 表示 \((i,i+1)/(i+1,i)\) 能否到达 \((p,p+1)/(p+1,p)\) 或被 \((p+1,p)\) 到达，这样转移可做，但是会比较烦，最后还需要容斥，考虑用另一种方式，将最后一维二进制压进状态值里，这样的话就可以用值的 \(0/1/2/3\) 表示能否连接** \((p,p+1)\) 和 \((p+1,p)\)，最后因为都满足的变成了 \(3\)，所以容斥的最后一步也省了。

然后计算答案，我们发现有一点问题是我们所谓的前面一段和后面一段连续的路径是不一定存在的，为了减少分类讨论，一个简单的办法是新建两个虚点 \(0\) 和 \(n+1\)，\(0\) 向所有点连边，所有点再向 \(n+1\) 连边，就保证了路径是 \(0\) 到 \(n+1\) 的路径，减少了讨论。

最后我们设 \(l\) 为 \(0\) 能爬到的最靠后的点，\(r\) 为不能爬到 \(n+1\) 的最靠后的点，则新增边 \(\langle x,y\rangle\) 除了满足 \(f_{y,0}\operatorname{bitand}f_{x,0}\ne0\) 以外，还须满足 \(y\le l\land x\ge r\)，直接在满足后面条件的区域统计就好了。

最后一个注意点，当整个序列中只有一个 \(i\) 没有 \(\langle i,i+1\rangle\) 这条边时，不满足题目要求的 \(\langle i,i+1\rangle\) 会被统计如答案，所以记得要减去。

代码有一些细节，整体实现难度一般。

这篇关于[CF1616G] Just Add an Edge 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！