题意
有 M 个人（人名是大写字母），其中 N 个始终说假话，另外 M-N 个始终说真话，一共有 P 句证词，其中只有 I am guilty.（自己是罪犯）、I am not guilty.（自己不是罪犯）、Y is guilty.（Y 是罪犯）、Y is not guilty.（Y 不是罪犯）和 Today is X.（今天是星期 X）是生效的，其余均无效，其中 Y 是人名，X 是星期单词，取值于 Sunday、Monday、Tuesday、Wednesday、Thursday、Friday 和 Saturday 之间。
如果有一个人可能是罪犯，输出这个人的名字，如果不止一个人可能是罪犯，输出 Cannot Determine，如果没有人可能是罪犯，输出 Impossible。
思路
暴力枚举所有可能的罪犯、星期，根据证词判断可能说假话的人数，一定说真话的记为 0，一定说假话的记为 1，没说话或者只说了无关话的记为 -1。对于每一种可能性，累加非 -1 的数字记为 x，并统计 -1 的个数记为 y，如果 x \le N \le x+y，则说明这个人可能成为罪犯（因为状态为 -1 的人既可能是说真话的人，也可能是说假话的人），这时就不需要继续对这个人枚举星期了，直接枚举下一个人。
最后，如果只有 1 个人可能是罪犯，输出其名字，否则如果至少 2 个人可能是罪犯，输出 Cannot Determine，否则输出 Impossible。
剪枝
提供几种可能的剪枝思路：
- 如果一个人既说了真话也说了假话，那么就说明这种情况不可能（例如枚举到星期三的时候，有一个人既说今天星期三也说今天星期四），直接返回
false。
- 当一个人既说 X 是罪犯，也说 X 不是罪犯，或者说了全部 7 种星期，则一定是不可能的，可以直接输出
Impossible 退出程序。
- 如果已经确定了 2 个人可能成为罪犯，则跳过后面的枚举，直接输出
Cannot Determine。
注意
本题的数据疑似是在 Windows 系统下造的，洛谷的评测环境为 Linux，因此 getline 会多读一个 \r，这时我们要判断字符串末尾是否是空格或控制字符，如果是，把这个字符去掉以免影响后面的判断。
代码
#include<bits/stdc++.h>
using namespace std;
struct word{
string name;
int saying;
string gname="n";
};
string temname;
string said;
int m,n,k;
string name[25];word words[105];
map<string,int>mp;
string realguil="Impossible";
int judge(string saying){
temname="n";
if(saying=="Today is Monday.")return 1;
if(saying=="Today is Tuesday.")return 2;
if(saying=="Today is Wednesday.")return 3;
if(saying=="Today is Thursday.")return 4;
if(saying=="Today is Friday.")return 5;
if(saying=="Today is Saturday.")return 6;
if(saying=="Today is Sunday.")return 7;
if(saying=="I am guilty.")return 1001;
if(saying=="I am not guilty.")return 1000;
if(saying.size()>11&&saying.substr(saying.size()-10,10)=="is guilty."){
temname=saying.substr(0,saying.size()-11);
return 2001;
}
if(saying.size()>15&&saying.substr(saying.size()-14,14)=="is not guilty."){
temname=saying.substr(0,saying.size()-15);
return 2000;
}
return 0;
}
void init(){
for(int i=1;i<=m;i++){
mp[name[i]]=-1;
}
}
bool play(string guil,int week){
init();
int negs=0,sum=0;
for(int i=1;i<=k;i++){
if(!words[i].saying)continue;
if(words[i].saying<1000){
if(words[i].saying!=week){
if(mp[words[i].name]==0)return 0;
mp[words[i].name]=1;
}
else{
if(mp[words[i].name]==1)return 0;
mp[words[i].name]=0;
}
}
else if(words[i].saying<2000){
if(words[i].saying==1001){
if(words[i].name==guil){
if(mp[words[i].name]==1)return 0;
mp[words[i].name]=0;
}
else{
if(mp[words[i].name]==0)return 0;
mp[words[i].name]=1;
}
}
else{
if(words[i].name!=guil){
if(mp[words[i].name]==1)return 0;
mp[words[i].name]=0;
}
else{
if(mp[words[i].name]==0)return 0;
mp[words[i].name]=1;
}
}
}
else{
if(words[i].saying==2001){
if(words[i].gname==guil){
if(mp[words[i].name]==1)return 0;
mp[words[i].name]=0;
}
else{
if(mp[words[i].name]==0)return 0;
mp[words[i].name]=1;
}
}
else{
if(words[i].gname!=guil){
if(mp[words[i].name]==1)return 0;
mp[words[i].name]=0;
}
else{
if(mp[words[i].name]==0)return 0;
mp[words[i].name]=1;
}
}
}
}
for(int i=1;i<=m;i++){
if(mp[name[i]]==-1)negs++;
else sum+=mp[name[i]];
}
if(n>=sum&&n<=sum+negs)return 1;
return 0;
}
int main(){
cin>>m>>n>>k;
for(int i=1;i<=m;i++){
cin>>name[i];
}
for(int i=1;i<=k;i++){
string st;
char sp;
cin>>st;
words[i].name=st.substr(0,st.size()-1); //去掉冒号
sp=getchar();
getline(cin,st);
if(st[st.size()-1]<=32)st=st.substr(0,st.size()-1); //<=32：空格或控制字符
words[i].saying=judge(st);
words[i].gname=temname;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=7;j++){
if(play(name[i],j)){
if(realguil!="Impossible"){
cout<<"Cannot Determine";
return 0;
}
realguil=name[i];
break;
}
}
}
cout<<realguil;
return 0;
}