代码:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int len/*有多少人*/,n/*有多少人说谎*/;
unordered_map<string,bool> day;//天
unordered_map<string,vector<pair<string,int>>> m;//0表示不是罪犯,1表示是罪犯,2表示是天
unordered_map<string,bool> a;//如果该人说谎,为true
vector<string> name;//人
int up=-1;
int qwq=0;
bool qaq=false;
void dfs(){//枚举说谎人
if (qwq==n){//如果说谎人够了
// cout<<up<<":\n";
unordered_map<string,int> today;//1表示一定是这个日子,2表示一定不是这个日子
unordered_map<string,int> t;//1表示一定是这个人,2表示一定不是这个人
for (const auto &item : name){
// cout<<item<<" ";
if (a[item]){//说谎
for (const auto &xinxi : m[item]){
if (xinxi.second==0){//一定是罪犯
int temp=t[xinxi.first];//获取当前人是什么状态
if (temp==0){//没被标记
t[xinxi.first]=1;
}else if (temp==1){
//不操作
}else if (temp==2){//如果冲突
return;
}
}else if (xinxi.second==1){//一定不是罪犯
int temp=t[xinxi.first];//获取当前人是什么状态
if (temp==0){//没被标记
t[xinxi.first]=2;
}else if (temp==1){//如果冲突
return;
}else if (temp==2){
//不操作
}
}else{//一定是错误的天
int temp=today[xinxi.first];
if (temp==1){//这一天是对的
return;
}else if (temp==2){
//不用操作
}else{
today[xinxi.first]=2;
}
}
}
}else{//没说谎
for (const auto &xinxi : m[item]){
if (xinxi.second==1){//一定是罪犯
int temp=t[xinxi.first];//获取当前人是什么状态
if (temp==0){//没被标记
t[xinxi.first]=1;
}else if (temp==1){
//不操作
}else if (temp==2){//如果一定不是这个人
return;
}
}else if (xinxi.second==0){//一定不是罪犯
int temp=t[xinxi.first];//获取当前人是什么状态
if (temp==0){//没被标记
t[xinxi.first]=2;
}else if (temp==1){//如果一定是这个人
return;
}else if (temp==2){
//不操作
}
}else{//一定是正确的天
int temp=today[xinxi.first];
if (temp==2){//这一天是错的
return;
}else if (temp==1){
//不用操作
}else{
today[xinxi.first]=1;
}
}
}
}
}
int sm1=0,sm2=0;
// cout<<sm1<<" "<<sm2<<endl;
for (const auto &item : today){
if (item.second==1){
++sm1;
}
}
for (const auto &item : t){
if (item.second==1){
++sm2;
}
}
if (sm2>1 && sm1<=1){
qaq=true;
}
if (sm1<=1 && sm2==1){
for (const auto &item : t){
if (item.second==1){
cout<<item.first<<endl;
exit(0);
}
}
}
return;
}
for (int i=up+1;i<len;++i){
++qwq;
a[name[i]]=true;
int tee=up;
up=i;
dfs();
up=tee;
a[name[i]]=false;
--qwq;
}
}
int main(){
int p;
cin >> len >> n >> p;
day["Monday."]=true,day["Tuesday."]=true,day["Wednesday."]=true,day["Friday."]=true,day["Saturday."]=true;
day["Sunday."]=true,day["Thursday."];
unordered_map<string,bool> f;
for (int i=0;i<len;++i){
string str;
cin >> str;
name.emplace_back(str);
f[name[i]]=true;
}
getchar();
for (int _=0;_<p;++_){
string str;
getline(cin,str);
vector<string> a;
string t;
for (int i=0;i<str.size();++i){//操作
if (str[i]==' '){
a.emplace_back(t);
t="";
continue;
}
t=t+str[i];
}
a.emplace_back(t);
a[0].pop_back();
if (a.size()==4 && a[1]=="I" && a[2]=="am" && a[3]=="guilty."){//计算哪一类
m[a[0]].emplace_back(a[0],1);
}else if (a.size()==5 && a[1]=="I" && a[2]=="am" && a[3]=="not" && a[4]=="guilty."){
m[a[0]].emplace_back(a[0],0);
}else if (a.size()==4 && f[a[1]] && a[2]=="is" && a[3]=="guilty."){
m[a[0]].emplace_back(a[1],1);
}else if (a.size()==5 && f[a[1]] && a[2]=="is" && a[3]=="not" && a[4]=="guilty."){
m[a[0]].emplace_back(a[1],0);
}else if (a.size()==4 && a[1]=="Today" && a[2]=="is" && day[a[3]]){
m[a[0]].emplace_back(a[1],2);
}
}
/*debug
for (const auto &item : m){
cout<<item.first<<":";
for (const auto &item2 : item.second){
cout<<item2.first<<" "<<item2.second<<"|";
}
cout<<endl;
}
*/
dfs();
if (qaq){
cout<<"Cannot Determine\n";
}else{
cout<<"Impossible\n";
}
return 0;
}
目前只有不可以总司令对了(只输出 Impossible 的点对了),第一个数据下了的,为啥我在 Dev 和洛谷 IDE 都能过洛谷不能过,能解释为啥吗/kk