「棋盘攻击」题解

题意简化

• $n \times n$ 棋盘，有空位和障碍
• 两个棋子能互相攻击当且仅当：
  1. 在同一行或同一列
  2. 它们之间没有障碍（包括端点之间所有格子）
• 有 $q$ 个询问，每次问：放 $k$ 个棋子时，最少能有多少对互相攻击的棋子？

$n \leq 50$，$q \leq 10000$。

核心观察

1. 攻击条件分析

如果两个棋子在同一行且中间无障碍，那么它们所在的行连通段内任意两个棋子都会互相攻击。

列同理。

2. 转化为图论问题

• 每个行连通段（一行中连续的空位段）是一个团：这段内任意两个棋子都互相攻击
• 每个列连通段也是一个团
• 但行和列有重叠：一个棋子同时属于一个行连通段和一个列连通段

这形成一个二分图冲突模型：

• 左部：所有行连通段
• 右部：所有列连通段
• 一个棋子对应一条边：连接它所在的行连通段和列连通段

3. 关键结论

最少攻击对数 ⇔ 最多能避免的攻击对数

每个棋子：

• 在其行段内：与段内其他棋子都互相攻击
• 在其列段内：与段内其他棋子都互相攻击

如果我们在某个行段放 $t$ 个棋子，它们会形成 $C(t,2)$ 对互相攻击。 但注意：这些攻击对会被行和列重复计算吗？不会，因为攻击对要么由行决定，要么由列决定。

实际上，问题转化为：

• 选择一些边（棋子）
• 每条边连接一个左节点（行段）和一个右节点（列段）
• 目标是：对于给定的边数 $k$，最小化 $\sum$（左节点度数选择的二元组数）+ $\sum$（右节点度数选择的二元组数）

解法：费用流/动态规划

方法一：费用流建模

1. 建图：

   • 源点 → 每个行段：容量无限，费用为 0
   • 每个行段 → 汇点：容量无限，但通过拆点技巧：增加流量的边际费用递增
   • 每个列段同理
   • 行段 ↔ 列段：根据棋盘空位连接

2. 费用计算：

   • 在一个行段中放 $t$ 个棋子，攻击对数为 $C(t,2) = t(t-1)/2$
   • 从 $t$ 增加到 $t+1$，新增攻击对数：$C(t+1,2)-C(t,2) = t$
   • 所以边际费用递增：第 $t$ 个棋子在该行段增加 $t-1$ 对攻击

3. 跑最小费用最大流：

   • 每增加一个棋子（流量）就记录当前总攻击对数
   • 预处理所有 $k$ 的答案

方法二：动态规划（更简单）

由于 $n \leq 50$，连通段数量不多：

• 行连通段数 ≤ $n^2$
• 列连通段数 ≤ $n^2$

DP状态： $dp[i][j]$ = 考虑前 $i$ 个行段，选了 $j$ 条边（棋子）时的最小攻击对数

转移：

• 在第 $i$ 个行段中放 $t$ 个棋子
• 这些棋子必须分配到不同的列段（不能在同一列段放多个，否则会增加列的攻击对数）
• 需要同时考虑列段的约束

但这样二维约束较复杂，所以通常用费用流更直观。

算法步骤

1. 提取连通段：

   • 扫描每一行，提取连续的空位段作为行连通段
   • 扫描每一列，提取连续的空位段作为列连通段

2. 建二分图：

   • 每个空位对应一条边：连接它所在的行段和列段

3. 费用流求解：

   • 对每个行段 $i$：拆为入点和出点，入点→出点有若干条边，第 $t$ 条边费用为 $t-1$（边际费用）
   • 列段同理
   • 连接行段出点 → 列段入点（原图中的边）
   • 跑最小费用流，记录每增加一个棋子时的最小攻击对数

4. 回答询问：

   • 预处理所有 $k$ 的答案
   • $O(1)$ 回答每个询问

复杂度

• 连通段数量：$O(n^2)$
• 费用流复杂度可接受（$n=50$ 时很小）
• 预处理后 $O(1)$ 回答询问

关键点

• 攻击对数 = 行段内攻击对数 + 列段内攻击对数
• 边际费用递增 → 费用流建模
• 每个棋子是行段和列段的连接