PAT Basic Level 1089 狼人杀-简单版 解题思路及AC代码 v0.96

PAT 乙级 1089 狼人杀-简单版

1. 题目简述及在线测试位置

1.1 N个人玩狼人杀,每个人 按从1到N的编号 顺序说明他人的身份,已知 N个人里面有两个狼人、有两个人在描述他人身份时说了谎话、只有一个狼人说了谎话,根据上述信息判断出谁是狼人
1.2 在线测试位置: 1089 狼人杀-简单版

2. 基本思路

2.0 想破头系列:一开始按求解数学题的思路去编码:第一个人可能有四种状态(人说真话、人说假话、狼说真话、狼说假话),按设定的状态逐步进行推导,发现根本编不下去啊… 最后发现正确的姿势应该是: 类似解方程(找到规律/方程式),用所有已知条件去尝试(计算机擅长啊),找到满足规律/方程式的条件
2.1 最终的结果需要满足 身份描述(其中两个人说了谎话,这两个人中一个是狼人),将身份描述信息存储到整型数组中。例如,PeopleWord[1]=6 第一个玩家说第六个玩家是人;PeopleWord[3]=-4 第三个玩家说第四个玩家扮演狼人

	for (int i = 1; i <= N; i++)
	{
		cin >> Data;
		PeopleWord[i] = Data; 
	}

2.2 通过计算机可以遍历所有可能的狼人组合:-1 -2,-1 -3 ,-1 -4 等等,狼人身份确定,每个人的身份状态也就随之确定了

	for (i = 1; i < N; i++)
	{
		for (j = i + 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
				Status[i] = 1;
			Status[i] = Status[j] = -1;
		}
	}		

2.3 将每个人的身份状态 与 身份描述信息 进行比对:当身份描述信息 和 身份状态不一致时,说明身份状态对应的述说者在说谎

CountLiar = 0;
for (int k = 1; k <= N; k++)
{
	int tmp = PeopleWord[k];//the k said

	if ( Status[Abs(tmp)] * tmp < 0 ) //standard for tell lies
		Liar[CountLiar++] = k; //k tell lies
}

2.4 当满足 说谎人数是2人 且 仅其中一人扮演狼人时,说明每个人的身份状态都是正确的,即找到了答案

if (CountLiar == 2 )
{
		if ((Liar[0] == i || Liar[0] == j) && (Liar[1] != i && Liar[1] != j))
		{
			cout << i << " " << j << endl;
			return 0;
		}					
		else if ((Liar[1] == i || Liar[1] == j) && (Liar[0] != i && Liar[0] != j))
		{
			cout << i << " " << j << endl;
			return 0;
		}
	}		

2.5 由于是从小到大遍历的,因此找到的第一个满足条件的结果就是题目所要求的最小序列

3. 完整AC代码

#include <iostream>
using namespace std;

#define MAX 101

int Abs(int n);

int main()
{
	int PeopleWord[MAX]; //存储每个人的描述
	int N,Data;

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> Data;
		PeopleWord[i] = Data;
	}
	
	short Status[MAX]; //存储身份状态的数组
	short Liar[MAX],CountLiar ; //统计说谎者  Liar数组计数器
		
	int i, j;
	for (i = 1; i < N; i++)
	{
		for (j = i + 1; j <= N; j++) //通过两层循环,遍历所有可能的狼人组合
		{
			//初始化
			for (int i = 1; i <= N; i++)
				Status[i] = 1;
			CountLiar = 0;
			Status[i] = Status[j] = -1; //狼人

			for (int k = 1; k <= N; k++)
			{
				int tmp = PeopleWord[k];//the k said
	
				if ( Status[Abs(tmp)] * tmp < 0 ) //standard for tell lies
					Liar[CountLiar++] = k; //k tell lies
			}

			if (CountLiar == 2 )
			{
				if ((Liar[0] == i || Liar[0] == j) && (Liar[1] != i && Liar[1] != j))
				{
					cout << i << " " << j << endl;
					return 0;
				}					
				else if ((Liar[1] == i || Liar[1] == j) && (Liar[0] != i && Liar[0] != j))
				{
					cout << i << " " << j << endl;
					return 0;
				}
			}			
		}
	}

	cout << "No Solution";

	return 0;
}

int Abs(int n)
{
	if (n < 0)
		return n * -1;
	else
		return n;
}
上一篇:Codeforces Round #572(div2)部分题解(A~C,E)


下一篇:AcWing 760. 字符串长度