OpenJudge NOI 2.1 6188:比饭量

【题目链接】

OpenJudge NOI 2.1 6188:比饭量

【题目考点】

1. 枚举

2. 深搜

【解题思路】

解法1：枚举

每个人有两个断言，正确断言的个数可能是2，1，0。显然3人的饭量也是不同的，这里假设为1，2，3。
题目中说：“饭量和正确断言的个数是反序的关系”，也就是说：饭量越大，断言正确数越少。饭量越小，断言正确数越大。即二者间有如下关系：

即：每个人的饭量数值和正确断言数的加和都等于3。

每个断言可以写成一个关系表达式，该表达式的值为true（1）或false（0），把一个人的断言写成的关系表达式的值加起来，即为正确断言的数量。

例：
A说：B比我吃的多，C和我吃的一样多
设a，b，c为A，B，C的饭量，那么这两个断言可以写为：b > a, c == a。正确断言的数量即为：(b > a) + (c == a)

• 枚举对象：三个人的饭量
• 枚举范围：1，2，3
• 判断条件：三人饭量两两不同，且每个人的饭量数值和正确断言数的加和都等于3。

注：题目中说“按饭量大小输出3个人的顺序”，指的是按升序输出。

解法2：深搜

设三人的饭量是1，2，3，且两两不同。那么3人饭量所有可能的情况数就是3个数的全排列，可以使用深搜来搜索到所有的排列，而后判断每人的断言数是否与饭量顺序相反，如果是，则输出。

【题解代码】

解法1：枚举

#include 
using namespace std;
int main()
{
	int a, b, c;//表示3人的饭量
	for(a = 1; a <= 3; ++a)
	for(b = 1; b <= 3; ++b)
	for(c = 1; c <= 3; ++c)
	{
		if(a != b && a != c && b != c)//两两不同 
		{
			if(a + (b > a) + (c == a) == 3 && 
				b + (a > b) + (a > c) == 3 && 
				c + (c > b) + (b > a) == 3)//每个人的饭量数值和正确断言数的加和都等于3
			{
				if(a < b && a < c && b < c)//升序输出字符序列 
					cout << "ABC";
				else if(a < b && a < c && c < b)
					cout << "ACB";
				else if(b < a && b < c && a < c)
					cout << "BAC";
				else if(b < a && b < c && c < a)
					cout << "BCA";
				else if(c < a && c < b && a < b)
					cout << "CAB";
				else if(c < a && c < b && b < a)
					cout << "CBA";	
				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

解法2：深搜

#include 
using namespace std;
int w[3], p[4];//w[0]:A的饭量 w[1]:B的饭量 w[2]:C的饭量  p[i]:饭量为i的人 
bool vis[4];
function<int()> f[3];//f[i]:求第i人的断言数 
void initFunc()
{
	f[0] = [](){return (w[1] > w[0]) + (w[2] == w[0]);};//B比我吃的多，C和我吃的一样多
	f[1] = [](){return (w[0] > w[1]) + (w[0] > w[2]);};//A比我吃的多，A也比C吃的多
	f[2] = [](){return (w[2] > w[1]) + (w[1] > w[0]);};//我比B吃得多，B比A吃的多。
} 
void dfs(int k)//确定第k个数字 
{
	if(k > 2)//找到解 
	{
		if(f[p[3]]() < f[p[2]]() && f[p[2]]() < f[p[1]]())//如果饭量越大，断言数越少 
		{
			for(int i = 1; i <= 3; ++i)//输出序列 
				cout << char(p[i]+'A');
		}
		return; 
	}
	for(int i = 1; i <= 3; ++i)
	{
		if(vis[i] == false)
		{
			w[k] = i;//k的饭量为i 
			p[i] = k;//饭量为i的人是k 
			vis[i] = true;
			dfs(k+1);
			vis[i] = false;
		}
	}
}
int main()
{
	initFunc();
	dfs(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