题意分析

题目描述了一个逻辑推理问题，涉及三种不同类型的居民：

1. 神（Divine）：总是说真话
2. 恶魔（Evil）：总是说谎
3. 人类（Human）：白天说真话，晚上说谎

每个居民都能识别其他居民的类型。题目要求根据对话内容推断：

• 当前是白天还是晚上？
• 每个说话者的身份（神、人类、恶魔）？

输入格式

• 多组对话，每组以整数n（语句数量）开头
• 每条语句格式为"[说话者]: [陈述]"
• 陈述可能是：
  • 关于自己或他人身份（divine/human/evil/lying）
  • 关于时间（day/night）
• 输入以n=0结束

输出要求

对于每组对话：

1. 如果对话矛盾，输出"This is impossible."
2. 如果无法推断任何事实，输出"No facts are deducible."
3. 否则按字母顺序输出可确定的事实（居民身份+时间）

解题思路

1. 枚举所有可能性：

   • 枚举每个居民可能的身份（3种）和时间（2种）
   • 共需枚举3^5 * 2 = 486种情况（最多5个居民）

2. 验证每种假设：

   • 根据说话者身份和时间判断陈述的真假
   • 检查所有陈述是否自洽

3. 收集确定事实：

   • 统计在所有可行解中都成立的事实
   • 输出唯一确定的信息

正确代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>

using namespace std;

enum Type { DIVINE, HUMAN, EVIL };
enum Time { DAY, NIGHT };

struct Statement {
    char speaker;
    string subject;
    bool isNot;
    string predicate;
};

vector<Statement> parseStatements(int n) {
    vector<Statement> statements;
    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        while (line.empty()) getline(cin, line);
        
        Statement st;
        st.speaker = line[0];
        
        size_t colon = line.find(':');
        string content = line.substr(colon + 2);
        
        size_t notPos = content.find("not");
        st.isNot = (notPos != string::npos);
        
        if (content.find("I am") != string::npos) {
            st.subject = string(1, st.speaker);
        } else if (content.find(" is") != string::npos) {
            st.subject = string(1, content[0]);
        } else if (content.find("It is") != string::npos) {
            st.subject = "It";
        }
        
        size_t predStart = content.find_last_of(' ');
        st.predicate = content.substr(predStart + 1);
        st.predicate.erase(st.predicate.size() - 1); // remove .
        
        statements.push_back(st);
    }
    return statements;
}

bool isConsistent(const map<char, Type>& types, Time time, const vector<Statement>& statements) {
    for (size_t i = 0; i < statements.size(); ++i) {
        const Statement& st = statements[i];
        Type speakerType = types.find(st.speaker)->second;
        
        bool truthValue;
        if (st.subject == "It") {
            truthValue = (st.predicate == "day") == (time == DAY);
        } else {
            Type subjectType = types.find(st.subject[0])->second;
            bool actual;
            if (st.predicate == "divine") actual = (subjectType == DIVINE);
            else if (st.predicate == "human") actual = (subjectType == HUMAN);
            else if (st.predicate == "evil") actual = (subjectType == EVIL);
            else if (st.predicate == "lying") {
                if (subjectType == DIVINE) actual = false;
                else if (subjectType == EVIL) actual = true;
                else actual = (time == NIGHT);
            }
            truthValue = (actual != st.isNot);
        }
        
        bool shouldSpeakTruth;
        if (speakerType == DIVINE) shouldSpeakTruth = true;
        else if (speakerType == EVIL) shouldSpeakTruth = false;
        else shouldSpeakTruth = (time == DAY);
        
        if (shouldSpeakTruth != truthValue) return false;
    }
    return true;
}

void deduceFacts(int n) {
    vector<Statement> statements = parseStatements(n);
    vector<char> speakers;
    for (size_t i = 0; i < statements.size(); ++i) {
        if (find(speakers.begin(), speakers.end(), statements[i].speaker) == speakers.end()) {
            speakers.push_back(statements[i].speaker);
        }
    }
    sort(speakers.begin(), speakers.end());
    
    vector<map<char, Type> > possibleTypes;
    vector<Time> possibleTimes;
    
    // Generate all possible type assignments
    int numSpeakers = speakers.size();
    int numCombinations = 1;
    for (int i = 0; i < numSpeakers; ++i) numCombinations *= 3;
    
    for (int combo = 0; combo < numCombinations; ++combo) {
        map<char, Type> types;
        int temp = combo;
        for (int i = 0; i < numSpeakers; ++i) {
            types[speakers[i]] = static_cast<Type>(temp % 3);
            temp /= 3;
        }
        
        // Check both day and night
        if (isConsistent(types, DAY, statements)) {
            possibleTypes.push_back(types);
            possibleTimes.push_back(DAY);
        }
        if (isConsistent(types, NIGHT, statements)) {
            possibleTypes.push_back(types);
            possibleTimes.push_back(NIGHT);
        }
    }
    
    if (possibleTypes.empty()) {
        cout << "This is impossible." << endl;
        return;
    }
    
    // Find facts that are true in all possible scenarios
    map<char, Type> commonTypes;
    Time commonTime;
    bool timeDeducible = true;
    
    // Initialize with first possibility
    commonTypes = possibleTypes[0];
    commonTime = possibleTimes[0];
    
    for (size_t i = 1; i < possibleTypes.size(); ++i) {
        for (size_t j = 0; j < speakers.size(); ++j) {
            if (possibleTypes[i][speakers[j]] != commonTypes[speakers[j]]) {
                commonTypes[speakers[j]] = HUMAN; // Mark as undeducible
            }
        }
        if (possibleTimes[i] != commonTime) {
            timeDeducible = false;
        }
    }
    
    bool anyFacts = false;
    for (size_t i = 0; i < speakers.size(); ++i) {
        if (commonTypes[speakers[i]] != HUMAN) {
            anyFacts = true;
            cout << speakers[i] << " is ";
            switch (commonTypes[speakers[i]]) {
                case DIVINE: cout << "divine."; break;
                case HUMAN: cout << "human."; break;
                case EVIL: cout << "evil."; break;
            }
            cout << endl;
        }
    }
    
    if (timeDeducible) {
        anyFacts = true;
        cout << "It is " << (commonTime == DAY ? "day" : "night") << "." << endl;
    }
    
    if (!anyFacts) {
        cout << "No facts are deducible." << endl;
    }
}

int main() {
    int n, caseNum = 0;
    while (cin >> n && n != 0) {
        cin.ignore(); // ignore newline after n
        caseNum++;
        cout << "Conversation #" << caseNum << endl;
        deduceFacts(n);
        cout << endl;
    }
    return 0;
}