CF259B题解

· · 题解

题目传送门

前置知识：幻方

幻方的定义

方的要求相对宽泛一点，每个数可以相等，大小也任意。 下面是一些基本的名词： - $n$ 阶幻方：$n \times n$ 的幻方。 - 幻和：幻方中每一行，每一列，每一条主对角线上几个数的和。 ### 幻方的性质 下面便是一个 $3$ 阶幻方： |$a_1$|$a_2$|$a_3$| | :- | :- | :- | |$a_4$|$a_5$|$a_6$| |$a_7$|$a_8$|$a_9$| 它的性质： - $a_1 + a_2 + a_3 = a_4 + a_5 + a_6 = a_7 + a_8 + a_9

这些性质，其实就是幻方最基本的性质，即：每行，每列，每条主对角线上的和都相等。下面是一些更深层次的性质。

证明：

由基本性质我们得到

a_1 + a_2 + a_3 = a_3 + a_6 + a_9 = a_3+a_5+a_7

约去 a_3，就得到了以上的式子：

a_1+a_2=a_6+a_9=a_5+a_7

类似的，还有：

等等一系列的性质。

接着，有：

下面是证明：

$(a_1+a_5+a_9)+(a_2+a_5+a_8)+(a_3+a_5+a_7)+(a_4+a_5+a_6)

即为 a_1+a_2+a_3+a_4+4a_5+a_6+a_7+a_8+a_9。

换 4 个幻和相加，得到

a_1+a_2+a_3+a_4+4a_5+a_6+a_7+a_8+a_9 = (a_1+a_2+a_3)+(a_4+a_5+a_6)+(a_7+a_8+a_9)+(a_2+a_5+a_8)

化简，得到

3a_5 = a_2+a_5+a_8

即

a_2+a_8=2a_5

由对称性可证明全式成立，得证。

接着，是这道题要用到的一个重要性质：

下面是证明：

\because a_1+a_2+a_3=a_1+a_4+a_7=a_1+a_5+a_9 \therefore a_2+a_3=a_4+a_7=a_5+a_9 \therefore a_2+a_4+a_3+a_7 = 2a_5+2a_9 \because a_3+a_7=2a_5 \therefore a_2+a_4=2a_9

得证。

同时，这个式子的其它 3 个对称式也成立：

**下面，我们可以开始分析本题了。** ## 题目讲解 ### 题意 给你一个缺掉其中一条对角线的 $3$ 阶幻方，要求补全整个幻方。 ### 分析 这下子，就要用到我们之前讲过的公式了。 - #### 如果是 $a_1$，$a_5$，$a_9$ 这条对角线没有给出数据，那么我们求出 $a_1$，$a_5$，$a_9$ 三个数的值就可以。 下面是这个 $3$ 阶幻方： |$0$|$a_2$|$a_3$| |:-|:-|:-| |$a_4$|$0$|$a_6$| |$a_7$|$a_8$|$0$| 首先 $a_5$ 由我们给出的公式 $a_2+a_8=2a_5$ 就可以推出 $a_5$ 的值； 其次 $a_1$ 和 $a_9$ 由我们给出的公式 $a_6+a_8=2a_1$ 和 $a_2+a_4=2a_9$ 就可以推出 $a_1$ 与 $a_9$ 的值。 - #### 如果是 $a_3$，$a_5$，$a_7$ 这条对角线没有给出数据，那么我们求出 $a_3$，$a_5$，$a_7$ 三个数的值就可以。 下面是这个 $3$ 阶幻方： |$a_1$|$a_2$|$0$| |:-|:-|:-| |$a_4$|$0$|$a_6$| |$0$|$a_8$|$a_9$| 首先 $a_5$ 的值与上面没有区别，还是 ${a_4+a_6} \over 2$； 其次 $a_3$ 和 $a_7$ 由我们给出的公式 $a_4+a_8=2a_3$ 和 $a_2+a_6=2a_7$ 就可以推出 $a_3$ 与 $a_7$ 的值。 那么，我们便求出了每一个数字的值，挨个输出即可。 这样，我们便可以写出本题的 AC 代码。时间复杂度 $O(1)$。 ## 代码 下面是 AC 代码：[AC 代码](https://www.luogu.com.cn/paste/xea1en7c) ```cpp #include<bits/stdc++.h> using namespace std; int main() { int a[4][4],i,j;//也可以使用一个二维数组来存储 for(i = 1;i <= 3;i++) { for(j = 1;j <= 3;j++) { cin >> a[i][j]; } } if(a[1][1] == 0) { a[1][1] = (a[2][3] + a[3][2]) / 2; a[2][2] = (a[2][1] + a[2][3]) / 2; a[3][3] = (a[1][2] + a[2][1]) / 2; } else { a[1][3] = (a[2][1] + a[3][2]) / 2; a[2][2] = (a[2][1] + a[2][3]) / 2; a[3][1] = (a[1][2] + a[2][3]) / 2; } for(i = 1;i <= 3;i++) { for(j = 1;j <= 3;j++) { cout << a[i][j] << " "; } cout << endl; } return 0; } ```