一些可行解问题

Published: by Creative Commons Licence

  • Tags:

网格问题

L形覆盖

TODO

原序列恢复问题

从每对元素和恢复

题目1:给定$n$个元素$a_1,\ldots,a_n$,以及它们的$m={n\choose 2}$个配对的和组成的序列$b_1,b_2,\ldots,b_m$。现在已知序列$b$,求一组可能的$a$,如果不存在则报告无解。

提供一道题目

首先当$n\leq 2$的时候,问题是非常简单的,这里仅考虑$n\geq 3$的情况。

首先我们将$b$进行排序,并且认为$a$也是有序的。很显然这时候$a_1+a_2=b_1$,$a_1+a_3=b_2$,之后我们可以发现$a_2+a_3$可能是$b_3,b_4,\ldots,b_n$中的任意一个。我们暴力枚举$a_2+a_3=b_i$,之后我们可以通过$a_1=\frac{b_1+b_2-b_i}{2}$来得到一个可能的$a_1$,最多有$n-2$个可能的选择。

接下来我们来考虑已知$a_1$,构造其它元素的算法。

我们扫描$b$,假设现在在扫描$b_i$,并且我们已经求解了$a$序列的前$k$个元素,并且已知元素的配对和的集合为$S$,且$S$中存放一个额外的哨兵$-\infty$。这时候有三种情况:

  • $b_i\gt \min(S)$,这时候一定无解。
  • $b_i=\min(S)$,这时候我们从$S$中删除$b_i$并结束流程。
  • $b_i\lt \min(S)$,我们得到$a_{k+1}=b_i-a_1$,并且将$a_2+a_{k+1},a_3+a_{k+1},\ldots,a_k+a_{k+1}$加入到$S$中。

上面的流程可以通过维护一个优先队列实现,总的时间复杂度为$O(n^2\log_2n^2)$。

由于这个流程我们总共会调用$O(n)$次,因此总的时间复杂度为$O(n^3\log_2n^2)$。

图问题

哈密顿环分解

二分图版本

题目1:给定二分图$G=(V,E)$,其中$V$由两个点集$A$和$B$组成,且所有边的一个端点为$L$中顶点,另外一个端点为$R$中顶点。要求将二分图分为任意个哈密顿环,要求每个顶点恰好在一个哈密顿环中出现正好一次,其中$1\leq V,E\leq 10^5$。

提供一道题目:SRM788 ParkPlace。

实际上哈密顿回路问题一般需要转换为欧拉环才能做。我们要做的实际上是删除一些边,保证每个顶点的度数都是$2$,这时候跑出的欧拉环实际上就是哈密顿路径。

要让每个顶点的度数都为$2$,我们可以考虑加入一个超级源点和汇点,之后从源点向所有$L$中顶点拉一条容量为$2$的边,从$R$中顶点向汇点拉一条容量为$2$的边。这样如果能跑出最大流$2|L|=2|R|$,就能得到哈密顿环分解。

有向图版本

题目1:给定有向图$G=(V,E)$。要求将图分为任意个哈密顿环,要求将图分解为若干个哈密顿环,每个顶点恰好在一个哈密顿环中出现正好一次,其中$1\leq V,E\leq 10^5$。

由于是哈密顿回路,因此我们实际上需要删除一些边,保证每个顶点的入度和出度均为$1$,这样我们就能将图分解为若干个欧拉环。而在度数为$1$的时候,欧拉环实际上就是哈密顿回路。

接下来的问题就是我们需要删除一些边,来保证每个顶点的入度和出度都是$1$。一种简单的思路是我们将每个顶点分解为两个顶点,一个染黑色,一个染白色,对于有向边$(u,v)$,我们从黑$u$向白$v$拉一条边。这样如果我们能找到一个完美匹配,就能找到一个哈密顿回路了。

时间复杂度为$O(E\sqrt{V})$。

哈密顿路径

题目1:给定一个包含$n$个顶点的完全图,之后给定一个序列$a_1,\ldots,a_n$,其中$a_i\neq i$,要求从图中删除边$(i,a_i)$。要求找到图中的一条哈密顿路径,或者报告无解。其中$2\leq n\leq 10^6$。

提供一道题目

很显然$n=2$的时候一定无解。我们证明其它情况下一定有解。

我们可以认为算法的流程如下,初始的时候我们有一个禁用元素$x=-1$和一个空序列$b$,之后我们要选择一个未在$b$出现的数$y$,且$y\neq x$,加入到$b$中,之后令$x=a_y$。

下面我们证明这样一个命题:当$n\geq 3$的时候,且$x,a_1,\ldots,a_n$中没有任意一个数出现达到$n$次,那么一定有解。

当$n=3$的时候我们可以暴力枚举所有可能的置换,并证明解都是存在的。下面我们认为在较小的$n$的时候命题都成立,那么我们可以随机选择一个数$i$,如果$a_i$在$a_1,\ldots,a_n$中出现次数达到$n-1$,那么这意味着$x\neq a_i$,我们将$a_i$加入到$b$尾部,这时候可以发现还剩下$n-1\geq 2$个元素,它们是一个团,我们可以挑选一个合适的元素加到$b$尾部,之后可以随意插入。否则这时候$a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n$依旧满足条件,通过归纳法可以证明解的存在。

因此这里我们就给出了解法,每次随机选择一个数$i$,之后检查$a_i$是否被剩下的顶点所孤立,如果是则使用$a_i$即可。直到顶点数剩下$3$个的时候,尝试所有置换即可。

时间复杂度为$O(n+3!)$。

环与最大公约数

考虑这样一个问题,给定$n$个顶点,$m$条带权边的一个有向图。

下面要求回答$q$个询问。每个询问要求判断是否存在这样一个环(环中可以出现重复的边),其中包含给定点$v_i$,且环的长度$L$,满足$L=x_i\pmod{p_i}$。

其中$1\leq n,m,q\leq 10^6$,且边的权重为正数,且不超过$10^9$。

提供一道题目

很显然,环中出现的点一定属于相同的双连通分量,因此我们可以单独考虑每个不同的双连通分量。下面我们假设整个图双连通。

我们从点$1$出发,维护每个点可能的距离,对于顶点$i$,其形式为$kc_i+d_i$,其中$k\geq 0$,初始的时候有$c_i=0$,这表示对于任意模数$p$,图中都存在长度为$c_i$的环,且从点$1$到点$i$存在一条长度为$d_i$的路径。

之后可以类似最短路一样进行迭代更新,这里可以仿照spfa算法。现在我们尝试要合并两个公式$kc+d$和$te+g$。考虑$c$和$e$的具体意义,这意味着图中存在长度为$l=gcd(c,e)$的环。这样两个公式可以化作$kl+d$和$kl+g$。接下来考虑$d$和$e$的意义,考虑任意一条长度为$M$的从当前顶点到顶点$1$的路径,那么这指出图中存在两个长度为$d+M$和$g+M$的环,因此一定存在长度为$|d-g|$的环(注意都是在对$p$取模意义下的)。因此合并后的结果为$k\cdot gcd(c,e,|d-g|)+d$,很显然合并后的结果,包含$kc+d$和$te+g$的所有信息。

很显然一个顶点只会被更新最多$O(\log_210^9)$次(每次都从初始的$d_i$中删除掉一些因子),因此预处理时间复杂度为$O((n+m)\log_210^9)$。

但是实际上我们可以观察发现,我们要求的环的长度实际上只需要考虑所有的边即可,只需要预先通过递归算出$d_i$。这样做预处理的时间复杂度为$O(m+\log_210^9)$。

接下来询问就非常容易了,我们只需要找到$c_{v_i}$,如果$\gcd(c_{v_i},p_i)\mid x_i$,那么就存在,否则不存在。这部分时间复杂度为$O(q\log_210^9)$。

生成树

题目1:给定一个包含$n$个顶点$m$条边的无向连通图,且第$i$个顶点的资金为$w_i$。现在要求找到一个边序列$e_1,\ldots,e_{n-1}$,其中这组边形成一个生成树,且边序列合法。一个序列合法是指在处理$e_1=(u,v)$的时候,有$u$所在连通块的剩余资金与$v$所在连通块的剩余资金之和至少为$x$,之后合并二者所在的连通块,并且将剩余资金减去$x$,在这个情况下$e_2,\ldots,e_{n-1}$是合法的序列。判断是否存在这样的序列,如果存在则找到一个合法序列。

提供一道题目

很容易序列存在的必要条件,发现一个必要条件$\sum_{i=1}^nw_i\geq (n-1)x$。下面我们证明这同时也是充分条件。我们通过构造法来证明。

如果存在一个连通块剩余资金不少于$x$,那么就从它出发与相邻的其它连通块合并。我们重复上面这个过程,直到所有连通块的资金都少于$x$。

接下来考虑如果存在两个不同的连通块,它们的剩余资金额少于$x$,那么一定有$\sum_{i=1}^nw_i<x+(n-2)x=(n-1)x$,这与前提相悖,因此不可能发生。这意味着这时候任意两个相邻的连通块都可以合并,并且合并后的所有连通块依旧满足没有连通块的资金量达到$x$。

上面的过程可以$O(n+m)$解决。

元素替换

两元素和替换

题目1:初始的时候,你有两个整数$1$,$0$,之后你需要不断的计算两个整数的和,并用来替换其中一个整数。要求找到最少的操作次数,使得某个元素等于$c$。要求构建这样一组操作序列并输出。

我们可以枚举最后的状态$(c,x)$,其中$0\leq x\leq c$。之后可以发现它的前一种状态是唯一的,只有$(c-x,x)$。因此根据这个唯一性,我们可以判断它是否是一个可行的结果。可以注意到这里类似于欧几里德算法的流程,其时间复杂度为$O(\log_2c)$。

因此总的时间复杂度为$O(c\log_2c)$。

题目2:初始的时候,你有两个向量$(1,0)$和$(0,1)$之后你需要不断的计算两个向量的和,并用来替换另外一个向量。要求构造出一个可能的操作序列,使得$(x,y)$出现在最终的两个向量中,或者报告无解。

这里如果我们采用题目1的方式,暴力枚举最终状态,时间复杂度为$O(xy\log_2xy)$。

但是可以发现这个实际上是The Stern-Brocot tree的构建过程。其有解的前提是$gcd(x,y)=1$。之后我们可以模拟SB树的构建流程,得到最终的序列。

动态规划

归0问题

题目1:给定$2n$个数,其中$n$个为正数,$n$个为负数,且所有数的绝对值不超过$n$。现在希望找到一个非空子集,满足子集和为$0$。

提供一道题目

将正数集合记作$A$,将所有负数绝对值集合记作$B$。不失一般性,认为$B$的总和不小于$A$。记$a_i$表示$A$中前$i$个元素的和,$b_j$表示$B$中前$j$个元素的和。对于每个$i$,找到一个最大的$f_i$,满足$a_i\geq b_{f_i}$,很显然此时$0\leq c_i=a_i-b_{f_i}\leq n-1$。如果$c_1,\ldots,c_n$中存在$0$,则我们直接找到了一个解。否则根据鸽巢定理,至少存在一对不同的下标$i,j$,满足$c_i=c_j$且$i<j$,这意味着我们可以选择第$i+1$个正数到第$j$个正数,以及第$f_i+1$个负数到第$f_j$个负数,它们合成的子集和为$0$。

上面的算法的时间复杂度为$O(n)$。

题目2:给定$n$个数$a_1,\ldots,a_n$,每个数的范围都在$-1000$到$1000$范围内。要求找到一组非负系数$c_1,\ldots,c_n$,满足$\sum_{i=1}^nc_ia_i=0$,且$\sum_i^nc_i$最小。其中$n\leq 10^6$。

一道题目

先讲一下我的做法。首先如果有解,要么存在某个$a_i=0$,要么存在两个数$a_i<0<a_j$。前者非常简单,所以我们仅讨论一下后者。这时候我们发现取$c_i$取$a_j$,而$c_j$取$-a_i$的时候,就有$c_ia_i+c_ja_j=0$。因此我们可以直接推出结果不可能超过$2000$。

实际上我们可以将$a$序列去重,这样就能保证$n\leq 2000+1$。

我们可以用最短路来解决这个问题,初始点为$a_1,\ldots,a_n$,而最短路需要考虑的范围为$-2\cdot 10^6$到$2\cdot 10^6$之间。把每个数当成边,边长都是$1$,因此如果我们用BFS的话时间复杂度为$O(8\cdot 10^9)$。但是这里可以用BitSet优化,因此时间复杂度为$O(\frac{8}{6}\cdot10^8)$。还是可以接受的。

但是这个问题实际上可以优化到$O(2001^2)$。我们可以认为取到的最短的总和为0的序列为$b_1,\ldots,b_k$,由于前缀和和后缀和异号,因此我们能通过调整顺序保证所有前缀和的绝对值都不超过$1000$。于是我们就只需要为$-1000$到$1000$建立$2001$个顶点,跑最短路。

并且这里我们还可以继续采用BitSet进行优化,这样时间复杂度可以降低到$O(\frac{2001^2}{60})$。

数论

前缀和非0

题目1:给定$n$个数$a_1,\ldots,a_n$以及一个素数$p$,要求重新排列这$n$个数,满足新序列的任意一段非空前缀和在模$p$意义下都不等于$0$,或者报告无解。

提供一道题目

首先如果$\sum_{i=1}^na_i=0\pmod p$,那么肯定无解。否则我们可以将所有$0$放在尾部。现在我们假设序列中不含$0$。

记$x$为出现次数最多的元素,记$C(x)$表示$x$的出现次数,那么$2\cdot C(x)\leq n$的情况下一定是有解的。因为我们每次可以选择一个数加到构建的序列尾部,我们直接选$x$,如果不行,就选择任意一个可行的数$y$,之后再加入$x$,由于$y\neq 0$,因此次数加入$x$,前缀和不可能变成$0$。可以发现这样操作下去会使得出现次数最多的数始终不超过一半。(除非只剩下一个元素,这时候由于保证总和非$0$,因此直接追加就可以了)

但是实际上条件还要更宽松点。考虑将所有元素都乘上$x^{-1}$,注意这样做不会影响前缀和是否等于$0$。这时候$1$的出现次数最多,我们最多可以允许多少个$1$,答案是$p-1+\sum_{i=2}^{p-1}(p-i)C(i)$。做法就是先使用$p-1$个$1$,之后追加一个非$1$元素$y$,之后追加$p-y$个$1$。

要构建一个具体的解,我们可以用贪心算法来做,每次选择出现次数最多的元素,增加直到它不再最多或者会出现$0$前缀为止。时间复杂度为$O(n\log_2n)$。

不同前缀和

题目1:将$0,1,\ldots,n-1$重新排列,要求所有前缀和在模$n$意义下不同,如果无解则报告。

首先特判$1$,一定是有解的。

容易发现$0$只能出现在首尾。无论哪种情况,如果$1+2+\ldots+(n-1)=0\pmod n$,那么一定无解。

之后考虑偶数的情况。实际上这种情况下一定有解,设$a$为答案序列,如果$i$是偶数,则$a_i=-i\pmod n$,如果$i$是奇数,则$a_i=i$。这时候前缀和为$0,1,-1,2,-2,\ldots,\frac{n}{2}$,两两不同。

不同前缀积

题目1:将$0,1,\ldots,n-1$重新排列,要求所有前缀积在模$n$意义下不同,如果无解则报告。

首先特判$1$,一定是有解的。

容易发现$0$只能出现在尾部。如果$n$是合数,则仅$4$可能有解,否则一定无解。事实上如果$n=xy$,其中$x\neq y$,那么任意同时包含$x,y$的前缀积一定为$0$。故只有可能$n=p^2$且$n/p-1=1$的情况下可能有解,其中$p$是素数。这时候只有可能是$4$。

之后考虑素数的时候的情况。如果我们找到一个原根$g$,之后考虑前$1,\ldots,n-1$的排列,这时候我们将所有元素$x$转换为$\log_gx$后,先在前缀积等价于$g^{t_i}$,其手中$t_i$是对数形式的前缀和。我们只需要保证前缀和不同即可。着回到了不同前缀和问题。

但是实际上还存在一种更加简单的方式,就是令第一个元素为$1$,而第$i$个元素为$\frac{i}{i-1}$,$i>1$。这时候前$i$个元素的前缀积为$i$,且所有元素不同。

区间和问题

题目1:给定一个长度为$n$的数组$a$,数组中的初始值都是$0$。现在给定$m$个请求,第$i$个请求给定一个区间$[l_i,r_i]$以及一个值$v_i$,其表示将区间中所有元素都加上$v_i$。现在要求找出一组可能的$v_1,\ldots,v_m$,要求满足$|v_i|=1$,且执行完所有请求后,数组中所有元素绝对值不超过$1$。

对于请求$A$,用$A.l$表示$A$的左边界,$A.r$表示$A$的右边界,$A.v$表示$A$的修改值。

我们维护所有未处理的请求的集合$Q$,记$L(Q)=\min_{A\in Q}A_l$。则我们执行下面流程,并且始终保证下面不变式:

对于$i<L(Q)$,有$|a_1|\leq 1$,而对于$i\geq L(Q)$,有$a_i=0$。

如果剩下的请求不超过$2$个,那么我们任意赋值即可,这样就得到一组可行解。否则我们可以从$Q$中弹出左边界最小的两个请求(如果有多个则任意),分别记作$A$和$B$,其中我们用$A.l$表示$A$的左边界,$A.r$表示$A$的右边界。分多种情况讨论:

  • $A.r<B.l$,我们可以任意赋值$A.v$,之后将$B$插回$Q$。
  • $A.r\geq B.r$。我们在$A$和$B$之间加入一条边,表示二者不能赋予相同值。之后将$A.l$修改为$B.r+1$,如果$A$代表的区间不空,则重新插回$A$。
  • $A.r<B.r$。我们在$A$和$B$之间加入一条边,表示二者不能赋予相同值。之后将$B.l$修改为$A.r+1$,如果$B$代表的区间不空,则重新插回$B$。

可以发现上面过程中不变式始终是成立的。但是实际上还有一些请求我们尚未真正的赋值。我们可以发现如果将请求视作顶点,之后问题变成了二染色问题。对于边$(u,v)$,且$u$比$v$更早删除,则认为$u$的父亲为$v$,可以发现图实际上是一个森林,里面是没有环的,因此始终是可以二染色的。

这里我们可以用一个最小堆来维护$Q$。时间复杂度为$O(m\log_2m)$。