题意：神人鬼三个种族，神只说真话，鬼只说假话，人白天说真话，晚上说假话。根据对话内容区分种族和白天黑夜。 最多有A, B, C, D, E五个人
算法：枚举A, B, C, D, E的种族情况和白天黑夜的情况。每个人有可能是神人鬼，所以用两个bit表示，白天黑夜用1个bit表示。一共需要11 bits.
#include<iostream> #include<cstdio> #include<string> using namespace std; struct statement { char a;//speaker char b;//object 等于状态的偏移量 bool c;//not char d; } p[50]; /* A: I am [not] ( divine | human | evil | lying ). A: X is [not] ( divine | human | evil | lying ). A: It is ( day | night ). */ void get(statement &t) { char c; cin >> c; t.a = c - 'A'; cin >> c >> c; if (c == 'I') { cin.get(c); if (c == 't')//It is t.b = 5;//day|night偏移5 else//I am t.b = t.a; } else t.b = c - 'A';//0-4对应 A-E 5对应day|night string s; cin >> s >> s; if (s == "not") t.c = true, cin >> s; else t.c = false; switch (s[0]) { case 'd': t.d = 0; break;//day divine case 'e': t.d = 2; break;//evil case 'l': t.d = 3; break;//lying default: t.d = 1;//human night } } //human + night = 2 //evil + (day|night) >= 2 bool lying(short state, char who) { return (state >> who*2 & 3) + (state >> 10 & 1) >= 2; } //this is too hard to understand bool check(statement st, short s) { return (st.d == 3 ? lying(s, st.b) : st.d == (s >> st.b + st.b & 3)) ^ st.c ^ lying(s, st.a); } //A-E 每个占2位; day,night 占1位 const int MAX_STATE=1<<11; bool is_valid_state(int s) { for(int i=0;i<5;i++) if((s>>i*2 & 3)==3) return false; return true; } //this is better then check function //判断说话的人是否说谎话 //判断话的内容是否是真的 bool judge(statement st, short s) { //if speaker is lying bool speaker=lying(s, st.a); //if statement is true bool object; //It is ( day | night ). if(st.b==5) { object = (s >> 10 & 1)==st.d; return speaker!=object; } //lying if(st.d==3) { if(st.c) object = !lying(s, st.b); else object = lying(s, st.b); return speaker!=object; } // X is [not] ( divine | human | evil ) object = (s >> st.b*2 & 3)==st.d; return speaker!=object; } //如果状态矛盾，则置为 11b void combine(short &a, short b) { for (int i = 0; i < 6; ++i) if (a & (3 << i + i) ^ b & (3 << i + i)) a |= (3 << i + i); } const char *s[] = { "divine", "human", "evil" }; int main() { #ifndef ONLINE_JUDGE freopen("./uva592.in", "r", stdin); #endif int Kase=0; int n; //printf("%0X ", MAX_STATE); while(cin>>n && n) { cout << "Conversation #" << ++Kase << endl; short a = -1; for(int i=0; i<n; i++) get(p[i]); for(int i=0; i<MAX_STATE; i++) if(is_valid_state(i)) { bool b=true; for (int j=0; j<n; ++j) if (!check(p[j], i)) { b = false; break; } if (!b) continue; if (a == -1) a = i; else combine(a, i); } if (a == -1) cout << "This is impossible." << endl; if (a == 0xFFF) cout << "No facts are deducible." << endl; for (int i = 0; i < 5; ++i) { int x = a>>i*2 & 3; if (x != 3) cout << char(i + 'A') << " is " << s[x] << "." << endl; } int x = a>>10 & 3; if (x != 3) cout << "It is " << (x ? "night." : "day.") << endl; cout << endl; } return 0; }