OpenJudge NOI 2.1 2673:比赛排名

【题目链接】

OpenJudge NOI 2.1 2673:比赛排名

【题目考点】

1. 枚举

2. function

头文件：（已被万能头包含）
使用function类可以定义函数对象
格式：function<函数返回值类型(参数类型列表)> 函数对象名
示例：

function<int(int,int)> f1 = fun;//函数名（函数指针）
function<int(int,int)> f2 = Fun();//仿函数对象，仿函数类名为Fun
function<int(int,int)> f3 = [](int a,int b){return a*b;};//lambda表达式
1
2
3

【解题思路】

解法1：枚举 使用多个变量，设函数判断

设整型变量a,b,c,d,e分别表示选手A,B,C,D,E的名次。

• 枚举对象：a,b,c,d,e
• 枚举范围：1到5
• 判断条件：名次两两不同，e不是第2名或第3名，且第1、2名说的条件为真，其他人说的条件为假

具体做法：

1. a,b,c,d,e都从1到5遍历，枚举所有可能的情况。
2. 排除掉5个变量中存在两个变量值相等的情况。
3. 写函数check()判断每个人说的话，思路为：
   记x为某个人。
   • 如果x是第1或2名，那么x说的话一定为真。如果x说的话为假，那么该名次序列不符合条件。
   • 如果x不是第1名且不是第2名，那么x说的话一定为假。如果x说的话为真，那么该名次序列不符合条件。

例：a说的话是：e是第1名，也就是e == 1
如果a是第1或第2名，那么a说的话为真，e一定的第1名。如果e不是不是第1名，则不符合条件。
如果a不是第1名且不是第2名，那么a说的话为假，e一定不是第1名。如果e是第1名，则不符合条件。
写成代码为：

if(a == 1 || a == 2)//如果a是第1或第2名 
{//那么a说的话为真，e一定的第1名
	if(e != 1)//如果e不是不是第一名，则不符合条件。 
		return false;
}
else//如果a不是第1名且不是第2名 
{//那么a说的话为假，e一定不是第1名
	if(e == 1)//如果e是第1名，则不符合条件。 
		return false;
}
1
2
3
4
5
6
7
8
9
10

对于c，d，e说的话，都可以使用类似的方法进行判断。
对于b的情况，如果b是第1名，这和他说的“我是第2名”矛盾，因此b一定不是第1名。如果b不是前两名，那么他说的“我是第2名”自然为假，不矛盾。
check函数运行到最后也没有在前面设置的return false处返回，那么返回true。表示这组数字满足条件。
4. 如果check函数返回true，那么输出每个人的名次。

解法2：深搜 存储函数判断每个人说的话

a,b,c,d,e五个人所有可能的名次序列就是1~5的全排列，可以用深搜的方法得到5个数字的全排列。
该写法需要用到存储函数的技术，可以选择使用函数指针（C语言）或function（C++11)，这里使用function。
设一个function类型的数组fun，fun[i]表示的函数功能为：判断第i个人说的话是否是正确的。给fun[i]设值时，可以分别先写函数再赋值，也可以写lambda表达式。
当搜索得到一个1~5的排列，也就是确定了每个人的名次后，使用函数判断是否满足：第1，2名的人说的话是真的，而且第3,4,5名的人说的话是假的。如果满足，那么输出结果。

【题解代码】

解法1：枚举 使用多个变量，设函数判断

#include
using namespace std;
int a, b, c, d, e;
bool check()
{
	if(e == 2 || e == 3)//如果e是第2名或第3名，不符合条件 
		return false;
	if(a == 1 || a == 2)
	{
		if(e != 1)
			return false;
	}
	else
	{
		if(e == 1)
			return false;
	}
	if(b == 1)
		return false;
	if(c == 1 || c == 2)
	{
		if(a != 5)
			return false;
	} 
	else
	{
		if(a == 5)
			return false;
	}
	if(d == 1 || d == 2)
	{
		if(c == 1)
			return false;
	}
	else
	{
		if(c != 1)
			return false;
	}
	if(e == 1 || e == 2)
	{
		if(d != 1)
			return false;
	}
	else
	{
		if(d == 1)
			return false;
	}
	return true;
}
int main()
{
	for(a = 1; a <= 5; ++a)
	for(b = 1; b <= 5; ++b)
	for(c = 1; c <= 5; ++c)
	for(d = 1; d <= 5; ++d)
	for(e = 1; e <= 5; ++e)
	{
		if(a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
		{//如果两两不同 
			if(check())
			{
				cout << a << endl << b << endl << c << endl << d << endl << e;
				return 0;
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

解法2：深搜 存储函数判断每个人说的话

#include
using namespace std;
int rk[6];//rk[i]:第i名是谁rk[i]-1+'a'，(a:1, b:2, c:3, d:4, e:5) 
bool vis[6];//vis[i]:名次i是否已经使用过
bool isOver;//是否已经输出解 
function<bool()> fun[6];
void initFun()
{//使用lambda表达式创建函数并赋值给fun数组中的元素 
	fun[1] = [](){return rk[1] == 5;};//a说：e是第1名 
	fun[2] = [](){return rk[2] == 2;};//b说：b是第2名 
	fun[3] = [](){return rk[5] == 1;};//c说：a是第5名 
	fun[4] = [](){return rk[1] != 3;};//d说：c不是第1名 
	fun[5] = [](){return rk[1] == 4;};//e说：d是第1名 
}
void dfs(int k)//确定第k人的名次 
{
	if(isOver)
		return;
	for(int i = 1; i <= 5; ++i)
	{
		if(vis[i] == false)
		{
			vis[i] = true;
			rk[k] = i;
			if(k == 5)
			{
				if(rk[2] != 5 && rk[3] != 5 && fun[rk[1]]() && fun[rk[2]]() && !fun[rk[3]]() && !fun[rk[4]]() && !fun[rk[5]]())
				{//如果e不是第2名或第3名，且第1，2名说得对，第3,4,5名说得不对
					int ans[6];//ans[i]:i-1+'A'的名次 
					for(int i = 1; i <= 5; ++i)
						ans[rk[i]] = i;//rk[i]这个人的名次是i 
					for(int i = 1; i <= 5; ++i)//输出每个人的名次 
						cout << ans[i] << endl;
					isOver = true;
					return;
				} 
			}
			else
				dfs(k+1);
			vis[i] = false;
		}
	}
}
int main()
{
	initFun();
	dfs(1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49