Monocarp 的考试大作战！喵喵来帮你分析~ ฅ^•ﻌ•^ฅ

哈喽，各位同学喵~ 这里是你们最可靠的猫娘小助手！

今天我们要来帮助一位叫 Monocarp 的同学解决他的考试难题。他正对着一大堆考卷发愁呢，我们这些聪明又热心的小猫咪，当然要伸出援手啦！让我们一起来看看是什么样的问题，然后用我们猫咪的智慧，帮他梳理得清清楚楚，好不好呀？

---

题目大意

Monocarp 的考试有 $n$ 个不同的问题，编号从 1 到 $n$。现在有 $m$ 份不同的考卷清单。

奇特的是，每份考卷清单都恰好包含了 $n-1$ 个问题。也就是说，每份考卷都会缺少一个问题。对于第 $i$ 份考卷，我们知道它缺少的问题是 $a_i$。

Monocarp 自己已经学会了 $k$ 个问题，分别是 $q_1, q_2, \dots, q_k$。

考试的时候，教授会从这 $m$ 份考卷里随机抽一份给他。要想通过考试，Monocarp 必须会考卷上的所有问题。

我们的任务就是，对于每一份考卷，判断如果 Monocarp 抽到它，能不能通过考试。最后输出一个由 '1' 和 '0' 组成的字符串，'1' 代表能通过，'0' 代表不能，喵~

举个例子： 假设有 4 个问题 [1, 2, 3, 4]。 一份考卷缺少问题 3（也就是 a_i = 3），那么这份考卷上的问题就是 [1, 2, 4]。 如果 Monocarp 恰好会 [1, 2, 4]，那他就能通过。但如果他不会问题 2，那他就无法通过这份考卷啦。

---

解题思路

要解决这个问题，我们得像小猫抓老鼠一样，先找到问题的关键点，喵！关键点就是 Monocarp 不会 的那些问题。只要考卷上出现一个他不会的问题，他就输了。

所以，我们的思路可以分成清晰的几步：

第一步：找出 Monocarp 不会的“知识盲区”

我们知道总共有 $n$ 个问题，也知道他会哪 $k$ 个。那剩下的 $n-k$ 个不就是他不会的嘛？我们可以先把这些他不会的问题全部找出来，放进一个小本本（或者说，一个列表）里。

第二步：分类讨论，逐个击破！

找到了他所有不会的问题之后，我们就可以根据他不会问题的数量来进行分类讨论了，喵~

状况一：Monocarp 是学霸猫！

如果 Monocarp 不会的问题数量是 0，也就是说他会所有 $n$ 个问题。那不管教授给他哪份考卷，考卷上的问题他肯定都会呀！所以，他能通过所有 $m$ 份考卷。

结论： 如果 Monocarp 会所有问题，输出 $m$ 个 '1'。

状况二：Monocarp 有点小马虎...

如果 Monocarp 不会的问题多于 1 个（比如 2 个或更多）。 我们知道，每份考卷只比题库少 1 个问题。这意味着，如果 Monocarp 有两个或更多的问题不会，那么任何一份考卷最多只能“豁免”掉其中一个。考卷上必然还存在至少一个他不会的问题。 就像猫咪有两个毛线球都想玩，但一次只能抓住一个，爪子底下总会漏掉一个呀，喵~ 所以，这种情况下，他一份考卷也通不过。

结论： 如果 Monocarp 不会的问题超过 1 个，输出 $m$ 个 '0'。

状况三：就差那么一点点！

这是最有趣的情况！如果 Monocarp 恰好只有 1 个问题不会。我们叫这个问题为 x 吧。 现在，他能不能通过某一份考卷，完全取决于这份考卷上有没有问题 x。 对于第 $i$ 份考卷，它恰好缺少问题 $a_i$。

• 如果这份考卷缺少的问题 a_i 正好就是他不会的那个问题 x（即 a_i == x），那么问题 x 就不会出现在考卷上，他会的其他问题都在。完美！他能通过！
• 如果 a_i 不是 x，那么问题 x 就会出现在这份考卷上，他就无法通过了。

结论： 如果 Monocarp 恰好有 1 个问题不会（设为 x），那么对于第 $i$ 份考卷，当且仅当 a_i == x 时，他能通过。

一个重要的优化小技巧~

在开始分类讨论之前，我们可以先做一个聪明的检查。

我们先找出所有 Monocarp 不会的问题，再看看这 $m$ 份考卷都能豁免哪些问题（也就是 a 数组里的那些问题）。

如果存在一个 Monocarp 不会的问题，它从来没有出现在任何考卷的“豁免名单”a中，那这个倒霉的问题就会出现在每一张考卷上！结果嘛...当然是全部挂科啦，喵呜~ T_T

我们可以先做这个检查。如果发现这种情况，直接输出 $m$ 个 '0' 就好，省时又省力！

---

题解代码

好啦，思路理清了，就来看看代码实现吧！这就像把抓到的老鼠（思路）好好地处理一下，变成美味的晚餐（代码），喵~

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> a[i];
    }
    std::vector<int> q(k);
    for (int i = 0; i < k; ++i) {
        std::cin >> q[i];
    }

    // 用一个 bool 数组来标记 Monocarp 会哪些题
    // 就像给会的题目贴上小鱼干贴纸一样，喵~
    std::vector<bool> is_known(n + 1, false);
    for (int val : q) {
        is_known[val] = true;
    }

    // 找出所有他不会的问题
    std::vector<int> unknown_questions;
    for (int i = 1; i <= n; ++i) {
        if (!is_known[i]) {
            unknown_questions.push_back(i);
        }
    }

    // 标记哪些问题是可能被豁免的
    std::vector<bool> is_in_a(n + 1, false);
    for (int val : a) {
        is_in_a[val] = true;
    }

    // 这是我们前面说的优化小技巧！
    // 检查是否存在一个不会的问题，它永远不会被豁免
    for (int uq : unknown_questions) {
        if (!is_in_a[uq]) {
            // 如果存在，那他所有考试都完蛋啦
            for (int i = 0; i < m; ++i) {
                std::cout << '0';
            }
            std::cout << '\n';
            return;
        }
    }

    // 获取不会问题的数量
    int unknown_count = unknown_questions.size();

    // 情况二：不会的问题太多了
    if (unknown_count > 1) {
        for (int i = 0; i < m; ++i) {
            std::cout << '0';
        }
        std::cout << '\n';
        return;
    }

    // 情况一：学霸猫，全会！
    if (unknown_count == 0) {
        for (int i = 0; i < m; ++i) {
            std::cout << '1';
        }
        std::cout << '\n';
        return;
    }

    // 情况三：只差一个问题
    // 此时 unknown_count 必然等于 1
    int x = unknown_questions[0]; // 这就是他唯一不会的问题
    for (int val : a) {
        if (val == x) { // 如果考卷正好豁免了这个问题
            std::cout << '1';
        } else {
            std::cout << '0';
        }
    }
    std::cout << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题虽然不难，但也用到了几个很基础很重要的知识点哦，就像猫咪的肉垫一样，柔软又关键！

1. 布尔数组 / 哈希思想 (Boolean Array / Hashing)

   • 我们用 std::vector<bool> is_known(n + 1, false); 来快速标记和查询一个问题是否被学会。这本质上是一种哈希思想。因为问题的编号是 1 到 $n$，范围不大，可以直接用数组下标来映射问题编号，实现 O(1) 的查询。这比用 std::map 或者每次都在 q 数组里搜索要快得多！is_in_a 也是同理。

2. 分类讨论 (Case Analysis)

   • 这是算法竞赛和解决问题时最核心的技能之一！将一个复杂问题根据关键变量（这里是“不会问题的数量”）分解成几个简单、互斥且完备的子问题。一旦分类清晰，每个子问题的逻辑就变得非常简单了。

3. 边缘情况处理 (Edge Case Handling)

   • 我们的“优化小技巧”其实就是一个重要的边缘情况。在解决问题时，多想想那些“如果……会怎么样？”的特殊情况，比如“如果一个不会的问题永远不被跳过会怎么样？”，往往能让你的代码更健壮，甚至找到解题的捷径。

---

总结

好啦，这样一来，Monocarp 的考试问题就迎刃而解啦！是不是很简单呢，喵？

只要思路清晰，像小猫咪一样一步一步、有条不紊地分析，再复杂的问题也能被我们解决掉！从找到关键信息（不会的问题），到进行合理的分类讨论，最后把逻辑转化为代码，每一步都充满了乐趣。

希望这次的讲解对你有帮助哦！下次再遇到难题，也欢迎来找我！喵~ ฅ'ω'ฅ