A. 棘手的模板 题解

1. 题目理解

我们有三个长度为 $n$ 的字符串 $a$、$b$、$c$，均由小写字母组成。我们需要构造一个模板 $t$，长度也为 $n$，每个位置可以是小写字母或大写字母，满足：

• 对于 $a$ 和 $b$：所有位置都必须与模板匹配；
• 对于 $c$：至少有一个位置与模板不匹配。

匹配规则（对于每个位置 $i$）：

• 若 $t_i$ 是小写，则字符串在该位置的字母必须等于 $t_i$；
• 若 $t_i$ 是大写，则字符串在该位置的字母必须不等于 $t_i$ 对应的小写字母。

题目要求判断是否存在这样的模板。

2. 关键观察

对于位置 $i$，我们分析模板在该位置的字符 $t_i$ 的两种可能：

情况 1：$t_i$ 为小写字母（假设为 $x$）

此时匹配条件为：

• $a_i = x$
• $b_i = x$
• $c_i \neq x$ （我们希望 $c$ 不匹配）

因此，为了让 $a$ 和 $b$ 同时匹配，必须有 $a_i = b_i$；同时，为了让 $c$ 不匹配，必须有 $c_i \neq a_i$。

情况 2：$t_i$ 为大写字母（假设为 $X$，对应小写为 $x$）

此时匹配条件为：

• $a_i \neq x$
• $b_i \neq x$
• $c_i = x$ （希望 $c$ 不匹配）

注意，要使 $c$ 不匹配，必须 $c_i = x$，即 $c_i$ 恰好等于该大写字母的小写形式。而 $a$ 和 $b$ 要匹配，必须它们都不等于 $x$。因此，只要 $a_i \neq c_i$ 且 $b_i \neq c_i$，我们就可以选择 $t_i$ 为对应 $c_i$ 的大写字母，使得 $a$ 和 $b$ 匹配（因为它们不等于 $c_i$），而 $c$ 不匹配（因为 $c_i$ 等于该大写字母的小写形式）。

3. 存在性条件

由上述分析可知，只要存在某个位置 $i$ 满足 $a_i \neq c_i$ 且 $b_i \neq c_i$，我们就可以在这个位置放置一个大写字母（即 $c_i$ 的大写形式），使得 $a$ 和 $b$ 匹配，而 $c$ 不匹配。对于其他位置，我们可以随意设置模板使得 $a$ 和 $b$ 匹配（例如直接使用 $a_i$ 的小写形式，此时由于 $a_i = b_i$ 则它们匹配，而 $c$ 在该位置可能匹配也可能不匹配，但只要有一个位置不匹配，整体 $c$ 就不匹配）。

如果对于所有位置 $i$，都不满足 $a_i \neq c_i$ 且 $b_i \neq c_i$，即对于每个位置，要么 $a_i = c_i$，要么 $b_i = c_i$（或两者都等于），那么无论我们如何选择模板，都无法让 $c$ 不匹配的同时保证 $a$ 和 $b$ 都匹配。因为：

• 若选择小写字母，要求 $a_i = b_i = t_i$，但此时若 $c_i = a_i$ 则 $c$ 也会匹配，若 $c_i \neq a_i$ 则要求 $a_i = b_i \neq c_i$，这又回到了 $a_i \neq c_i$ 且 $b_i \neq c_i$ 的条件。
• 若选择大写字母，要求 $a_i \neq c_i$ 且 $b_i \neq c_i$，这正是我们需要的条件。

因此，当且仅当存在至少一个位置 $i$ 满足 $a_i \neq c_i$ 且 $b_i \neq c_i$ 时，答案才为 YES，否则为 NO。

标程正是基于此判断。

4. 算法步骤

对于每个测试用例：

1. 读入 $n$ 和三个字符串 $a$、$b$、$c$。
2. 遍历 $i = 0$ 到 $n-1$：
   • 如果 $a_i \neq c_i$ 且 $b_i \neq c_i$，标记找到可行位置，终止遍历。
3. 若找到可行位置，输出 "YES"；否则输出 "NO"。

时间复杂度：$O(n)$ 每个测试用例。总复杂度 $O(\sum n)$，由于 $n \le 20$，完全足够。

5. C++ 代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string a, b, c;
        cin >> a >> b >> c;
        
        bool found = false;
        for (int i = 0; i < n; ++i) {
            if (a[i] != c[i] && b[i] != c[i]) {
                found = true;
                break; // 找到一个即可
            }
        }
        cout << (found ? "YES" : "NO") << '\n';
    }
    return 0;
}

6. 总结

本题巧妙地将模板匹配条件转化为简单的字符不等关系判断。关键在于意识到：要使 $c$ 不匹配，我们只需在一个位置上利用大写字母的“排斥”性质，而该位置必须满足 $a$ 和 $b$ 都与 $c$ 不同。该思路简洁且易于实现。