Gcj练习

Published: April 05, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• Qualification Round 2020 Indicium

Qualification Round 2020 Indicium

题意

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209aa0

翻译

给定$n$和$k$，要求生成一个大小为$n$的拉丁方，且其对角线元素之和为$k$，如果不存在则报告，否则输出一个满足条件的拉丁方。

题解

以前没做过这样的题，这里记录一下。首先如果矩阵的大小不超过$3$，我们可以直接暴力枚举。否则将对角线元素设置为$1,\ldots,1,x,n,\ldots, n$的形式，这里$1\leq x\leq n$。

很显然如果如果对角线中有两种数值，且其中一种数值出现的次数为1的时候，是无解的。如果对象线的元素为$1\ldots,1,2$或者$n-1,n,\ldots,n$，那么是修正的，故一定无解。否则我们可以对其进行修正，具体方法非常简单，如果对角线形式为$1,\ldots,1,x$的，我们可以将其修正为$1,\ldots,1,2,x-1$，否则对角线形式为$x,n,\ldots,n$，我们可以将其修正为$x+1,n-1,n,\ldots,n$。

如果对角线元素全部相同，那么可以不必考虑接下来的这一步。否则对角线至少包含一种以上元素，对角线的形式应该为$a,\ldots,a,c,\ldots, c$或$a,\ldots,a,b,c,\ldots,c$。现在我们将已经出现过的数值，全部加入到矩阵中。如果是前者，则结果为：

$$\left( \begin{array}{cccccc} a&c\\ &a&c\\ c&&a\\ &&&c&&a\\ &&&a&c\\ &&&&a&c \end{array} \right)$$

如果是后者，则结果是：

$$\left( \begin{array}{cccccc} a&c&b\\ b&a&c\\ &b&a&c\\ c&&&b&&&a\\ &&&a&c&b&\\ &&&&a&c&b\\ &&&&b&a&c \end{array} \right)$$

利用这种方式，我们可以得到前几个颜色的置换。接下来我们可以不断将其它数值放进去，这实际上可以转换为二分图匹配问题进行解决，且霍尔定理保证了完美匹配的存在性。具体细节可以参见我的《匹配算法》中的霍尔定理的题目4.