「PA 2020」Wybór zadań 题解

算法思路

本题使用贪心算法和直接计数的方法来检查是否能组成完整的题目集合。核心思想是验证每个位置是否有足够数量的题目。

关键观察

1. 题目需求分析

• 前4轮（1-4）：每个位置需要 $1$ 道题
• 第5轮：每个位置需要 $2$ 道题
• 总共需要：$4 \times 3 \times 1 + 3 \times 2 = 12 + 6 = 18$ 道题

2. 充分必要条件

要能组成完整的题目集合，必须满足： 对于每个位置 $(i,j)$：

• 如果 $i \leq 4$：$cnt[i][j] \geq 1$
• 如果 $i = 5$：$cnt[i][j] \geq 2$

代码解析

计数数组初始化

int cnt[6][3] = {0};  // 6行(1-5轮)，3列(A,B,C)

统计每个位置的题目数量

int n;
cin >> n;
while (n--) {
    string s;
    cin >> s;
    cnt[s[0] - '0'][s[1] - 'A']++;  // 将字符转换为数组索引
}

检查可行性

string ans = "TAK";
for (int i = 1; i <= 5; i++)
    for (int j = 0; j < 3; j++)
        if (cnt[i][j] < 1 + (i == 5))  // 前4轮需要1，第5轮需要2
            ans = "NIE";

算法正确性证明

必要性

如果某个位置题目数量不足，显然无法满足要求。

充分性

当所有位置都满足数量要求时：

• 从前4轮的每个位置选择1道题：$4 \times 3 = 12$ 道
• 从第5轮的每个位置选择2道题：$3 \times 2 = 6$ 道
• 总共正好 $18$ 道题，且每个位置都满足要求

复杂度分析

• 时间复杂度：$O(n + 15)$
  • 读取输入：$O(n)$
  • 检查条件：$O(15)$（5轮×3组别）
• 空间复杂度：$O(1)$