$n=2^k$
当$n=2^k(k\in\lbrace 1, 2, 3\cdots,n\rbrace)$,$(n-1)$天比赛完,如下表当n=2时,我们在$2^{k-1}$行,$2^{k-1}$列处将表分割为四块,我们很容易看出,在一个最小块$(k=1)$中,只需将对角数值复制即可。然后将填完的块复制到对角的块,所以直接采用分治法解决问题。
例表
$\Rightarrow$ $n=2^k$
代码
1 | /** |
$n\in\lbrace 1,\cdots,n\rbrace$
奇数时用$n$天,偶数时用$(n-1)$天
奇数时采用轮空规则,增加虚拟对手。
填写规则:
$\Rightarrow$当$n\%2=1$时:
$\rightarrow$ 从左上角1开始,往右下角对角处填1
$\rightarrow$ 在从1右边的2开始往右下角填写2,若数字相等(对手是自己)则轮空,填写0
$\rightarrow$ 若填到末尾列,但未填写末尾行时,将列转移到第一列的相同行继续往右下角填写
$\Rightarrow$当$n\%2=0$时:
$\rightarrow$ 和奇数填写规则一样,最后一行有BUG,但是不影响,我们可以先按规则填完,然后根据列来修正最后一行
例表一
$\Rightarrow$ $n\%2=1$
例表二
$\Rightarrow$ $n\%2=0$
代码
1 | /** |
无论奇偶都用$(n-1)$天
奇数时不轮空,不增加虚拟对手
填写规则:
$\rightarrow$ 以第一列为准,往右上角填写相同的数
$\rightarrow$ 若填到第一行,但未填写到末尾列时,将数字复制到末尾行的相同列继续往右上角填写
例表一
$\Rightarrow$ $n\%2=1$
例表二
$\Rightarrow$ $n\%2=0$
代码
1 | /** |
时间复杂度
我们只需要将二维数组填满即可,三种方法的时间复杂度都为