一些可行解问题

Published: January 17, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 网格问题
  • L形覆盖
• 原序列恢复问题
  • 从每对元素和恢复
  • 从子集和恢复
• 图问题
  • 哈密顿环分解
    • 二分图版本
    • 有向图版本
  • 哈密顿路径
  • 环与最大公约数
  • 生成树
• 元素替换
  • 两元素和替换
• 动态规划
  • 归0问题
• 数论
  • 前缀和非0
  • 不同前缀和
  • 不同前缀积
• 区间和问题
• 二维移动问题

网格问题

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)$。

从子集和恢复

给定一个包含$n$个整数的多重集合$A$，以及它的$2^n$个子集和$S$。现在我们丢失了$A$，仅保留子集和，希望找到一个合法的集合$A$，或者判断无解。其中$1\leq n\leq 20$，且子集和为整数（可能为正数或负数）。

一道原题。

题解来自这里。我这里重新阐述一下。

$w(T)$表示$T$中所有元素的和。

首先我们考虑$A$中仅存在非负整数的情况。我们从$S$中删除一个$0$，之后$S$中仅包含所有非空集合的子集和。我们可以贪心求解剩下的问题，维护集合$A$，初始为空。设$S$中最小的元素为$e$，我们将$e$加入$A$中，并从$S$中删除所有包含$e$的$A$的子集和。重复上面这个流程直到$S$为空。最后只要验证$A$的大小正好为$n$即可。

下面我们考虑扩展原问题，支持子集和中出现负数。

设最小的负数为$m$。之后我们考虑$S-m$（即将$S$中所有元素都减去$m$），找到它的一组可行解$B$。之后我们考虑$B$中的一个和为$-m$的子集$B^{-1}$。我们取$A$为$B$中$B^{-1}$部分所有元素取反后得到的集合。考虑任意$B$的子集$T$，可以发现$\sum T\oplus B^{-1}\in S$，其中$T\oplus B^{-1}$表示对于任意$e\in T$，如果$e\in T$，则从$T$中删除$e$，否则将$-e$加入$T$中，很显然同时有$T\oplus B^{-1}\subseteq A$。可以发现$\oplus$操作是可逆的，它是一个定义在$B$的子集族，值域为$A$的子集族的双射函数。

同理如果$A$存在，我们可以记$A^{-1}$表示$A$中所有负数的集合。考虑任意$A$中的集合$T$，我们可以通过将$A$中$A^{-1}$部分全部取反得到$B$，可以发现$B$是$S-m$的一个有效解。实际上对于任意$T\subseteq A$，可以发现$T\oplus A^{-1} \subseteq B$。且$\oplus$操作是可逆的，它是一个定义在$A$的子集族，值域为$B$的子集族的双射函数。

因此我们给出了原问题解和$S-m$问题解的转换方式，以及二者解存在的等价性。

图问题

哈密顿环分解

二分图版本

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

二维移动问题

题目1：在一个二维平面上，我们初始在$(0,0)$，目的地为$(x,y)$。现在允许移动$n$次，第$i$次移动的距离为$d_i$。每次移动需要选择上下左右四个方向中的一个移动。现在问是否存在一种方向选择，使得我们最终能移动到$(x,y)$，如果有则找到一种方案。其中$1\leq n\leq 10^5$，$1\leq d_i\leq 10^3$。

提供一道题目。

首先这个问题很难直接做。因为我们需要将移动分类，分别作用在横坐标或纵坐标上。但是很神奇的是，如果我将所有坐标都绕原点旋转45度，现在我们可以沿着四个对角线移动。（这里为了方便，我们可以把坐标再乘上$\sqrt{2}$以避免出现小数）。

这时候我们要移动到$(x-y,x+y)$去，对于第$i$次移动，可选的移动为$(\plusmn d_i,\plusmn d_i)$，这意味着横坐标和纵坐标可以独立选择符号。这时候我们可以独立考虑问题，选择一组变量$s_1,\ldots,s_n$，使得$\sum_{i=1}^ns_id_i=x$，其中$s_i=\plusmn 1$。

这个我们可以先将所有$s_i$赋予$1$，之后选择一个子集赋值为$-1$，这时候问题变成选择一个子集和正好为某个特定的数，这是一个简单的背包问题，但是需要用到一些特殊的优化技巧，从而做到$O(n\max_{i=1}^nd_i)$的时间复杂度。