P1039 侦探推理

Sanust · 2025-03-29 15:53:54 · 题解

P1039 侦探推理

难点一：证言的读入

我们使用一个 vector 数组记录证言，数组下标表示是谁说的句子，内容是一个结构体，其中 id 表示该句的主语，day 表示是否是说日期的语句，rev 表示是不是否定句，其为真则是否定句，为假则是肯定句。

由于证言必定满足“人名: 文字”的形式，故先 cin 一次，pop_back 掉冒号，记录下来这句话谁说的。接下来再 cin 一次，判第一个词是 I，Today 或其它。考虑第一种，由于有可能一个人本身就叫 I，所以读入人名时提前判断一下。

具体而言，如果是 I am 开头的则为表示说话人自己为主语的句子，如果是 I is 开头的则为名字叫 I 的人为主语的句子，之后 getline 读完句子，判断句子合法性并记录即可。

考虑最后一种，检查这个词是否是一个人名，如果是则与前者同理，如果不是则直接读完并跳过即可。中间那种也一样。

由于数据有锅，每次 getline 的时候都要把尾部的 \r 和 \n 清除掉，这样才能正常判断。强烈建议读入完输出一下你的证言 vector 的内容看看有没有什么问题。

难点二：推理的判断

由于数据量很小且只有一个罪犯，我们可以直接循环枚举所有可能的情况。两层循环，第一层枚举谁是罪犯，第二层枚举今天星期几。接着再枚举每一个人及其证词，判断满不满足条件即可。

对于一个没说过话的人，他既可以说真话也可以说假话，我们单独记录一个值 none 表示没说过话的人的数量。

对于一个说过话的人，我们依据假设的条件判断每句句子的真伪即可，如果这个人说的话全真则此时他说真话，如果全假则此时他说假话，如果有真有假则不合法跳过该种假设条件。对于一个合法的假设，我们记录说假话的人的数量 cnt。

接着再判断一次假设关于 n 的合法性，若 none + cnt < n 或 cnt > n，即加上所有不说话的人说假话的人数仍到不了总说假话人数 n，或不算不说话的人说假话的人数也已经超过总说假话人数 n，则这种假设是不合法的。

经过这些判断后，假设的这个人就可能是罪犯了，我们记录下来。如果当前假设的罪犯和之前的罪犯不一致，则输出 Cannot Determine 并退出。注意若多种情况都能判断出某一个人是罪犯，则不应该输出 Cannot Determine。

把所有的假设都遍历过一遍后，还没有记录过任何答案，则输出 Impossible，否则记录的这个人就是罪犯。

#include <bits/stdc++.h>
using namespace std;
int m, n, p, I; // I 是名字为 I 的人的编号
string s;
map<string, int> name; // 把名字、天数与编号进行转化
map<int, string> reday, ren;
struct node // 含义见前文
{
    int id, day;
    bool rev;
};
vector<node> v[25]; // 记录证言
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> m >> n >> p;
    for (int i = 1; i <= m; i++)
    {
        cin >> s, name[s] = i, ren[i] = s;
        if (s == "I")
            I = i; // 特判名字叫 I 的人
    }
    reday[1] = "Monday.", reday[2] = "Tuesday.", reday[3] = "Wednesday.", reday[4] = "Thursday.", reday[5] = "Friday.", reday[6] = "Saturday.", reday[7] = "Sunday.";
    for (int i = 1; i <= p; i++)
    {
        cin >> s;
        s.pop_back(); // 去冒号
        int u = name[s]; // 记录这句证言谁说的
        cin >> s;
        if (s == "I")
        {
            getline(cin, s);
            while (s.back() == '\r' || s.back() == '\n')
                s.pop_back(); // 防数据的锅
            if (s == " am guilty.")
                v[u].push_back({ u, 0, 0 }); // 如果不是日期类，则第二项为 0，否则为日期编号
            if (s == " am not guilty.")
                v[u].push_back({ u, 0, 1 });
            if (I && s == " is guilty.") // 特判名字叫 I 的人
                v[u].push_back({ I, 0, 0 });
            if (I && s == " is not guilty.")
                v[u].push_back({ I, 0, 1 });
        }
        else if (s == "Today")
        {
            getline(cin, s);
            while (s.back() == '\r' || s.back() == '\n')
                s.pop_back();
            for (int j = 1; j <= 7; j++)
                if (s == " is " + reday[j])
                    v[u].push_back({ u, j, 0 });
        }
        else
        {
            int id = 0;
            for (int j = 1; j <= m; j++)
                if (s == ren[j])
                    id = j; // 找主语
            if (!id) // 非法语句读完直接跳
            {
                getline(cin, s);
                continue;
            }
            getline(cin, s);
            while (s.back() == '\r' || s.back() == '\n')
                s.pop_back();
            if (s == " is guilty.")
                v[u].push_back({ id, 0, 0 });
            if (s == " is not guilty.")
                v[u].push_back({ id, 0, 1 });
        }
    }
    s = ""; // 罪犯名字
    for (int i = 1; i <= m; i++) // 假设编号为 i 的人是罪犯
        for (int d = 1; d <= 7; d++) // 假设今天星期 d
        {
            bool flag = false;
            int cnt = 0, none = 0; // 含义见上文
            for (int j = 1; j <= m; j++) // 遍历所有证言
            {
                int tot = 0; // tot 为假证言的数量
                if (v[j].empty()) // 没说过话加 none 并跳过
                {
                    none++;
                    continue;
                }
                for (auto k : v[j])
                    if (k.day && k.day != d) // 证言日期和假设日期不符 
                        tot++;
                    else if (!k.day && k.rev && k.id == i) // 否定句证言罪犯和实际罪犯相符
                        tot++;
                    else if (!k.day && !k.rev && k.id != i) // 肯定句证言罪犯和实际罪犯不符
                        tot++;
                if (tot == v[j].size()) // 证言全假说假话；证言全真说真话
                    cnt++;
                else if (tot != 0) // 其它情况都不合法
                {
                    flag = true;
                    break;
                }
            }
            if (flag || cnt > n || cnt + none < n) // 判定理由见上文
                continue;
            if (s == "") // 记录罪犯名字
                s = ren[i];
            else if (s == ren[i])
                continue;
            else // 有多个罪犯名字
            {
                cout << "Cannot Determine";
                return 0;
            }
        }
    if (s == "") // 遍历完所有情况都没找到
        cout << "Impossible";
    else
        cout << s;
    return 0;
}