OpenJudge NOI 2.1 2673:比赛排名

OpenJudge NOI 2.1 2673:比赛排名

【题目链接】

OpenJudge NOI 2.1 2673:比赛排名

【题目考点】

1. 枚举

2. function

头文件：<functional>（已被万能头包含）
使用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：枚举 使用多个变量，设函数判断

设整型变量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;
}

对于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<bool()>类型的数组fun，fun[i]表示的函数功能为：判断第i个人说的话是否是正确的。给fun[i]设值时，可以分别先写函数再赋值，也可以写lambda表达式。
当搜索得到一个1~5的排列，也就是确定了每个人的名次后，使用函数判断是否满足：第1，2名的人说的话是真的，而且第3,4,5名的人说的话是假的。如果满足，那么输出结果。

【题解代码】

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

#include<bits/stdc++.h>
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;
}

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

#include<bits/stdc++.h>
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;} }elsedfs(k+1);vis[i] = false;}}
}
int main()
{initFun();dfs(1);return 0;
}