10pts求助大佬
查看原帖
10pts求助大佬
890311
xiaoyang111楼主2023/10/10 22:39

代码:

#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

2023/10/10 22:39
加载中...