题目描述

我们有一个目标字符串数组 a，长度为 n。
初始时，我们有一个长度为 n 的数组 c，所有元素都是空白符号 *。
我们还有 m 个神经网络，第 i 个网络可以生成一个字符串数组 b_i，长度也为 n。

我们可以执行两种操作任意次：
1. 神经网络填充 (Op 1): 选择一个神经网络 i。该网络会随机选择数组 c 中的一个空白位置 j，并将 c[j] 替换为 b_i[j]。此操作成本为 1。
2. 置为空白 (Op 2): 选择一个位置 j，并将 c[j] 替换为空白符号 *。此操作成本为 1。

我们需要预先设定一个操作序列，这个序列必须保证无论神经网络操作中随机选择了哪个空白位置，最终得到的数组 c 都与目标数组 a 完全相同。

在所有能够保证得到数组 a 的操作序列中，找到操作次数最少的序列，并输出其操作次数。如果不存在任何操作序列能保证得到数组 a，则输出 -1。

样例

输入 #1

4
3 3
I love apples
He likes apples
I love cats
They love dogs
3 2
Icy wake up
wake Icy up
wake up Icy
4 3
c o D E
c o D s
c O l S
c o m E
4 5
a s k A
d s D t
O R i A
a X b Y
b a k A
u s k J

输出 #1

5
-1
6
8

样例 1 解释:
目标 a = [I, love, apples]
网络 1: b1 = [He, likes, apples]
网络 2: b2 = [I, love, cats]
网络 3: b3 = [They, love, dogs]

• 为了得到 a[0] = I，必须使用网络 2。
• 为了得到 a[1] = love，必须使用网络 2 或 3。
• 为了得到 a[2] = apples，必须使用网络 1。

一个可能的保证策略（成本 5）：
1. Op1(2)
2. Op1(2)
3. Op1(2) (此时 c 保证为 b2 = [I, love, cats]) (成本 3)
4. Op2(2) (将 c[2] 置为空白) (成本 +1)
5. Op1(1) (此时只有 c[2] 是空白，网络 1 保证将其填充为 b1[2]=apples) (成本 +1)
最终 c = [I, love, apples]。总成本 5。

算法 (贪心策略)

$O(N \cdot M)$ 对每个测试用例

思路分析

1. 理解 “保证”: 问题的核心在于操作 1 (神经网络填充) 的随机性。它会随机选择一个 空白 位置进行填充。为了 保证 最终结果是 a，我们的策略必须在任何随机选择下都能成功。
   特别是，如果我们想确保 c[j] 最终变成 a[j]，当执行填充操作时，我们必须对神经网络的选择和当前 c 的状态有足够的控制。
   最直接能保证 c[j] 被特定值填充的方法是：当使用某个网络 i 时，j 是 c 中唯一的空白位置。这样，网络 i 别无选择，只能填充 c[j]。

2. 必要条件: 要想最终得到 a，对于目标数组 a 中的每一个位置 j，必须至少存在一个神经网络 i，使得该网络在 j 位置生成的字符串与目标字符串相同，即 b[i][j] == a[j]。如果对于某个位置 j，所有的神经网络 b_i 在该位置生成的字符串 b[i][j] 都不等于 a[j]，那么无论如何操作，都不可能让 c[j] 变成 a[j]。因此，这是得到解的一个必要条件。如果此条件不满足，应直接输出 -1。

3. 构造保证策略: 考虑如何设计一个操作序列来保证得到 a。基于第 1 点的观察，我们可以设计一个两阶段策略：

   • 阶段 1: 建立一个确定的中间状态。
     选择一个神经网络 i。重复执行 Op 1 (使用网络 i) 共 n 次。

     • 为什么是 n 次？ 考虑执行 n 次 Op1(i) 后的状态。初始有 n 个空白。每次操作减少一个空白（如果填充的是之前未填充的位置）或保持空白数不变（如果填充的是因为 Op 2 而变为空白的位置，但本策略不使用 Op 2）。关键在于：经过 n 次填充操作后，数组 c 中不可能再有空白。如果还有空白 j，说明在之前的 n 次填充中，j 从未被选中过。但是，每次操作至少填充一个位置。经过 n 次，所有位置都应该被填充过至少一次。
     • 最终状态是什么？ 当我们重复使用同一个网络 i 进行填充时，一个位置 j 可能被多次写入。但由于没有 Op 2 操作，一旦一个位置 j 被填充了 b[i][j]，它就会一直保持这个值，直到所有位置都被填充。因此，在执行 n 次 Op1(i) 后，可以保证数组 c 的状态恰好等于神经网络 i 的输出 b_i。 (即 c[j] = b[i][j] 对所有 j)。
     • 此阶段的操作成本为 n。

   • 阶段 2: 修正与目标 a 不符的位置。
     现在数组 c 的状态是 b_i。我们需要将其变为 a。
     遍历所有位置 j (从 0 到 n-1)：

     • 如果 c[j] (即 b[i][j]) 已经等于 a[j]，则此位置无需修改。
     • 如果 c[j] != a[j]，我们需要将 c[j] 修正为 a[j]。根据必要条件，我们知道一定存在某个（或某些）神经网络 k 使得 b[k][j] == a[j]。
     • 修正步骤（保证）：
       1. 执行 Op 2(j)：将 c[j] 置为空白 *。 (成本 1)
       2. 执行 Op 1(k)：选择一个满足 b[k][j] == a[j] 的网络 k。由于此时 c[j] 是唯一的空白位置，神经网络 k 必定会填充 c[j]，将其值设为 b[k][j] = a[j]。 (成本 1)
     • 每个需要修正的位置 j 都需要 2 次操作。

4. 计算总操作次数:

   • 阶段 1 (填充) 的成本是 n。
   • 阶段 2 (修正) 的成本是 2 * (需要修正的位置数)。
   • 需要修正的位置数等于 n - (b_i 与 a 匹配的位置数)。令 count(i) 为网络 i 的输出 b_i 与目标 a 在相同位置上字符串相等的数量，即 count(i) = |{j | b[i][j] == a[j]}|。
   • 那么需要修正的位置数是 n - count(i)。
   • 总成本 Cost(i)（使用网络 i 进行初始填充的策略）= n (阶段1) + 2 * (n - count(i)) (阶段2)
   • Cost(i) = n + 2n - 2 * count(i) = 3n - 2 * count(i)。

5. 最小化操作次数:
   我们设计的策略能够保证得到最终结果 a。为了使总操作次数最少，我们应该选择哪个神经网络 i 用于阶段 1 的填充呢？
   我们应该选择那个能使 Cost(i) = 3n - 2 * count(i) 最小的网络 i。
   要最小化 3n - 2 * count(i)，就等价于最大化 count(i)。
   因此，我们应该找到与目标数组 a 匹配位置最多的那个神经网络 i。令 max_matches = max(count(k)) 对所有 $k = 1 \dots m$。
   那么，最小的操作次数就是 3n - 2 * max_matches。

6. 算法流程总结:

   1. 读取输入 n, m, a, 和所有的 b_i。
   2. 检查必要条件: 遍历每个位置 j (0 to n-1)。对于每个 j，检查是否存在至少一个网络 i 使得 b[i][j] == a[j]。如果存在某个 j 没有任何网络匹配，则输出 -1 并结束。
   3. 计算最大匹配数: 初始化 max_matches = 0。遍历每个网络 i (0 to m-1)：
      • 计算当前网络 i 与 a 的匹配数 current_matches = 0。
      • 遍历每个位置 j (0 to n-1)：如果 b[i][j] == a[j]，则 current_matches++。
      • 更新 max_matches = max(max_matches, current_matches)。
   4. 计算最小操作数: ans = 3 * n - 2 * max_matches。
   5. 输出 ans。

时间复杂度

• 读取输入：取决于总的字符串长度和 nm，设总长度为 L，则约为 O(L + nm)。
• 检查必要条件：O(n * m * S)，其中 S 是比较字符串的平均时间（由于长度限制为 10，可视为 O(1)）。所以是 O(n * m)。
• 计算最大匹配数：外层循环 m 次，内层循环 n 次，比较字符串。复杂度 O(n * m)。
• 计算最终答案：O(1)。
• 每个测试用例的总时间复杂度主要是 O(n * m)。
• 由于所有测试用例的 n*m 总和有限制，总的运行时间是可接受的。

空间复杂度

• 存储数组 a 和 b：取决于总字符串长度 L 和 n*m。
• 其他变量：O(n) 或 O(m)。
• 主要是输入数据占用的空间。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// 处理单个测试用例的函数
void solve() {
    int n, m; // 数组长度 n, 神经网络数量 m
    std::cin >> n >> m;

    // 存储目标数组 a
    std::vector<std::string> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    // 存储 m 个神经网络的输出数组 b
    // b[i] 是第 i 个网络的输出数组
    std::vector b(m, std::vector<std::string>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> b[i][j];
        }
    }

    // 1. 检查必要条件：每个位置 j 是否至少有一个网络 i 满足 b[i][j] == a[j]
    for (int j = 0; j < n; j++) { // 遍历目标数组的每个位置
        bool ok = false; // 标记位置 j 是否有匹配的网络
        for (int i = 0; i < m; i++) { // 遍历所有网络
            if (b[i][j] == a[j]) { // 如果找到一个匹配的网络
                ok = true; // 标记为真
                break; // 不需要检查其他网络了
            }
        }
        if (!ok) { // 如果遍历完所有网络，位置 j 仍然没有找到匹配
            std::cout << -1 << "\n"; // 输出 -1，表示无法保证得到 a
            return; // 当前测试用例结束
        }
    }

    // 2. 计算与目标数组 a 匹配位置最多的网络的匹配数 (max_matches)
    int max_matches = 0; // 初始化最大匹配数为 0
    for (int i = 0; i < m; i++) { // 遍历每个网络 i
        int current_matches = 0; // 计算当前网络 i 的匹配数
        for (int j = 0; j < n; j++) { // 遍历每个位置 j
            // 如果网络 i 在位置 j 的输出与目标 a 相同
            if (b[i][j] == a[j]) {
                current_matches++; // 增加当前网络的匹配数
            }
        }
        // 更新全局最大匹配数
        max_matches = std::max(max_matches, current_matches);
    }

    // 3. 计算最小操作次数
    // 公式： 3 * n - 2 * max_matches
    int ans = 3 * n - 2 * max_matches;

    // 4. 输出结果
    std::cout << ans << "\n";
}

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}