OpenJudgeNOI2.16188:比饭量-创新互联

【题目链接】

OpenJudge NOI 2.1 6188:比饭量

10年积累的成都网站制作、网站设计经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有方正免费网站建设让你可以放心的选择与我们合作。【题目考点】 1. 枚举 2. 深搜【解题思路】解法1：枚举

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

饭量	正确断言数
3	0
2	1
1	2

即：每个人的饭量数值和正确断言数的加和都等于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：枚举

#includeusing 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;
}

解法2：深搜

#includeusing namespace std;
int w[3], p[4];//w[0]:A的饭量 w[1]:B的饭量 w[2]:C的饭量  p[i]:饭量为i的人 
bool vis[4];
functionf[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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前标题：OpenJudgeNOI2.16188:比饭量-创新互联
网页链接：http://6mz.cn/article/ecjhe.html

网站建设知识

OpenJudgeNOI2.16188:比饭量-创新互联

其他资讯