Topcoder练习

Published: by Creative Commons Licence

  • Tags:

SRM782 PaintItBlack

翻译

给定一个拥有$n$个顶点$m$条边的无向连通图。你现在位于顶点$1$。所有顶点的颜色初始时都是白色,当你沿着边$(u,v)$从$u$移动另外一个顶点$v$的时候,$v$的颜色会改变(从黑色变成白色,或从白色变成黑色)。现在要求找出一条从顶点$1$出发最后回到顶点$1$的回路(回路中同一条边可以走多次),要求回路的长度不超过$5n$,且沿着这条回路移动后,最终所有顶点的颜色都变成了黑色。输出这样一条回路或者报告无解。

题解

挺不错的题目。

问题实际上要求找到一条回路。如果仅考虑回路中的单向边,每个顶点的入度都是奇数,且回路是欧拉回路,有向图欧拉回路有解当且仅当每个顶点入度和出度相同,且图连通。

由于是无向图,那么我们可以沿着某条路径$P$从$1$移动到$x$,之后在原路返回到$1$。这样也是一条回路,注意到走过这样一条路径后,除了$1$和$x$的颜色改变,其余顶点的颜色都保持不变。同时由于图是连通的,因此我们可以利用这种方法,对于任意顶点$2\leq i\leq n$,都找到一条从$1$到$i$的路径,并原路返回,这样除了$1$外其余所有顶点的颜色都变成了黑色,且这样移动还能得到一条回路。

现在我们来讨论$1$的最终颜色,由于$1$的入度最终为$n-1$,因此如果$n$是偶数,那么$1$最终是黑色。这样就大功告成了。

现在来讨论$n$是奇数的情况。我们发现其实之所以$n$是奇数的情况下上面的策略$1$一定是白色,因为没走一趟,都有偶数个顶点的颜色变更,因此无论走多少趟,至少会有一个顶点的颜色保持白色。但是如果此时如果图中有长度为奇数的简单环,那么我们可以通过走这条环改变图中白色顶点数目的奇偶性,这样就有解了。

下面我们证明在其余情况下,一定无解。所谓的其余情况实际上就是$n$是奇数且没有奇数环,这时候我们会得到一个顶点数为奇数的二分图$(L,R)$,其中$1 \in L$,我们发现回路的终点一定在$L$,但是回到$L$集合的时候,路径的长度一定为偶数,换句话说,只有偶数个顶点的颜色变更,而$n$奇数,因此不可能所有顶点同时颜色为黑色。

至于题目要求回路长度不超过$5n$,我们可以生成任意一颗生成树,之后我们假如我们考虑连接父亲$f$和孩子$c$边$(f,c)$,注意到我们会通过$(f,c)$从$f$到$c$的次数和从$c$到$f$次数是一样的,对于$c$子树内的每个顶点$v$,从$f$到$v$都要经过一次$(f,c)$,因此经过$(f,c)$从$f$到$c$的次数等于$size(c)$。但是如果$size(c)>2$,那么说明我们从$f$到$c$和从$c$到$f$的次数超过了$2$,我们可以各减去$2$,这样不会改变任何顶点入度的奇偶性,且每个顶点的入度和出度一致,且不破坏连通性。因此每条树边的每个方向都最多在回路出现两次,这里总共有$4n-4$条边。之后可能还需要加入一条奇数长度的简单环,长度最多为$n$,因此我们要找的回路长度最多为$5n-4$,是满足条件的。

算法的过程,我们可以先将最终会出现在回路中的有向边提取,之后在找欧拉回路,可以用Hierholzer算法解决。

SRM783 CardboardBoxes

翻译

要求求公式$2(x^2+xy+xz+yz)=S$的正整数解数目,其中$S$是给定整数,$x,y,z$是要赋值的未知数,且$y\geq x$,$S\leq 10^{15}$

题解

首先有解的前提是$S$是偶数,我们将公式先进行化简:

之后最重要的就是左部公式可以化简:

由于$(x+y)|\frac{S}{2}$。因此我们可以枚举所有$\frac{S}{2}$的因子。考虑$x+y=a$,那么$x+z=\frac{S}{2a}$。

这时候还有三个约束条件,一个是$y\geq x$,另外一个是$x\geq 1$,最后还有$z\geq 1$。将$y$和$x$都用$x$代替可以得出:

最后可以得出$x$的取值范围。

SRM763 ProductAndProduct

翻译

给定$n$个盒子,第$i$个盒子中有$c_i$个大理石。现在还有额外的$m$个大理石,要求这些大理石独立等概率放入到某个盒子中。记第$i$个盒子最终放入$x_i$大理石,要求计算$\prod_{i=1}^n(c_i+x_i)$的期望值。

题解

记$N={1,\ldots,n}$

我们先将$\prod_{i=1}^n(c_i+x_i)$拆分开来,其等价于$\sum_{U\subseteq N}(\prod_{i\notin U}c_i)(\prod_{i\in U}x_i)$。

我们套入期望公式可以得到:

记$f(i)=\sum_{U\subseteq N\land |U|=i}\prod_{j\in U}c_i$。即所有大小为$i$的${c_1,\ldots,c_n}$的子集的乘积和。我们可以用生成函数+多项式卷积$O(n(\log_2n)^2)$时间复杂度预处理这些内容。

同时可以发现,每个盒子仅有指标不同,因此$E[\prod_{i\in U}x_i]=E[\prod_{i=1}^{|U|x_i}]$,可以代入替换为:

$E[\prod_{i=1}^kx_i]$可以解释为所有方案下前$k$个元素的乘积和除上总方案数。所有方案下前$k$个元素的乘积和这个问题可以通过隔板法解决,具体可以参见我的另外一篇博客《组合数学》中隔板法一节中的题目1。可以简化为:

最后得出的公式为:

SRM761 SortArray

翻译

给定长度$n$和$m$个命令,判断是否对于所有长度为$n$的序列,执行上述$m$个命令后都能得到有序序列。命令从前往后执行,每个命令指定若干个位置,将这些位置的数从小到大进行重排。其中$n\leq 15$,$m\leq 100$。

题解

我们不能枚举所有的$n$种排列,因为数量级太大。但是我们可以这样玩,我们考虑一个长度为$n$的01序列,其中部分为1,部分为0。如果命令能保证对所有长度为$n$的序列正确排序,那么自然也能对我们的$01$序列进行排序。

现在我们断定如果所有可能的长度为$n$的二进制序列经过排序后都是有序的,那么一定能正确排序所有的长度为$n$的序列。用反证法,假设存在一个序列$a$不能被正确排序,那么考虑在对$a$应用$m$个命令后得到的新序列为$b$,考虑最小的数$x$,满足存在某个更小的数在$b$中排在$x$后面。接下来,我们将$a$中所有大于等于$x$的数改写为$1$,而所有小于$x$的数改写为$0$,那么经过$m$个命令后,得到的新序列实际上是将$b$中所有大于等于$x$的数改成$1$,而其余数改写为$0$,这样我们就发现一个长度为$n$的二进制序列不能被正确排序,这与前提相悖。

用这种方式做校验,时间复杂度为$O(mn2^n)$。

SRM784 SpeedingUpBozosort

翻译

题解

首先置换最多为$m=6!=720$,因此可以用马尔可夫矩阵$O(m^3)$求期望。

但是问题来了,由于我们随机操作会进行$k=1000$次,如何计算每个置换在1000次随机操作后变成各种其它置换的概率呢。这个可以想到用DP的方式,记$dp(i,j)$表示相同置换(123456)在$i$次随机操作后变成置换$j$的概率。对相同置换求结果概率的时间复杂度为$O(mn^2k)$。这里也就出现了一个难点,怎么计算所有$m$种置换在$k$此操作后的概率呢?如果暴力计算,则时间复杂度为$O(m^2n^2k)$,肯定过不了,但是我们发现置换之间的区别仅在于标号,如果我们将$dp$中用到的所有标号进行替换,就会发现$O(m^2n)$即可得到其余所有矩阵的DP方程。

最后我们要做的就是套上马尔可夫矩阵,求出结果即可。

SRM785 TAASquares

翻译

要求找出一个$n\times n$的矩阵,每个单元都只能为$0,1,2$,要求所有列和和行和的集合最大(即有最多不同的列和和行和)。

题解

答案是:

可以发现上两行和与左两列和拥有相同的奇偶性,且值不同,同理下两行和与右两列和奇偶性不同,但是值不同,因此每行每列都拥有不同的和。

上面这个答案对$n$是偶数的情况下,不同总和为$2n$,正确性是显然的,现在考虑奇数$n$。

可以发现除了第三行和第三列的总和相同以外,其余行列都不同。因此这个构造算法给出的不同总和数为$2n-1$。但是这是正确的吗。我们可以证明当$n$是奇数的时候,所有行列和不可能都不相同。

先考虑将矩阵全部用1填充。现在我们要修改矩阵使得每行每列和都不同。我们对每行每列单独考虑修改次数,考虑到和为$n$的只能出现一次,因此其总有效修改次数至少为0,同理$n-1$和$n+1$也都各只能出现一次,因此这两个行列的总修改次数至少为2。对于$n-2$和$n+2$同理。因此我们推出对于所有行列总的修改次数至少为$0+1+1+2+2+\ldots +(n-1)+(n-1)+n=n^2$。

接下来我们假设已经得到了一个$n\times n$的矩阵,且每行每列的和都不同。我们将所有行按行和进行排序,同时将所有列按列和进行排序。这时候我们应该恰好有$n$个数大于$n$或大于等于$n$。这里不失一般性我们假设为前者,假设后$r$行和后$n-r$列满足条件。现在我们来定义好坏操作,如果在前$n-r$行或前$r$列做减少操作则为好操作,在后$r$行后后$n-r$列做增加操作则为好操作。我们由上一段知道$#好操作-#坏操作\geq n^2$。考虑如果在前$n-r$行$r$列最多做$2r(n-r)$次好操作,而在后$r$行$n-r$最多做$2r(n-r)$次好操作,其余位置好操作和坏操作抵消。

因此我们能做的好操作的上限次数为

这里等号取到的条件是$r=\frac{n}{2}$。我们知道当$n$为奇数的时候是取不到的,因此当$n$是奇数时,我们不能让所有行列都不同。