「木棍拼正方形」题解

核心思路

从 $n$ 根木棍中选 $6$ 根拼正方形，只有两种拼法：

1. 三根单棍 + 一根三棍拼边

• 三条边各用一根木棍，第四条边用三根木棍拼接
• 需要：三根长度相等的木棍 $L$（作为三条单棍边）
• 还需要：另外三根木棍长度之和等于 $L$（拼成第四条边）

2. 两根单棍 + 两根双棍拼边

• 两条边各用一根木棍，另外两条边各用两根木棍拼接
• 需要：两根长度相等的木棍 $L$（作为两条单棍边）
• 还需要：四根木棍分成两对，每对长度之和等于 $L$（作为两条双棍边）

计数方法

第一步：统计

统计每种长度木棍的出现次数 $\text{cnt}[L]$。

第二步：分别计算两种情况的方案数

情况一（三单棍 + 一三棍边）

对每个可能的边长 $L$：

• 如果 $\text{cnt}[L] \ge 3$，则选出三根 $L$ 的方案数为 $C(\text{cnt}[L], 3)$
• 从长度不等于 $L$ 的木棍中找三根，长度和为 $L$ 的方案数为 $T_3[L]$
• 贡献：$C(\text{cnt}[L], 3) \times T_3[L]$

情况二（两单棍 + 两双棍边）

对每个可能的边长 $L$：

• 如果 $\text{cnt}[L] \ge 2$，则选出两根 $L$ 的方案数为 $C(\text{cnt}[L], 2)$
• 从长度不等于 $L$ 的木棍中找四个，能分成两对且每对和为 $L$ 的方案数为 $P_4[L]$
• 贡献：$C(\text{cnt}[L], 2) \times P_4[L]$

实现技巧

1. 预处理：先枚举所有木棍对，记录和为 $S$ 的数对，用于快速查找
2. 去重：注意木棍不能重复使用，且正方形四条边无序
3. 排序：先对木棍排序，便于使用双指针查找和为特定值的组合

算法复杂度

核心是枚举数对，复杂度 $O(n^2)$，对于 $n \le 5000$ 可以接受。

将两种情况的结果相加就是最终答案。