题解：P1039 [NOIP 2003 提高组] 侦探推理

~~很像小学学某思的奥数题。~~

但是我们的计算机可没有所谓机灵的脑袋，那就枚举所有情景。

模拟每个人是罪犯和今天的日期，模拟每一句话，发现始终说谎的人数。

如果有人真假话都说或者大于

N

个直接跳过该情景。

如果发现和前面情景推定的凶手不同或者有多个凶手可能性即输出 Cannot Determine。

如果所有情景都没有凶手即输出 Impossible。

否则即输出名字。

这边输入与判断建议用 string，容易发现 string 比较好比较，插入也很方便。

假设该字符串为

y

，删除最后一个字符用 y.erase(y.length()-1,1);。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int num[25],rub[105];
int n,m,p,wer=0,tf[21];
string name[21];
string bish[105],ans[21];
void dat(int x,int y)
{
	int i,j,t=0,f=0;
	for(i=0;i<p;i++)
	{
		int flag;
		if(bish[i]=="Today is Monday.")
		{
			if(y==1)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Tuesday.")
		{
			if(y==2)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Wednesday.")
		{
			if(y==3)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Thursday.")
		{
			if(y==4)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Friday.")
		{
			if(y==5)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Saturday.")
		{
			if(y==6)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="Today is Sunday.")
		{
			if(y==7)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="I am guilty.")
		{
			if(rub[i]==x)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		if(bish[i]=="I am not guilty.")
		{
			if(rub[i]!=x)flag=1;
			else flag=0;
			if(tf[rub[i]]==-1)tf[rub[i]]=flag;
			if(tf[rub[i]]!=flag)return;
		}
		for(j=0;j<m;j++)
		{
			string d=name[j]+" is guilty.";
			if(d==bish[i])
			{
				if(j==x)flag=1;
				else flag=0;
				if(tf[rub[i]]==-1)tf[rub[i]]=flag;
				if(tf[rub[i]]!=flag)return;
			}
		}
		for(j=0;j<m;j++)
		{
			string d=name[j]+" is not guilty.";
			if(d==bish[i])
			{
				if(j!=x)flag=1;
				else flag=0;
				if(tf[rub[i]]==-1)tf[rub[i]]=flag;
				if(tf[rub[i]]!=flag)return;
			}
		}
	}
	for(i=0;i<m;i++)
	{
		if(tf[i]==1)t++;
		if(tf[i]==0)f++;
	}
	if(f>n||t>m-n)return;
	ans[wer++]=name[x];
}
int main()
{
	int i,j;
	scanf("%d%d%d",&m,&n,&p);
	for(i=0;i<m;i++)
		cin>>name[i];
	for(i=0;i<p;i++)
	{
		string x,y;
		cin>>x;
		x.erase(x.length()-1,1);
		for(j=0;j<m;j++)
			if(name[j]==x)rub[i]=j;
		getline(cin,y);
		y.erase(0,1);
		if(y[y.length()-1]=='\n'||y[y.length()-1]=='\r')
			y.erase(y.length()-1,1);
		bish[i]=y;
	}
	for(i=0;i<m;i++)
	{
		for(j=1;j<=7;j++)
		{
			memset(tf,-1,sizeof(tf));
			dat(i,j);
		}
	}
	if(wer<1)
	{
		printf("Impossible");
		return 0;
	}
	string lan=ans[0];
	for(i=1;i<wer;i++)
	{
		if(ans[i]!=lan)
		{
			printf("Cannot Determine");
			return 0;
		}
	}
	cout<<lan;
	return 0;
}

如果你想要珍惜自己的生命这边建议直接跳过该题。

题解：P1039 [NOIP 2003 提高组] 侦探推理

文章操作

Code

相关推荐

评论

题解：P1039 [NOIP 2003 提高组] 侦探推理