题目大意
考虑一个 $x\times y$ 的矩阵 $A_{x\times y}$ ,$A_{i,j} = (i-1)x+y$ 。
从矩阵中的某个位置出发,每次可向上下左右移动一步,每到一个位置,记录下此位置上的数,如此可得到一个序列。 现给定序列 $a_1, a_2, \dots, a_n$,判断是否存在 $x,y$ 使得在 $A_{x,y}$ 中移动能得到此序列。解法
考察 $|a_{i+1} - a_{i}|$,显然有 $|a_{i+1} - a_i| = 1$ 或 $|a_{i+1} - a_i| = y $ 。
所以若 $\exists i\ |a_{i+1} - a_{i}| \ne 1$,则 $y= |a_{i+1} - a_{i}|$ 。若按上述必要条件检查不出矛盾,且可确定 $y\ne 1$,则我们可以确定序列中每个数在矩阵 $A$ 中位置。此时还需进一步检查
序列中相邻且差的绝对值为 $1$ 的两个数是否在同一行。
若不存在 $|a_{i+1} - a_{i}| \ne 1$ 的情况,则取 $y=1$ 即可,无需进一步检查。
我的代码赛后被 Hack 了。我当时想到的是, $y\ne 1$ 确定以后,还需要检查处在同一行的数不超过 $y$ 个。
我判断的方法是:检查应在同一行的连续若干个数的最大值和最小值之差是否大于 $y$ 。 这个想法是有 bug 的。我当时没有认识到
$y$ 确定以后,每个数所在的行列就确定了。
这是 key observation 。