一些可行解问题

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\times m$的网格,起点为$(x_1,y_1)$,终点为$(x_2,y_2)$,要求找到一条哈密顿路径。

元素替换

两元素和替换

题目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})$。