题目描述

有 N 个宝宝玩猜帽子游戏。每个宝宝头上戴着一顶帽子，颜色是黑色（用数字 1 表示）或黄色（用数字 2 表示）。每个宝宝能看到其他人帽子的颜色，但看不到自己的。

游戏开始后，每个宝宝可以：
1. 猜自己帽子的颜色（猜 1 或 2）。
2. 弃权不猜（用数字 0 表示）。

游戏获胜（获得大奖）的条件是：
1. 没有任何一个宝宝猜错自己的帽子颜色。
2. 并且，至少有一个宝宝猜对了自己帽子的颜色。

如果满足以下任一情况，则游戏失败（没有奖）：
1. 所有宝宝都弃权不猜。
2. 只要有一个宝宝猜错了自己的帽子颜色。

给定 N 顶帽子的实际颜色序列，以及 K 群宝宝各自的猜测结果。对于每一群宝宝，判断他们是否能获得大奖。

样例

输入:
5
1 1 2 1 2
3
0 1 2 0 0
0 0 0 0 0
1 2 2 0 2

• N=5，实际帽子颜色是 (1, 1, 2, 1, 2) (黑, 黑, 黄, 黑, 黄)。

• K=3，有 3 群宝宝的猜测。

• 第一群猜测: (0, 1, 2, 0, 0)

  • 宝宝 0: 弃权
  • 宝宝 1: 猜 1 (黑)，实际是 1 (黑) -> 猜对
  • 宝宝 2: 猜 2 (黄)，实际是 2 (黄) -> 猜对
  • 宝宝 3: 弃权
  • 宝宝 4: 弃权
  • 结果：无人猜错，且有 2 人猜对。满足获胜条件。

• 第二群猜测: (0, 0, 0, 0, 0)

  • 所有宝宝都弃权。
  • 结果：失败。

• 第三群猜测: (1, 2, 2, 0, 2)

  • 宝宝 0: 猜 1 (黑)，实际是 1 (黑) -> 猜对
  • 宝宝 1: 猜 2 (黄)，实际是 1 (黑) -> 猜错
  • 宝宝 2: 猜 2 (黄)，实际是 2 (黄) -> 猜对
  • 宝宝 3: 弃权
  • 宝宝 4: 猜 2 (黄)，实际是 2 (黄) -> 猜对
  • 结果：有人猜错 (宝宝 1)。失败。

输出:
Da Jiang!!!
Ai Ya
Ai Ya

算法 (模拟判断)

$O(K \times N)$

思路分析

这个问题的核心是根据游戏规则，对每一群宝宝的猜测结果进行判断。我们可以直接模拟这个判断过程。

对于每一群宝宝的猜测（共 K 群，每群 N 个猜测）：

1. 初始化状态:
   我们需要跟踪几个关键信息来判断最终结果：

   • 弃权的人数 (cnt0)。
   • 猜对的人数 (correct)。
   • 是否有人猜错 (wrong)，这是一个布尔标志。

2. 遍历猜测:
   依次检查该群中每个宝宝（从 0 到 N-1）的猜测情况：

   • 令第 j 个宝宝的实际帽子颜色为 a[j]，他的猜测为 g[i][j] (这里 i 代表第几群宝宝)。
   • 情况一：弃权: 如果 g[i][j] == 0，则弃权人数 cnt0 加 1。
   • 情况二：猜对了: 如果 g[i][j] != 0 (表示没有弃权) 且 g[i][j] == a[j] (猜测颜色与实际颜色相同)，则猜对人数 correct 加 1。
   • 情况三：猜错了: 如果 g[i][j] != 0 且 g[i][j] != a[j]，则说明这个宝宝猜错了。我们立刻将 wrong 标志设为 true。

3. 判断结果:
   遍历完该群所有宝宝的猜测后，根据规则判断胜负：

   • 失败条件 1: 如果 wrong 标志为 true（即有人猜错），则该群宝宝失败。
   • 失败条件 2: 如果 cnt0 == n（即所有人都弃权），则该群宝宝失败。
   • 失败条件 3: 在没有人猜错 (wrong 为 false) 且不是所有人都弃权 (cnt0 != n) 的前提下，如果 correct == 0（即没有人猜对），则该群宝宝也失败。
   • 获胜条件: 如果以上三个失败条件都不满足，即：
     • wrong 为 false (无人猜错)
     • cnt0 != n (不是所有人都弃权)
     • correct > 0 (至少一人猜对)
       则该群宝宝获胜。

4. 输出:
   根据判断结果，输出 “Da Jiang!!!” (获胜) 或 “Ai Ya” (失败)。

5. 重复: 对 K 群宝宝重复以上步骤。

代码逻辑解读

提供的 C++ 代码完美地实现了上述思路：

• 首先读取 N 和实际颜色数组 a。
• 然后读取 K 和 K 组猜测结果，存入二维数组 g。
• 外层循环 for (int i = 0; i < k; i++) 处理每一群宝宝 i。
• 在循环内部，初始化 cnt0 = 0, correct = 0, wrong = false。
• 内层循环 for (int j = 0; j < n; j++) 遍历该群的每个宝宝 j。
• if-else if-else 结构根据宝宝 j 的猜测 g[i][j] 与实际颜色 a[j] 的关系，更新 cnt0, correct, wrong。
• 最后，if (cnt0 == n || wrong || correct == 0) 这行代码检查了所有的失败条件：
  • cnt0 == n: 对应失败条件 1。
  • wrong: 对应失败条件 2。
  • correct == 0: 对应失败条件 3。
• 如果满足任何一个失败条件，输出 “Ai Ya”。
• 否则（不满足任何失败条件，意味着满足获胜条件），输出 “Da Jiang!!!”。

这个逻辑清晰、直接，并且完全符合题目要求。

时间复杂度

• 读取输入：$O(N + K \times N)$。
• 处理 K 组猜测：对于每组猜测，需要遍历 N 个宝宝。所以是 $O(K \times N)$。
• 总时间复杂度为 $O(K \times N)$。考虑到 $N \le 100, K \le 10$，这个复杂度非常小，远在时间限制内。

C++ 代码

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

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

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

    int n; // 帽子个数
    cin >> n;

    vector<int> a(n); // 存储 n 顶帽子的实际颜色 (1:黑, 2:黄)
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int k; // 宝宝群数
    cin >> k;

    // g[i][j] 存储第 i 群宝宝中第 j 个宝宝的猜测结果 (0:弃权, 1:黑, 2:黄)
    vector<vector<int>> g(k, vector<int>(n));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    // 遍历每一群宝宝的猜测结果
    for (int i = 0; i < k; i++) {
        int cnt0 = 0;     // 统计本群弃权人数
        int correct = 0;  // 统计本群正确猜测人数
        bool wrong = false; // 标记本群是否有人猜错，初始为 false

        // 遍历本群中每个宝宝的猜测
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 0) { // 如果宝宝 j 弃权
                cnt0++;
            } else if (g[i][j] == a[j]) { // 如果宝宝 j 猜对了
                correct++;
            } else { // 否则，宝宝 j 猜错了
                wrong = true; // 标记有人猜错
                // 注意：即使有人猜错，我们仍然需要完成内循环，
                // 但一旦 wrong 为 true，最终结果一定是 "Ai Ya"
            }
        }

        // 根据统计结果判断胜负
        // 失败条件：(所有人弃权) 或者 (有人猜错) 或者 (无人猜对)
        if (cnt0 == n || wrong || correct == 0) {
            cout << "Ai Ya\n"; // 输出失败信息
        } else {
            // 如果不满足任何失败条件，则获胜
            cout << "Da Jiang!!!\n"; // 输出获胜信息
        }
    }

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