题解 | 侦探推理-牛客假日团队赛12B题

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

输入描述:

算法知识点: 枚举，模拟，字符串处理
复杂度：

解题思路：

对于比较繁琐的模拟题，写代码的时候建议尽可能模块化。
依次枚举每个同学是否可能是凶手。最终结果有三种：
可能的凶手只有一个，输出凶手名字；
可能的凶手多于一个，输出"Cannot Determine"；
任何一个同学都不可能是凶手，输出"Impossible"；
在枚举每个同学是凶手的过程中，依次枚举今天是星期几，然后判断说谎的同学是否有可能有 n 个。

这里有两点需要注意：
每个同学需要始终如一，如果出现某个同学既说真话又说假话，那么当前枚举的情况不合法；
每个句子有三种情况：真话、假话、废话。最终只要 假话数量 ≤n≤ 假话数量 + 废话数量，那么说谎的同学就有可能有 n 个；

时间复杂度分析:

我们会依次枚举凶手、星期几以及句子，对于每个句子在判断是谁说的时会再循环一遍所有同学，所以总时间复杂度是，其中 M 是总人数，P 是总句子数。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110;
  
int n, m, P;
string sentence[N];
string name[N];
string weekday[7] = {
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};
int state[N];
  
int get_person(string str)
{
    for (int i = 0; i < m; i++)
        if (name[i] == str)
            return i;
    return -1;
}
  
pair <int, string> get(string str)
{
    int t = str.find(":");
    int person = get_person(str.substr(0, t));
    return make_pair(person, str.substr(t + 2));
}
  
int get_state(int bad_man, int day, int now, string line)
{
    if (line == "I am guilty.")
    {
        if (bad_man == now) return 0;
        return 1;
    }
    if (line == "I am not guilty.")
    {
        if (bad_man == now) return 1;
        return 0;
    }
    int t = line.find(" is guilty.");
    if (t != -1)
    {
        int p = get_person(line.substr(0, t));
        if (p == bad_man) return 0;
        return 1;
    }
    t = line.find(" is not guilty.");
    if (t != -1)
    {
        int p = get_person(line.substr(0, t));
        if (p != bad_man) return 0;
        return 1;
    }
  
    for (int i = 0; i < 7; i++)
        if (weekday[i] == line)
        {
            if (i == day) return 0;
            return 1;
        }
  
    return -1;
}
  
bool check(int bad_man, int day)
{
    memset(state, -1, sizeof state);
    for (int i = 0; i < P; i++)
    {
        pair <int, string> t = get(sentence[i]);
        int p = t.first;
        int s = get_state(bad_man, day, p, t.second);
  
        if (s == 0)
        {
            if (state[p] == 1) return false;
            state[p] = s;
        }
        else if (s == 1)
        {
            if (state[p] == 0) return false;
            state[p] = s;
        }
    }
  
    int fake = 0, other = 0;
    for (int i = 0; i < m; i++)
        if (state[i] == 1)
            fake++;
        else if (state[i] == -1)
        other++;
  
    if (fake <= n && fake + other >= n) return true;
    return false;
}
  
int main()
{
    cin >> m >> n >> P;
    for (int i = 0; i < m; i++) cin >> name[i];
    getline(cin, sentence[0]);
    for (int i = 0; i < P; i++) getline(cin, sentence[i]);
  
    int cnt = 0, p;
    for (int i = 0; i < m; i++)
    {
        bool flag = false;
        for (int j = 0; j < 7; j++)
            if (check(i, j))
            {
                flag = true;
                break;
            }
  
        if (flag)
        {
            cnt++;
            p = i;
        }
    }
  
    if (cnt == 1) cout << name[p] << endl;
    else if (cnt > 1) puts("Cannot Determine");
    else puts("Impossible");
  
    return 0;
}