P2489. 猜数字

解题思路

枚举法概述

正向计算这个问题是比较麻烦的。考虑使用枚举的方式来完成本题。

由于答案由四个数字构成，因此一共要枚举 10^4 个数字。 另外，对于每一个数字而言，都需要去考虑是否和每一个条件匹配。 由于一共存在 N 个条件，N 的最大值为 10^2。 因此总的时间复杂度为 O(mn) = O(10^6)。这种枚举的办法不会超时。

将数字类型转化为字符串类型

考虑到，如果我们想要比较两个数字之间的关系，用字符串类型来比较的效率要远远优于用整数类型。 因此我们最好是构建一个将数字类型转化为字符串类型的函数。

由于我们枚举数字的时候，会从 0 枚举到 9999。所以对于位数不足 4 的数字而言，其字符串形式的高位必须用若干的字符 "0" 来进行填充。譬如把 "15" 填充为 "0015"。

那么，我们就可以通过以下方式来枚举所有数字并转化为字符串类型了：

如果想不到上述方法，也可以使用四重 for 循环，通过从 0 到 9 枚举数字的每一位并拼接到一起，来完成所有数字的枚举。

不过这种写法就显得嵌套过多了，建议还是使用更加简洁的前一种写法来完成枚举。

另外，对于输入的 N 个条件，我们也可以直接使用字符串格式进行储存，而不用特意去转化为数字。 这样才方便后续进行字符串之间的比较。

枚举数字和条件数字的比较

当我们同时拿到枚举数字 s，条件数字 g（表示 guess），以及对应的比较结果 r（表示 result）的时候，我们需要判断 s 和 g 之间的关系是否符合比较结果 r。

首先我们需要明确两种比较的严格定义。这在题目中的描述是比较模糊的，我们只能够通过用例反推。

比较条件 8585 3A0B 和答案 3585，可以看到当 g = "8585" 时，虽然存在第一个 "8" 和 s = "3585" 中的 "8" 位置不同，但是由于 g 中存在第二个 "8" 和 s 中的这个 "8" 属于数字正确且位置相同的关系，这个条件中的 Y 为 0 而不是 1。

这说明，条件 A 的判定优先级要高于条件 B。 如果 g 中存在某个数字既满足条件 A 又满足条件 B，只会计入条件 A（增加 X 的计数）而不会计入条件 B（不会增加 Y 的计数）。

这个结论也可以从条件 8555 2A1B 和答案 3585 得到验证。虽然 g = "8555" 存在第二个 "5" 和 s 中的两个 "5" 位置不同，但是并没有计入条件 B，Y 为 1 而不是 2（Y 是 1 是因为 g 中存在数字 "8" 和 s 中的 "8" 位置不同）。

所以，我们在做关于 X 的判定的时候，可以构建一个哈希集合 `A_set`，来储存所有满足条件 A 的数字。

检查条件 A 较容易完成，只需要枚举 s 和 g 中所有同一位置的数字，比较它们是否相等即可。 如果相等，则将这个数字本身储存在 A_set 中，方便后续关于条件 B 的判定。即：

在得到 A_set 之后，我们就可以来判定条件 B 了。 我们使用一个双重循环枚举 g 和 s 中的所有下标组合，当 g[i] 和 s[j] 相等，且 g[i] 并不是一个满足条件 A 的数时（也就是不位于 A_set 中），我们找到了一个满足条件 B 的数。 另外需要特别注意，一旦找到一个符合条件 B 的数字 `g[i]`，要使用 `break` 直接退出 j 的遍历，否则可能会发生重复统计。综上代码为：

对于比较结果 r，必然由 "XAYB" 这样的格式组成。 首先我们要把 X 和 Y 提取出来，然后构建一个空的 A_set，分别计算传入 check_X 和 check_Y 的结果。当这两个函数都返回 True 时，则整体可以返回 True。即：

构建整体代码框架

前一小节的工作主要围绕单个 s 和 g 的比较，但别忘了 s 和 g 都是要进行枚举的。 所以整体的代码框架为：

同时还需要注意到，题目告知如果不确定答案，需要直接输出 NA。 不确定答案分为两种情况：

1. 一个满足所有条件的数字 s 都没找到 2. 存在超过 1 个的满足所有条件的数字 s

对于这两种情况，我们可以分别设置 "e1" 和 "e2" 两种标识来判断。 在循环外先初始化 ans 为 "e1"，表示一开始没找到任何答案，然后修改更新 ans 的条件：

如果在更新答案时，发现 ans 并不是 "e1"，则说明之前已经找到过至少一个匹配所有条件的数字 s，此时需要把 ans 修改为 "e2"。最后，ans 无论是 "e1" 还是 "e2"，都要输出 "NA"。

这样就完成了整道题目。