题目分析
本题要求找到一个长度为 $L$ 的二进制方案串，使得与 $N$ 个匹配项的总汉明距离最小，并且该方案不在 $M$ 个禁用方案中。

---

算法思路

核心思想：Trie树剪枝搜索 + 预处理最优下界

关键观察：

• 对于每一位，如果选择 0，错误值贡献为这一位为 1 的匹配项个数
• 如果选择 1，错误值贡献为这一位为 0 的匹配项个数
• 禁用方案构成一个集合，需要避免选择它们

---

算法流程详解

1. 数据预处理

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
        tot[j] += a[i][j] - '0';

统计每一位上 1 的出现次数 tot[i]。

2. 计算最优下界

for (int i = k; i >= 1; i--)
    sum[i] = sum[i + 1] + min(tot[i], n - tot[i]);

sum[i] 表示从第 i 位到第 L 位的最小可能错误值之和（忽略禁用约束），用于后续剪枝。

3. 构建禁用方案Trie树

void insert(int x) {
    int now = 0;
    for (int i = 1; i <= k; i++) {
        if (ch[now][b[x][i]^'0'] == -1)
            ch[now][b[x][i]^'0'] = ++cnt;
        now = ch[now][b[x][i]^'0'];
    }
}

将所有禁用方案插入Trie树，便于快速判断当前路径是否为禁用方案。

4. 深度优先搜索

void dfs(int i, int s, int now) {
    if (now == -1)  // 当前路径是禁用方案
        return ans = min(ans, s + sum[i]), void();
    
    if (i == k + 1)  // 到达叶子节点
        return;
    
    // 选择0
    dfs(i + 1, s + tot[i], ch[now][0]);
    // 选择1  
    dfs(i + 1, s + n - tot[i], ch[now][1]);
}

• i: 当前处理到的位
• s: 前 i-1 位已产生的错误值
• now: 在Trie树中的当前位置

剪枝策略：

• 当遇到禁用方案时（now == -1），用当前值加上剩余位的最优下界更新答案
• 否则继续搜索两种选择

---

关键技术与优化

1. Trie树高效判重

• 使用数组实现，避免指针开销
• 预处理所有禁用方案，$O(ML)$ 时间构建

2. 最优下界剪枝

sum[i] = sum[i + 1] + min(tot[i], n - tot[i])

提供剩余位的最小可能错误值，当 当前错误值 + sum[i] >= 当前最优解 时可提前剪枝（代码中隐含）。

3. 位运算优化

b[x][i]^'0'

将字符 '0'/'1' 转换为整数 0/1。

4. 空间优化

• 使用静态数组而非动态分配
• Trie树节点数最多 $ML$，在数据范围内可行

---

复杂度分析

• 预处理：$O(NL + ML)$
• DFS搜索：最坏 $O(2^L)$，但实际由于：
  • 禁用方案限制搜索空间
  • 最优下界剪枝
  • $M \leq 1000$ 且 $L \leq 1000$，实际运行效率较高

---

样例验证

样例1

输入：
4 1 4
0000
1000  
1100
1010
1000（禁用）

• tot = [1,2,2,0]（每列1的个数）
• 搜索找到最优方案 0000，错误值 = 1+2+2+0 = 5

样例2

输入：
2 4 4
0000
0000
0000 1000 0100 0010（禁用）

• tot = [0,0,0,0]
• 唯一可用方案 0001，错误值 = 0+0+0+2 = 2

---

算法优势

1. 剪枝高效：最优下界大幅减少搜索空间
2. 判重快速：Trie树 $O(L)$ 判断是否为禁用方案
3. 实现简洁：代码清晰，逻辑直接
4. 理论保证：找到全局最优解

该算法通过巧妙的预处理和剪枝策略，在指数级搜索空间中高效找到了满足约束的最优方案。