刷题记录:牛客:NC16680or洛谷P1039

传送门:洛谷,牛客
题目概要:

说实话在刚刚看到这道题的时候我的心里是毫无思路,甚至感觉十分的麻烦
讲述一下第一眼的思路:设置一个vis数组,记录每一个人说的话(记录每一个人的罪犯指向,然后试着枚举一下每一句话是不是假话,然后在逐个判断是不是正确,然后想着想着就觉得越来越麻烦,感觉根本无法实现,这种思路就想是人思考时的那样跳来跳去,用代码感觉很难实现)

看了题解之后豁然开朗,焯,我可以直接枚举每个人是不是罪犯和,当前的是星期几啊,然后根据每个人对当前日期和罪犯的描述来判断是不是合理即可,虽然也是大模拟(用了150多行)

vis[i]=1表示当前描述是正确的
vis[i]=0 表示当前描述是不确定的,即无用言论
vis[i]=-1 表示当前描述与假设不符合

判断条件:若一个人既说谎又没有说谎,那么这个枚举的情况就是错误的

注意点:即使是无用言论,也可能是说谎的,不要忘记了这点(也就是说 说无用言论的人我们也可以将其加入真话或者假话的行列之中,随情况而定)

ps:下面代码判断vis之后都可以加上break;但是因为调试方便原因,我下面代码是没有加上的

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	int x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
/*
下面是本体代码,上面是无用代码
*/
string name[200],say[200];
string Name,Say;int w[200];
int vis[200];
//因为就那么几个星期,直接记录下来,以后好判断,这里我将Sunday放在第一个是因为样例中出现了Sunday,为了更好的调试代码(毕竟是**模拟)
string day[10]={"Today is Sunday.","Today is Monday.","Today is Tuesday.","Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday."};
int main() {
	int M,N,P;
	cin>>M>>P>>N;
	for(int i=1;i<=M;i++) cin>>name[i];
	for(int i=1;i<=N;i++) {
		cin>>Name;
		Name.erase(Name.end()-1);//去掉末尾的冒号
		for(int j=1;j<=M;j++) {//记录当前的描述是哪位人士描述的
			if(Name==name[j]) {
				w[i]=j;
			}
		} 
		//因为cin是会被空格打断的,所以我们要记录一整句带空格的话就需要用getline来读取
		getline(cin,say[i]);
		say[i].erase(say[i].begin());//去掉说的话之前的空格
//下面这句话是为了读取样例中不知为何存在的换行符,在洛谷中有用
//在牛客网中不需要
//		say[i].erase(say[i].end()-1);
	}
	//可能有多个可能的罪犯,用nzf来记录之前有没有符合的罪犯
	int nzf=0;
	for(int i=0;i<=6;i++) {//枚举正确的星期 
	//枚举正确的罪犯
		for(int zf=1;zf<=M;zf++) {
			memset(vis,0,sizeof(vis));
			int flag=0;
			for(int j=1;j<=N;j++) {
				if(say[j]=="I am guilty."){
				//如果当前是假定的罪犯,自己说自己是罪犯即描述是正确的反之则错误
					if(w[j]==zf) {
						if(vis[w[j]]==-1) {
							flag=1;//表示错误	
//							break;
						}else {
							vis[w[j]]=1;
						}
					}else {/如果当前不是罪犯,逻辑取反即可
						if(vis[w[j]]==1) {
							flag=1;//break;
						}else {
							vis[w[j]]=-1;
						}
					}
					
				} 
				//如果说自己不是罪犯,思路跟上面一样
				else if(say[j]=="I am not guilty.") {
					if(w[j]==zf) {
						if(vis[w[j]]==1) {
							flag=1;//break;
						}else {
							vis[w[j]]=-1;
						}
					}else {
						if(vis[w[j]]==-1) {
							flag=1;//break;
						}else {
							vis[w[j]]=1;
						}
					}
				}
				//枚举当前描述中的日期
				for(int ii=0;ii<=6;ii++) {
				//判断当前时期跟描述中的是不是一样的
					if(say[j]==day[ii]) {
						if(day[ii]==day[i]) {
							if(vis[w[j]]==-1) {
								flag=1;//break;
							}else {
								vis[w[j]]=1;
							}
						}else {
							if(vis[w[j]]==1) {
								flag=1;//break;
							}else {
								vis[w[j]]=-1;
							}
						}
					}
				}
				//如果指认其他人为罪犯
				for(int ii=1;ii<=M;ii++) {
					if(say[j]==name[ii]+" is guilty.") {
						if(ii==zf) {
							if(vis[w[j]]==-1) {
								flag=1;//break;
							}else {
								vis[w[j]]=1;
							} 
						}else {
							if(vis[w[j]]==1) {
								flag=1;//break;
							}else {
								vis[w[j]]=-1;
							}
						}
					}
					//思路同上
					else if(say[j]==name[ii]+" is not guilty.") {
						if(ii==zf) {
							if(vis[w[j]]==1) {
								flag=1;//break;
							}else {
								vis[w[j]]=-1;
							}
						}else {
							if(vis[w[j]]==-1) {
								flag=1;//break;
							}else {
								vis[w[j]]=1;
							}
						}
					}
				}				
//				for(int ii=1;ii<=M;ii++) cout<<vis[ii]<" ";
//				cout<<flag;
//				cout<<endl;
			}
			//cnt1用来记录说谎的人数
			//cnt2记录说废话的人数
			int cnt1=0,cnt2=0;
			for(int j=1;j<=M;j++) {
				if(vis[j]==-1) cnt1++;
				else if(vis[j]==0) cnt2++;
			}
			if(cnt1<=P&&cnt1+cnt2>=P&&flag==0) {
				if(nzf!=zf&&nzf!=0) {
					cout<<"Cannot Determine";
					return 0;
				}else {
					nzf=zf;
				}
			}
		}
	}
	if(nzf==0) cout<<"Impossible";
	else cout<<name[nzf];
	return 0;
}