Gcj练习

Published: by Creative Commons Licence

  • Tags:

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$。现在我们将已经出现过的数值,全部加入到矩阵中。如果是前者,则结果为:

如果是后者,则结果是:

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