一些圆环问题

Published: July 26, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 环上连通问题
• 环上传递问题
• 环上匹配问题

环上连通问题

现在有$n$个顶点形成一个环，顺时针编号为$0,1,\ldots,n-1$，相邻的两个顶点有连边。第$i$个顶点和$i+1$顶点的连边权重为$w_i$。现在希望有$q$个请求，每个请求指定两个顶点。现在要求保留环中总权重最小的一组边的子集，且每个请求中给出的两个顶点之间总是存在至少一条路径。

首先讲一个线段树的做法。很显然我们至少可以删除一条边，我们循环遍历删除的那条边，之后发现环成了一个序列，而每个请求变成了一段区间，我们不能删除被区间覆盖的边，但是能删除所有不被区间覆盖的边。很显然正常做的时间复杂度为$O(nq)$，但是实际上可以发现对于相邻的两条边，删除一条并恢复另外一条，实际上区间的总插入和删除次数是$O(q)$级别的，因此我们可以用线段树维护，总的时间复杂度为$O((n+q)\log_2n)$。

下面讲一下更快的$O(n+q)$做法。思路非常简单，就是我们可以把每个请求视作一段区间（从较小的顶点到较大的顶点），之后记$f(i)$表示覆盖边$(i,i+1)$的请求集合。可以发现，如果我们删除边$(i,i+1)$后，所有出现在$f(i)$中的请求必须经过$(n-1,0)$，而所有未出现在$f(i)$中的请求可以，不能经过$(n-1,0)$这条边，即一旦选择删除边$(i,i+1)$后，所有查询的连通方案都由$f(i)$给定的，并且总是有方案的。如果$f(i)\neq f(j)$，我们不能同时删除边$(i,i+1)$和$(j,j+1)$，因为二者的方案存在冲突。因此我们只需要维护$f(i)$，并按照它们代表的集合分组，找到分组总权最大的那个分组中的边删除即可。维护分组是很有难度的，我们可以用随机化的方式，为每个分组维护多重集合的哈希信息，之后判同就变成了$O(1)$的整数比较问题。如果使用哈希表来分组，时间复杂度会优化到$O(n+q)$。

环上传递问题

题目1：一个环上有$n$个人，顺时针编号为$1,\ldots,n$。第$i$个人持有$a_i$个糖果。你每个回合可以指定某个人，将他手头的一个糖果传递给顺时针下一个人（前提被选人至少有一个糖果）。现在给定$b_1,\ldots,b_n$，保证$a_1+\ldots+a_n=b_1+\ldots+b_n$，问至少需要多少个回合，才能使得对于任意$1\leq i\leq n$，第$i$个人正好持有$b_i$个糖果。

记$c_i$表示第$i$个人向下一位总共传递的糖果数。可以发现$b_i=a_i-c_i+c_{i-1}$。可以发现如果我们令$c_1=x$，那么有$c_i=x-t_i$。而我们需要的回合数为$\sum_{i=1}^n|x-t_i|$。这个问题等价于在数轴$t_1,\ldots,t_n$上都有一个点，现在要在数轴上选择一个点$x$，它到所有存在的点的总距离最小。很显然我们选择所有存在的点的中位数就能达到最优。

总的时间复杂度为$O(n)$。（我们最后不需要排序，使用第k大算法即可）

题目2：一个环上有$n$个人，顺时针编号为$1,\ldots,n$。第$i$个人持有$a_i$个糖果。你可以对每个$i$指定一个$0\leq c_i\leq a_i$。之后第$i$个人会向顺时针下一个人传递$c_i$个糖果。设之后第$i$个人持有的糖果数为$b_i$，要求返回$b$序列总共有多少不同的可能值，结果对素数$p$取模。

可以发现如果$\min(c)>0$的时候，我们可以让所有$c_i-\min(c)$，$b$是不变的。因此我们可以认为$\min(c)=0$。

令$d_i=c_i-c_{i-1}$。那么有$b_i=a_i-d_i$。很显然有多少不同的$d$序列，就存在多少不同的$b$序列。

下面我们证明$c$和$d$序列一一对应。假设两个不同的序列$c$和$c'$，产生相同的$d$序列。分两种情况讨论：一种是存在$i$使得，$c_i=c'_i$，那么由于$d$相同，可以直接得出$c=c'$。还有一种情况是存在一个$i$，使得$c_i=0$且$c'_i>0$，这时候由于$d$相同，可以得出$c'_i$是$c'$中的最小值，而它不满足$\min(c')=0$。

因此我们的答案就变成了存在多少$c$序列，满足$0\leq c_i\leq a_i$，且$\min(c)=0$。答案为$\prod_{i=1}^n(a_i+1)-\prod_{i=1}^na_i$。

总的时间复杂度为$O(n)$。

环上匹配问题

题目1：给定$2n$个人，顺时针编号为$1,\ldots,2n$。现在要求让环上的两两拉一条绳子，且绳子之间的交点数最多（重复的交点也要多次统计）。

很显然让$i$和$i+n$共拉一条绳子，这时候任意两条绳子都有交点，达到理论最大值${n\choose 2}$。

总的时间复杂度为$O(n)$。

题目2：给定$2n$个人，顺时针编号为$1,\ldots,2n$。现在要求让环上的两两拉一条绳子，且绳子之间的交点数最多（重复的交点也要多次统计）。其中我们已经存在$k$条绳子，拉第$i$条绳子的人为$a_i$和$b_i$。

提供一道题目。

实际上我们把所有未匹配的人按照顺时针排序后，第$i$个人和第$i+n-k$个人拉一条绳子即可。

可以发现如果$(a,b)$和$(c,d)$形成的两条绳子无交点，那么$(a,d)$和$(c,b)$就一定有交点，且与其它绳子的交点总数是不会减少的。换言之最优解的情况下，未选择的绳子必须两两相交，而这时候只有一个唯一解，就是每个人和对面的人拉绳子。

总的时间复杂度为$O(n)$。