Topcoder练习

Published: April 11, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• SRM782 PaintItBlack
• SRM783 CardboardBoxes
• SRM763 ProductAndProduct
• SRM761 SortArray
• SRM784 SpeedingUpBozosort
• SRM785 TAASquares

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^2+xy+xz+yz=\frac{S}{2}$$

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

$$(x+y)(x+z)=\frac{S}{2}$$

由于$(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$代替可以得出：

$$\left\{ \begin{array}{ccc} x &\geq &1\\ -2x+a&\geq& 0\\ -x+\frac{S}{2a} &\geq& 0 \end{array} \right.$$

最后可以得出$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)$。

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

$$E[\prod_{i=1}^n(c_i+x_i)]=E[\sum_{U\subseteq N}(\prod_{i\notin U}c_i)(\prod_{i\in U}x_i)]\\ =\sum_{U\subseteq N}(\prod_{i\notin U}c_i)E[\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}]$，可以代入替换为：

$$\sum_{U\subseteq N}(\prod_{i\notin U}c_i)E[\prod_{i\in U}x_i]=\sum_{k=0}^nf(n-k)E[\prod_{i=1}^kx_i]$$

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

$$E[\prod_{i=1}^kx_i]=\frac{n+m-1\choose n+k-1}{n+m-1\choose n-1}$$

最后得出的公式为：

$$\sum_{k=0}^nf(n-k)\frac{n+m-1\choose n+k-1}{n+m-1\choose n-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$，要求所有列和和行和的集合最大（即有最多不同的列和和行和）。

题解

答案是：

$$\left[ \begin{array}{cccc} 1 & 2 & 2 & 2\\ 0 & 1 & 2 & 2\\ 0 & 0 & 0 & 2\\ 0 & 0 & 0 & 0 \end{array} \right]$$

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

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

$$\left[ \begin{array}{ccccc} 1 & 2 & 2 & 2 & 2\\ 0 & 1 & 2 & 2 & 2\\ 0 & 0 & 0 & 2 & 2\\ 0 & 0 & 0 & 0 & 2\\ 0 & 0 & 0 & 0 & 0 \end{array} \right]$$

可以发现除了第三行和第三列的总和相同以外，其余行列都不同。因此这个构造算法给出的不同总和数为$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)$次好操作，其余位置好操作和坏操作抵消。

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

$$4r(n-r)\leq n^2$$

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