集合划分问题

Published: by Creative Commons Licence

  • Tags:

数字匹配问题

题意

假设有一个长度为$nk$的数字,其中包含$n$个$1$,$n$个$2$,…,$n$个$k$。我们将整个序列分裂为$n$个子序列,每个子序列需要同时包含$1,2,\ldots,k$,且这$k$个数字按顺序出现。问有多少种分裂方案。

比如k为2,n为2,那么考虑这样一个序列1,1,2,2,就有两种分裂方案,第一个1和第一个2在一个子序列,或第一个1和第二个2在一个子序列。

题解

我们维护一个数组$c$,$c_i$表示以$i$出现的次数,初始时都为0,之后我们从左往右扫描并更新数组$c$。假设现在我们扫描到$x$,如果$x=1$,则我们简单修改$c$数组。否则我们发现这个$x$可能与前面的$c_{x-1}$个$x-1$匹配,但是考虑到已经有$c_{x}$个$x-1$被匹配了,因此还可以匹配$c_{x}-c_{x-1}$个数。因此我们将结果乘上$c_{x}-c_{x-1}$,只有修改$c$数组。

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

提供一个Atcoder的题目

多色球划分问题

题目1:给定$nk$个球,共有$k$种颜色,每种颜色的球正好有$n$个。每个球同时有一个权值,现在我们希望将这些求划分为$n$个大小为$k$的子集,每个子集中正好有$k$种不同的颜色,且定义每个集合的权值为集合中球的最大权值减去最小权值,而定义划分的权值为划分得到的每个集合的权值之和。现在要求给出所有划分中的最小权值,并给出一套划分方案。

注意到划分$T$的权值为$\sum_{s\in T}(\max(s)-\min(s))=\sum_{s\in T}\max(s)-\sum_{s\in T}\min(s)$。因此如果我们能同时取到$\sum_{s\in T}\max(s)$的最小值和$\sum_{s\in T}\min(s)$的最大值就可以保证结果是最小的。

事实上我们可以直接给出算法,就是我们将同颜色的球按照权值从小到大进行排序,其中颜色$i$,第$j$大的球我们记作$b_{i,j}$。我们将$b$用二维网格表示出来,$b_{i,j}$表示网格第$i$行第$j$列元素,那么一种简单的划分方案就是每一列的球作为一个子集。

现在我们要证明上面的划分方案是最优的。我们先证明上面的划分中$\sum_{s\in T}\max(s)$最小。我们可以假设集合之间按照最大权值权值进行从小到大排序。这时候我们发现第$j$个集合的最大权值一定不可能小于$\max_ib_{i,j}$。同理可以证明上面的划分的$\sum_{s\in T}\min(s)$是最大的。

题目2:给定$3n$个球,共有$3$种颜色,每种颜色的球正好有$n$个。每个球同时有一个权值(权值互不相同),现在我们希望将这些求划分为$n$个大小为$3$的子集,每个子集中正好有$3$种不同的颜色,且定义每个集合的权值为集合中球的最大权值减去最小权值,而定义划分的权值为划分得到的每个集合的权值之和。现在要求给出所有划分中的最小权值。并给定有多少划分方案的权值为给定最小权值,结果对某个$p$取模。

那么现在我们考虑如何计算方案数。由于题目中给了权值互异的条件,因此任意权值最小的划分中,可以保证最大权值第$j$大的集合的最大权值为$\max_ib_{i,j}$,以及最小权值第$j$大的集合的最小权值为$\min_ib_{i,j}$。

我们将每一列中最小的球标记为1,最大的球标记为3,而其余球标记为2。之后将所有球按照权值从小到大排序,会发现这实际上是一个数字匹配问题。

提供一道Atcoder题目

子序列划分问题

题目1:给定一个序列$1,\ldots,n$,要求将其划分为任意数目个非空子序列,且每个序列的长度不超过3。子序列的顺序不重要,比如说划分$[0],[1]$和序列$[1],[0]$是认为相同的。

一般的方式从前向后处理子序列,记$f(i,j)$为仅考虑前$i$个元素,还有$j$个元素未分配的方案数,这样做的时间复杂度和空间复杂度为$O(n^2)$。

换一种思路,我们可以把时间复杂度优化到$O(n)$。注意到这$n$个数的数值本身是没有意义的,只是标志不同而已,因此我们可以从中删除几个元素后把问题缩小为某个子问题。我们可以考虑与$n$分成一组的元素,在删除与$n$一组的元素后,剩下的元素还需要继续分组,且每个分组方案给出的划分都是互不相同的。因此我们可以定义一个新的函数$g$,记$g(i)$表示对长度为$i$的序列进行分组的方案数,因此可以推出递推公式:

这样时间复杂度就缩小为$O(n)$了。