思路与算法

枚举唯一罪犯和星期。对每个识别到的证词求真假；同一说话者的全部有效证词必须全真或全假，有矛盾则该假设不成立。统计被迫说谎人数L，以及没有任何有效证词的人数U，恰好N人说谎可行当且仅当L≤N≤L+U。收集能在任意星期成立的罪犯，按0、1、多个分别输出Impossible、名字、Cannot Determine。

正确性说明

罪犯和星期给定后，每条规定格式证词的真值唯一确定。真话者不能说假证词、说谎者不能说真证词，所以一个人证词真假混杂必不可能；一致时身份被唯一确定。没有有效证词者可以任选身份，只需从U人中选N-L个说谎者，区间条件正好充要。枚举全部罪犯与七天穷尽所有世界，收集结果就准确表达唯一性。

复杂度

O(7MPL+7M²)时间、O(M+PL)空间，L≤250为证词长度；包含姓名字典、证词解析和每个假设的身份数组初始化。

易错点

非规定格式的话必须忽略，不能当作假话。罪犯不一定说谎；一天未知但所有人的星期证词指同一天。原样例全角句号按普通句号识别，冒号后有无空格都能读入。证词表图片已核对并随题包保留。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Statement {
    int who, type, arg;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N, P;
    cin >> M >> N >> P;
    vector<string> names(M);
    map<string, int> id;
    for (int i = 0; i < M; i++) {
        cin >> names[i];
        id[names[i]] = i;
    }
    vector<string> days = {"Monday", "Tuesday",  "Wednesday", "Thursday",
                           "Friday", "Saturday", "Sunday"};
    string line;
    getline(cin, line);
    vector<Statement> st;
    for (int i = 0; i < P; i++) {
        getline(cin, line);
        string full = "．";
        size_t pos;
        while ((pos = line.find(full)) != string::npos)
            line.replace(pos, full.size(), ".");
        auto colon = line.find(':');
        string who = line.substr(0, colon), text = line.substr(colon + 1);
        while (!text.empty() && text.front() == ' ')
            text.erase(text.begin());
        if (text == "I am guilty.")
            st.push_back({id.at(who), 0, id.at(who)});
        else if (text == "I am not guilty.")
            st.push_back({id.at(who), 1, id.at(who)});
        else {
            bool done = false;
            for (auto x : id) {
                if (text == x.first + " is guilty.") {
                    st.push_back({id.at(who), 0, x.second});
                    done = true;
                } else if (text == x.first + " is not guilty.") {
                    st.push_back({id.at(who), 1, x.second});
                    done = true;
                }
            }
            if (!done)
                for (int d = 0; d < 7; d++)
                    if (text == "Today is " + days[d] + ".")
                        st.push_back({id.at(who), 2, d});
        }
    }
    vector<int> possible;
    for (int guilty = 0; guilty < M; guilty++) {
        bool found = false;
        for (int day = 0; day < 7; day++) {
            vector<int> truth(M, -1);
            bool ok = true;
            for (auto s : st) {
                int value =
                    s.type == 2 ? day == s.arg : (s.type == 0 ? guilty == s.arg : guilty != s.arg);
                if (truth[s.who] >= 0 && truth[s.who] != value) {
                    ok = false;
                    break;
                }
                truth[s.who] = value;
            }
            int lies = count(truth.begin(), truth.end(), 0),
                unknown = count(truth.begin(), truth.end(), -1);
            if (ok && lies <= N && N <= lies + unknown) {
                found = true;
                break;
            }
        }
        if (found)
            possible.push_back(guilty);
    }
    if (possible.empty())
        cout << "Impossible\n";
    else if (possible.size() > 1)
        cout << "Cannot Determine\n";
    else
        cout << names[possible[0]] << "\n";
}