(未完成的)NFLSPC #1 G题 Encryption 题解

2018-12-11 21:58:33 By TRCYX

这题是 @fizzydavid 去年出的,不过去年不会造通讯题,所以就咕了一年。

题面中没有给样例,似乎影响了一些人做题,我们之前都没有发现,在这里给大家道歉。样例现已补上。

子任务 1

直接输出原矩阵即可。

在接下来的子任务里,我们需要在不丢失原矩阵信息的基础上(最简单的方法就是不改变原矩阵),在矩阵上增加两行两列,这两行两列需要包含一些标志,使得经过中间的变换后,解密程序能够通过找到这些标记,从而知道如何还原原矩阵。

子任务 2

两种翻转是独立的,而每种翻转进行两次之后就会和不做任何改变一样,所以事实上只有 $2 \times 2 = 4$ 种不同的变换结果,可以参考下图(虽然图中是以旋转作为基本操作的,但结果相同):

四种不同变换结果

我们先考虑上下翻转。因为矩阵可能被翻转也可能不被翻转,我们对矩阵做一些有方向性的标志。因为可以增加两行,我们可以在整个矩阵上方加上一行 $1$,整个矩阵下方加上一行 $0$: $$ \begin{array}{ccccc} \color{red}1 & \color{red}1 & \color{red}1 & \color{red}\cdots & \color{red}1 \\ a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} \\ \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}\cdots & \color{blue}0 \end{array} $$ 这样,解密程序可以根据收到的矩阵最上面一行任意位置是 $1$ 还是 $0$ 决定是否要上下翻转矩阵。

对于左右翻转也是差不多的。我们可以在之前的基础上,在矩阵左侧加上一列 $1$,整个矩阵右侧加上一列 $0$: $$ \begin{array}{ccccccc} \color{orange}? & 1 & 1 & 1 & \cdots & 1 & \color{orange}? \\ \color{red}1 & a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} & \color{blue}0 \\ \color{red}1 & a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} & \color{blue}0 \\ \color{red}1 & a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} & \color{blue}0 \\ \color{red}\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \color{blue}\vdots \\ \color{red}1 & a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} & \color{blue}0 \\ \color{orange}? & 0 & 0 & 0 & \cdots & 0 & \color{orange}? \end{array} $$ 这样,解密程序可以根据收到的矩阵最左边一列(中间)任意位置是 $1$ 还是 $0$ 决定是否要左右翻转矩阵。

四个角落之所以打问号,是因为在这个方案中,角落写什么是无关紧要的,只要我们从第一行中间、第一列中间读取值就好了。这个做法的程序可以参见 提交 #12011

当然也可以有其他做法,如: $$ \begin{array}{ccccccc} \color{red}1 & \color{orange}? & \color{orange}? & \color{orange}? & \color{orange}\cdots & \color{orange}? & \color{blue}0 \\ \color{orange}? & a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} & \color{orange}? \\ \color{orange}? & a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} & \color{orange}? \\ \color{orange}? & a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} & \color{orange}? \\ \color{orange}\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \color{orange}\vdots \\ \color{orange}? & a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} & \color{orange}? \\ \color{blue}0 & \color{orange}? & \color{orange}? & \color{orange}? & \color{orange}\cdots & \color{orange}? & \color{blue}0 \end{array} $$ 可以根据角落的 $1$ 被翻到了什么位置知道是否被上下 / 左右翻转。

子任务 3

考虑增加的旋转 $90^\circ$ 这个操作。进行两次旋转的结果和进行一次上下翻转和一次左右翻转的结果是一样的。事实上,增加这种操作以后一共只有 $8$ 种不同的变换结果,即在原来的四种

四种不同变换结果

的基础上增加了

另外四种变换结果

观察之前的做法,例如在角落放一个 $1$ 和三个 $0$ 的做法,我们会发现后四种结果中 $1$ 最后的位置和前四种会一一对应,但是对应的两种结果中,有某种顺时针和逆时针的差异。我们可以通过增加一个顺时针逆时针看起来不同的标记,确定这个方向: $$ \begin{array}{ccccccc} \color{red}1 & \color{red}1 & \color{orange}? & \color{orange}? & \color{orange}\cdots & \color{orange}? & \color{blue}0 \\ \color{blue}0 & a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} & \color{orange}? \\ \color{orange}? & a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} & \color{orange}? \\ \color{orange}? & a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} & \color{orange}? \\ \color{orange}\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \color{orange}\vdots \\ \color{orange}? & a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} & \color{orange}? \\ \color{blue}0 & \color{orange}? & \color{orange}? & \color{orange}? & \color{orange}\cdots & \color{orange}? & \color{blue}0 \end{array} $$

解密程序可以先找到角落的 $1$,从而确定哪一个角落是原矩阵的左上角;再根据这个 $1$ 旁边的 $1$,确定哪个方向是原矩阵的列上的正方向(即 $a_{0, 0}$ 到 $a_{0, 1}$ 的方向),这样一来就可以还原原矩阵。这个做法的程序可以参见 提交 #12107

子任务 4

由于有了行列轮换,原先角落的位置不一定会保持在角落,所以子任务 3 的做法就无效了。由于不需要考虑翻转,所以我们只需要找到变换后的矩阵中原矩阵左上角的位置,就可以复原原矩阵,即变换后的矩阵一定类似于 $$ \begin{array}{ccc} \begin{array}{ccccc} \color{red}{a_{0, 0}} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} \end{array} & \Longrightarrow & \begin{array}{ccccccc} a_{p, q} & a_{p, q + 1} & \cdots & a_{p, m - 1} & a_{p, 0} & \cdots & a_{p, q - 1} \\ a_{p + 1, q} & a_{p + 1, q + 1} & \cdots & a_{p + 1, m - 1} & a_{p + 1, 0} & \cdots & a_{p + 1, q - 1} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{n - 1, q} & a_{n - 1, q + 1} & \cdots & a_{n - 1, m - 1} & a_{n - 1, 0} & \cdots & a_{n - 1, q - 1} \\ a_{0, q} & a_{0, q + 1} & \cdots & a_{0, m - 1} & \color{red}{a_{0, 0}} & \cdots & a_{0, q - 1} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{p - 1, q} & a_{p - 1, q + 1} & \cdots & a_{p - 1, m - 1} & a_{p - 1, 0} & \cdots & a_{p - 1, q - 1} \end{array} \end{array} $$

和之前一样,我们可以分行和列两个方向来考虑这个问题。例如要找出原矩阵的最上方在变换后的矩阵中是第几行,我们会希望让第一行有和其他行不一样的特征。例如,全部为 $1$;但是输入的矩阵也可以有某一行全部为 $1$,所以我们需要借助增加的列。这样一来,我们就可以让加密程序输出的矩阵有且只有一行全部为 $1$: $$ \begin{array}{ccccccc} \color{red}1 & \color{red}1 & \color{red}1 & \color{red}\cdots & \color{red}1 & \color{red}1 \\ a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} & \color{blue}0 \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} & \color{blue}0 \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} & \color{blue}0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \color{blue}\vdots \\ a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} & \color{blue}0 \\ \end{array} $$ 现在再来考虑列。我们也可以让唯一一列全部为 $1$,当然这也需要借助增加的行。我们只要保证增加的行不全为 $1$,且第一行仍全为 $1$,就可以不打乱之前对行的处理: $$ \begin{array}{ccccccc} \color{red}1 & 1 & 1 & 1 & \cdots & 1 & 1 \\ \color{red}1 & a_{0, 0} & a_{0, 1} & a_{0, 2} & \cdots & a_{0, m - 1} & 0 \\ \color{red}1 & a_{1, 0} & a_{1, 1} & a_{1, 2} & \cdots & a_{1, m - 1} & 0 \\ \color{red}1 & a_{2, 0} & a_{2, 1} & a_{2, 2} & \cdots & a_{2, m - 1} & 0 \\ \color{red}\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \color{red}1 & a_{n - 1, 0} & a_{n - 1, 1} & a_{n - 1, 2} & \cdots & a_{n - 1, m - 1} & 0 \\ \color{red}1 & \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}\cdots & \color{blue}0 & \color{blue}0 \end{array} $$ 这样,变换后的矩阵一定只有一行一列为 $1$,通过找到这样的一行一列,就可以确定原矩阵左上角的位置(事实上这个方案和子任务 2 的第一个方案很像)。这个做法的程序参见 提交 #12109

子任务 5、6

先咕着。简单思想是用异或和完成有方向的标记。(事实上,子任务 5 可能不用异或和也可以完成。)

我的一个 $(n + 1) \times (m + 1)$ 的做法可参见 提交 #9639,不过要求 $n \geq 6, m \geq 5$;我非常相信有(很恶心)的做法可以把所有大小的矩阵都用不超过 $(n + 1) \times (m + 1)$ 的矩阵编码。

@fizzydavid 的正解参见 提交 #9638

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。