算法

(枚举，模拟，字符串处理) $O(7M^2P)$

对于比较繁琐的模拟题，写代码的时候建议尽可能模块化。

依次枚举每个同学是否可能是凶手。最终结果有三种：

• 可能的凶手只有一个，输出凶手名字；
• 可能的凶手多于一个，输出"Cannot Determine"；
• 任何一个同学都不可能是凶手，输出"Impossible"；

在枚举每个同学是凶手的过程中，依次枚举今天是星期几，然后判断说谎的同学是否有可能有 $n$ 个。

这里有两点需要注意：

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

时间复杂度分析

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

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 20;

int m, n, P;
string name[N];
pair<int, string> sentence[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_id(string str)
{
    for (int i = 0; i < m; i ++ )
        if (str == name[i])
            return i;
    return -1;
}

// 返回0表示真话，返回1表示假话，返回-1表示无意义的话
int judge(int day, int badman, int now, string str)
{
    if (str == "I am guilty.") return badman != now;
    if (str == "I am not guilty.") return badman == now;
    for (int i = 0; i < m; i ++ )
        if (name[i] + " is guilty." == str)
            return i != badman;
    for (int i = 0; i < m; i ++ )
        if (name[i] + " is not guilty." == str)
            return i == badman;
    for (int i = 0; i < 7; i ++ )
        if (weekday[i] == str)
            return day != i;
    return -1;
}

bool check(int day, int badman)
{
    memset(state, -1, sizeof state);

    for (int i = 0; i < P; i ++ )
    {
        pair<int, string> sen = sentence[i];

        int t = judge(day, badman, sen.first, sen.second);
        int p = sen.first;

        if (t == 0) // 这句话是真话
        {
            if (state[p] == -1) state[p] = 0;
            else if (state[p] == 1) return false;
        }
        else if (t == 1) // 这句话是假话
        {
            if (state[p] == -1) state[p] = 1;
            else if (state[p] == 0) return false;
        }
    }

    int fake = 0, other = 0;
    for (int i = 0; i < m; i ++ )
        if (state[i] == 1) fake ++ ;
        else if (state[i] == -1) other ++ ;

    return fake <= n && n <= fake + other;
}

int main()
{
    cin >> m >> n >> P;
    for (int i = 0; i < m; i ++ ) cin >> name[i];
    for (int i = 0; i < P; i ++ )
    {
        string first, second;
        cin >> first;
        first.erase(first.end() - 1);
        getline(cin, second);
        second.erase(second.begin());
        // second.erase(second.end() - 1);      // 注意在洛谷提交时需要加上这一行，因为洛谷的评测数据里多了个行末空格
        sentence[i] = make_pair(get_id(first), second);
    }

    int cnt, p = -1;
    for (int day = 0; day < 7; day ++ )
    {
        cnt = 0;
        for (int i = 0; i < m; i ++ )
            if (check(day, i))
            {
                cnt ++ ;
                p = i;
            }
        if (cnt > 1)
        {
            puts("Cannot Determine");
            break;
        }
    }

    if (cnt <= 1)
    {
        if (p == -1) puts("Impossible");
        else cout << name[p] << endl;
    }

    return 0;
}