思路
- 枚举每个人是罪犯的情况
- 存在星期几会影响结果,所以也要枚举星期几
- 虽然我们知道那几个人一直说假话,但是由于我们并不知道星期几,所以可能会误判(也就是一个人即说真话,又说假话),这种情况出现说明我们假设错误
- 是罪犯的条件:说假话的人人数小于等于n,说假话的加上说废话的大于等于n
参考代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
string name[N];
string sentence[N];
string week[7]=
{
"Today is Monday.",
"Today is Tuesday.",
"Today is Wednesday.",
"Today is Thursday.",
"Today is Friday.",
"Today is Saturday.",
"Today is Sunday.",
};
int n,m,p;
int state[N];//0真1假
int get_person(string str)
{
for(int i=0;i<m;++i){
if(name[i]==str)
return i;
}
return -1;
}
pair<int,string> get(string str)
{
int t=str.find(":");
int p=get_person(str.substr(0,t));
return {p,str.substr(t+2)};
}
int get_state(int bad_man,int day,int now,string str)
{
if(str=="I am guilty."){
if(now==bad_man)return 0;
return 1;
}
if(str=="I am not guilty."){
if(now!=bad_man)return 0;
return 1;
}
int t = str.find(" is guilty.");
if(t!=-1&&t==str.size()-11){
int p = get_person(str.substr(0,t));
if(p==bad_man)return 0;
return 1;
}
t = str.find(" is not guilty.");
if(t!=-1&&t==str.size()-15){
int p = get_person(str.substr(0,t));
if(p!=bad_man)return 0;
return 1;
}
for(int i=0;i<7;++i){
if(str==week[i]){
if(i==day)return 0;
return 1;
}
}
return -1;
}
bool check(int bad_man,int day)
{
memset(state,-1,sizeof state);
for(int i=0;i<p;++i){
auto t = get(sentence[i]);
int p = t.first;
int s = get_state(bad_man,day,p,t.second);
if(s==0){
if(state[p]==1)return false;
state[p]=0;
}
else if(s==1){
if(state[p]==0)return false;
state[p]=1;
}
}
int fake=0,other=0;
for(int i=0;i<m;++i){
if(state[i]==1){
fake++;
}
else if(state[i]==-1){
other++;
}
}
if(fake<=n&&n<=fake+other)return true;
return false;
}
int main()
{
cin>>m>>n>>p;
int res=0,index;
for(int i=0;i<m;++i)cin>>name[i];
getline(cin,sentence[0]);
for(int i=0;i<p;++i)getline(cin,sentence[i]);
for(int i=0;i<m;++i){
bool flag = false;
for(int j=0;j<7;++j){
if(check(i,j)){
flag = true;
break;
}
}
if(flag){
res++;
index=i;
}
}
if(res==1)cout<<name[index]<<endl;
else if(res>1)cout<<"Cannot Determine"<<endl;
else cout<<"Impossible"<<endl;
return 0;
}