猜数字

题目描述

一个人设定一组四码的数字作为谜底，另一方猜。
每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。
其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。
例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。
例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。
当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。

输入描述

第一行输入一个正整数，0＜N ＜ 100。
接下来N行，每一行包含一个猜测的数字与提示结果。

输出描述

输出最后的答案，答案不确定则输出NA。

效果展示

示例1
输入

bash

输出
3585

解题思路

暴力枚举所有可能的谜底，即0000~9999，然后用每一个谜底去匹配输入的猜测。如果当前谜底与输入的猜测产生的提示符合预期，则说明该谜底是可行的。如果某个谜底可以符合所有输入的猜测，那么该谜底就是题解。如果暴力枚举出来的所有谜底中只有一个可行的谜底，那么该谜底就是题解，否则本题无解，返回NA。

由于需要验证0000~9999这一万个可能的谜底，而每个谜底最多需要验证100个输入的猜测数字，因此该算法非常容易超时。为了优化算法，我们可以对输入的猜测进行剪枝处理。例如，当输入的猜测提示为0A0B时，我们可以排除所有包含输入数字的谜底，因为这些谜底与输入数字的位置和数字都不匹配。同样地，当输入的猜测提示为0A时，我们可以排除所有包含输入数字的位置的谜底，因为这些谜底与输入数字的位置不匹配。通过对输入的猜测进行剪枝处理，我们可以大大减少需要验证的谜底数量，从而提高算法效率。

cpp

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <sstream>

using namespace std;

int main() {
    int n;
    cin >> n; // 输入猜测的次数

    // 存储所有猜测的数字和提示结果
    vector<pair<string, string>> guessInfos;
    for (int i = 0; i < n; i++) {
        string guessNum, guessResult;
        cin >> guessNum >> guessResult; // 输入猜测的数字和结果
        guessInfos.push_back(make_pair(guessNum, guessResult)); // 将猜测的数字和结果存入列表中
    }

    int validCount = 0; // 记录符合条件的答案数量
    string validAnswer = ""; // 存储符合条件的答案

    // 遍历所有可能的四位数
    for (int num = 0; num <= 9999; num++) {
        stringstream ss;
        ss << setw(4) << setfill('0') << num;
        string answer = ss.str(); // 将数字格式化为四位数字符串
        bool isValid = true; // 标记当前答案是否有效

        // 遍历每个猜测的数字和结果
        for (const auto& guessInfo : guessInfos) {
            string guess = guessInfo.first; // 获取猜测的数字
            string expectResult = guessInfo.second; // 获取猜测的结果

            int countA = 0; // 记录数字和位置都正确的个数
            int countB = 0; // 记录数字正确但位置不正确的个数

            vector<int> answerArr(10, 0); // 存储答案中每个数字出现的次数
            vector<int> guessArr(10, 0); // 存储猜测中每个数字出现的次数

            // 遍历每个位置
            for (int i = 0; i < guess.length(); i++) {
                int c1Int = guess[i] - '0'; // 获取猜测中该位置上的数字
                int c2Int = answer[i] - '0'; // 获取答案中该位置上的数字

                if (c1Int == c2Int) {
                    countA++; // 如果数字和位置都正确，countA+1
                } else {
                    guessArr[c1Int]++; // 在 guessArr 中记录该数字出现的次数
                    answerArr[c2Int]++; // 在 answerArr 中记录该数字出现的次数
                }
            }

            for (int i = 0; i < 10; i++) {
                countB += min(answerArr[i], guessArr[i]); // 计算数字正确但位置不正确的个数
            }

            string realResult = to_string(countA) + "A" + to_string(countB) + "B"; // 根据猜测和答案计算真实结果

            if (realResult != expectResult) {
                isValid = false; // 如果真实结果和猜测结果不一致，标记当前答案为无效
                break;
            }
        }

        if (isValid) {
            validCount++; // 如果当前答案有效，更新符合条件的答案数量
            validAnswer = answer; // 更新符合条件的答案

            if (validCount > 1) {
                break; // 如果符合条件的答案数量大于1，跳出循环
            }
        }
    }

    if (validCount != 1) {
        cout << "NA" << endl; // 如果符合条件的答案不唯一，输出 NA
    } else {
        cout << validAnswer << endl; // 如果符合条件的答案唯一，输出答案
    }

    return 0;
}

猜数字 ​

题目描述 ​

输入描述 ​

输出描述 ​

效果展示 ​

解题思路 ​

猜数字

题目描述

输入描述

输出描述

效果展示

解题思路