题解 | #半皇后#

GH题解

对于一个$n\times nn\; \backslash times\; n$的棋盘，我们在上面放置了$kk$个半皇后(行和列互不相交)

假设我们使$kk$个棋子占据前$kk$行和前$kk$列，那么就只剩余一个$(n-k)\times (n-k)(n-k)\backslash times\; (n-k)$的棋盘

假设这个棋盘的所有格子都可以被半皇后的斜线攻击到

那么我们棋子个数的理论下界需要满足的条件就是$(n-k)\times 2-1\le k(n-k)\backslash times\; 2-1\backslash leq\; k$

即$k\ge \frac{2n-1}{3}k\; \backslash geq\; \backslash frac\{2n-1\}\{3\}$

但是你无法证明理论下界一定成立

那么我们此时就需要找出一种构造方式或用其他的方式求出实际下界

这时我们就可以先提交$easyversioneasy\backslash \; version$来判断理论下界是否就是实际下界

(自己判断当然也是可以的

构造方式需要大家自己去摸索，这里提供一种出题人的思路:

前$(k+1)\mathrm{/}2(k+1)/2$个棋子:$(i,i\times 2-1)(i,i\backslash times\; 2\; -1)$

后$k\mathrm{/}2k/2$个棋子:$(i+(k+1)\mathrm{/}2,i\times 2)(i+(k+1)/2,i\backslash times\; 2)$

这里提供一种来自验题人的更优解：

1. 我们用这k枚皇后，占据棋盘的前k行和前k列。那么剩下的 $(n-k)\times (n-k)(n\; -\; k)\; \backslash times\; (n\; -\; k)$ 大小的棋盘，其***有 $2(n-k)-12(n\; -\; k)\; -\; 1$ 条对角线需要占据。
2. 对于前 $kk$ 行和前 $kk$ 列，我们把它分成三个部分：
   1. 第一部分，前 $(n-k)(n\; -\; k)$ 行和前 $(n-k)(n\; -\; k)$ 列：我们在前 $(n-k)\times (n-k)(n\; -\; k)\; \backslash times\; (n\; -\; k)$ 的矩形区域内的右上至左下的对角线上的格子放置皇后；
   2. 第二部分，第 $(n-k+1)(n\; -\; k\; +\; 1)$ 行至第 $2(n-k)-12(n\; -\; k)\; -\; 1$ 行， 第 $(n-k+1)(n\; -\; k\; +\; 1)$ 列至第 $2(n-k)-12(n\; -\; k)\; -\; 1$ 列：类似的，我们在这部分中间的矩形区域内的右上至左下的对角线上的格子放置皇后；
   3. 第三部分，第 $2(n-k)2(n\; -\; k)$ 行至第 $kk$ 行， 第 $2(n-k)2(n\; -\; k)$ 列至第 $kk$ 列 ：在这部分对应的矩形区域内挑一条你喜欢的对角线放皇后。