「棋盘放置」题解

问题分析

有一个 $n \times m$ 的棋盘，需要在格子中放置棋子，满足：

1. 第 $i$ 列恰好有 $a_i$ 个棋子
2. 任意两个棋子不能边相邻（即不能有公共边）

需要判断是否存在合法方案，并构造一个方案。

关键限制：

• 列约束：每列棋子数量固定
• 相邻约束：棋子不能有公共边（四连通相邻）

问题转化

1. 相邻约束的影响

由于棋子不能边相邻，这意味着：

• 每个棋子最多与4个格子相邻（上、下、左、右）
• 如果某个格子放置了棋子，那么它的四个邻居都不能放置棋子

这可以看作是一个图着色问题：棋盘构成一个网格图，需要选择一些顶点（放置棋子），使得没有两个被选中的顶点相邻。

2. 二分图性质

棋盘网格图是一个二分图：可以按照 $(i+j)$ 的奇偶性将格子分为两类（国际象棋棋盘染色）：

• 黑色格子：$(i+j)$ 为偶数的格子
• 白色格子：$(i+j)$ 为奇数的格子

在二分图中，相邻的格子必然属于不同颜色类。

重要观察：如果只在一个颜色类中放置棋子，那么任意两个棋子都不会相邻（因为它们没有公共边）。

3. 列约束的可行性

假设我们只在黑色格子中放置棋子，那么：

• 每列最多能放置的棋子数取决于该列黑色格子的数量
• 对于第 $j$ 列，黑色格子数为 $\lceil n/2 \rceil$（如果第一行是黑色）或 $\lfloor n/2 \rfloor$（如果第一行是白色）

具体来说：

• 如果第一行第1列是黑色，那么黑色格子的行号奇偶性：第 $j$ 列的黑色行号与 $j$ 的奇偶性相同
• 设 $black(j)$ 表示第 $j$ 列黑色格子的数量

必要条件：对于所有 $j$，$a_j \leq black(j)$

类似地，如果只使用白色格子，也需要 $a_j \leq white(j)$，其中 $white(j) = n - black(j)$。

算法思路

1. 判断可行性

定理：存在合法方案当且仅当存在一种颜色选择（全部使用黑色或全部使用白色），使得对于所有 $j$，$a_j$ 不超过该列该颜色的格子数，并且总棋子数不超过该颜色的总格子数。

更精确地说：设 $B$ 为黑色格子总数，$W$ 为白色格子总数。 设 $black(j)$ 为第 $j$ 列黑色格子数，$white(j)$ 为第 $j$ 列白色格子数。

我们需要检查是否存在方案满足：

1. 对于所有 $j$，$a_j \leq black(j)$ 或对于所有 $j$，$a_j \leq white(j)$
2. $\sum a_j \leq B$（如果使用黑色）或 $\sum a_j \leq W$（如果使用白色）

但实际上，条件1已经隐含了条件2：如果 $a_j \leq black(j)$ 对所有 $j$ 成立，那么 $\sum a_j \leq \sum black(j) = B$。

简化：只需要检查两种可能性：

• 方案A：全部使用黑色格子，检查是否对所有 $j$，$a_j \leq black(j)$
• 方案B：全部使用白色格子，检查是否对所有 $j$，$a_j \leq white(j)$

如果两者都不满足，则无解。

2. 黑色/白色格子数的计算

对于第 $j$ 列（1-indexed）：

• 如果使用黑色格子：
  • 当 $j$ 为奇数时：黑色行号为 $1,3,5,\dots$，共 $\lceil n/2 \rceil$ 个
  • 当 $j$ 为偶数时：黑色行号为 $2,4,6,\dots$，共 $\lfloor n/2 \rfloor$ 个
• 如果使用白色格子：
  • $white(j) = n - black(j)$

所以：

• $black(j) = \lceil n/2 \rceil$ 如果 $j$ 为奇数且第一行是黑色（即 $(1,1)$ 是黑色）
• $black(j) = \lfloor n/2 \rfloor$ 如果 $j$ 为偶数且第一行是黑色

实际上，我们有两种染色方式：

1. $(1,1)$ 为黑色
2. $(1,1)$ 为白色

3. 构造方案

如果存在可行方案，我们需要构造一个具体的放置。

贪心构造： 假设我们选择使用黑色格子（白色格子类似）：

1. 初始化一个 $n \times m$ 的棋盘，全部填 0
2. 对于每一列 $j = 1$ 到 $m$：
   • 统计该列黑色格子的行号
   • 选择前 $a_j$ 个黑色格子放置棋子
   • 标记这些位置为 1

这样构造的方案：

• 满足列约束：每列恰好 $a_j$ 个棋子
• 满足相邻约束：所有棋子都在黑色格子上，而黑色格子之间不相邻

详细算法步骤

步骤1：判断可行性

1. 计算两种染色方案下的列容量：

   方案1：$(1,1)$ 为黑色

   • 对于 $j=1$ 到 $m$：
     • 如果 $j$ 为奇数：$cap1_j = \lceil n/2 \rceil$
     • 如果 $j$ 为偶数：$cap1_j = \lfloor n/2 \rfloor$

   方案2：$(1,1)$ 为白色

   • 对于 $j=1$ 到 $m$：
     • 如果 $j$ 为奇数：$cap2_j = \lfloor n/2 \rfloor$
     • 如果 $j$ 为偶数：$cap2_j = \lceil n/2 \rceil$

2. 检查：

   • 如果对所有 $j$，$a_j \leq cap1_j$，则选择方案1（使用黑色格子）
   • 否则如果对所有 $j$，$a_j \leq cap2_j$，则选择方案2（使用白色格子）
   • 否则，输出 No

步骤2：构造方案

假设选择方案1（使用黑色格子）：

1. 创建 $n \times m$ 的矩阵 $board$，初始全为 0
2. 对于每列 $j = 1$ 到 $m$：
   • 确定该列哪些行是黑色：
     • 如果 $j$ 为奇数：黑色行号为 $1,3,5,\dots$
     • 如果 $j$ 为偶数：黑色行号为 $2,4,6,\dots$
   • 在这些黑色行中，选择前 $a_j$ 个放置棋子
   • 将对应的 $board[i][j]$ 设为 1
3. 输出方案

如果选择方案2（使用白色格子），类似处理，只是黑色行号变成白色行号。

正确性证明

1. 必要性证明

如果存在合法方案，考虑方案中所有棋子所在的格子。 由于棋子不能相邻，它们构成一个独立集。 在二分图中，最大独立集要么包含所有黑色节点，要么包含所有白色节点（不完全是，但我们可以调整）。

实际上，我们可以将方案转化为只使用一种颜色的方案：

• 如果方案中同时使用了黑色和白色格子，我们可以将所有白色格子上的棋子移动到相邻的黑色格子上（如果有空的话）
• 但这样可能会破坏列约束

更严谨的证明：对于合法方案，考虑每一行。由于棋子不能相邻，每行中棋子之间至少隔一个空格。 因此，对于第 $j$ 列，最多能放置的棋子数受到该列可用位置的限制。

2. 充分性证明

如果满足条件 $a_j \leq black(j)$ 对所有 $j$ 成立，那么我们的构造方案：

• 每列放置 $a_j$ 个棋子在黑色格子上
• 由于所有棋子都在黑色格子上，而黑色格子之间没有公共边，所以满足相邻约束

因此构造的方案是合法的。

复杂度分析

• 可行性检查：$O(m)$
• 构造方案：$O(nm)$
• 总复杂度：$O(nm)$，对于 $n,m \leq 300$，完全可行。

特殊情况处理

1. $n=1$ 的情况

当 $n=1$ 时，棋盘只有一行。 相邻约束意味着不能有两个相邻的棋子。 因此，如果存在 $a_j > 1$，则无解。 实际上，对于单行棋盘，黑色/白色格子的概念：每个格子交替为黑色和白色。 最多只能每隔一个格子放一个棋子。

2. $m=1$ 的情况

当 $m=1$ 时，只有一列。 相邻约束意味着不能有两个棋子在同一列中相邻（上下相邻）。 因此，最多只能放 $\lceil n/2 \rceil$ 个棋子（如果使用黑色格子）。

3. $a_j=0$ 的情况

某些列可能不需要放置棋子，这不会造成问题。

示例验证

样例1：$n=3, m=4, a=[2,1,2,1]$

计算方案1（$(1,1)$为黑色）：

• 第1列（奇）：$cap1_1 = \lceil 3/2 \rceil = 2$，$a_1=2 \leq 2$ ✓
• 第2列（偶）：$cap1_2 = \lfloor 3/2 \rfloor = 1$，$a_2=1 \leq 1$ ✓
• 第3列（奇）：$cap1_3 = 2$，$a_3=2 \leq 2$ ✓
• 第4列（偶）：$cap1_4 = 1$，$a_4=1 \leq 1$ ✓

满足条件，使用方案1。

构造：

• 第1列：黑色行号 1,3，放2个棋子 → 行1,3放棋子
• 第2列：黑色行号 2，放1个棋子 → 行2放棋子
• 第3列：黑色行号 1,3，放2个棋子 → 行1,3放棋子
• 第4列：黑色行号 2，放1个棋子 → 行2放棋子

得到：

1010
0101
1010

与样例一致。

样例2：$n=3, m=4, a=[2,3,3,3]$

检查方案1：

• 第2列：$cap1_2 = 1$，但 $a_2=3 > 1$，不满足

检查方案2：

• 第1列：$cap2_1 = \lfloor 3/2 \rfloor = 1$，但 $a_1=2 > 1$，不满足

无解，输出 No。

总结

本题的关键洞察是将棋盘看作二分图，并利用独立集的性质：

1. 棋子不能相邻 → 棋子构成独立集
2. 在二分图中，可以只使用一种颜色的节点作为独立集
3. 列约束转化为每列该颜色节点数量的限制