问题描述
某场比赛过后，你想要知道A~E五个人的排名是什么，于是要求他们每个人说了一句话。（经典的开头……-_-!）得了第1名的人23，说了假话；得了第5名的人不好意思，也说了假话；为了使求解问题简单，第3名同样说了假话。（奇数名次说假话）
输入格式
共5行，各行依次表示A~E说的话。
每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。
大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！
输出格式
可能有多解，请按照字典序输出排名序列，每个解一行
最后一行输出解的数量
样例输入
A=2
D=5
E>3
A>2
B!=1
样例输出
ACDEB
AECBD
BADCE
BCADE
BDACE
CEADB
CEBDA
7
分析：1.用全排列公式，枚举除所有可能的排序，检查每个排序是否符合要求
2.检查每种名次，如果出现了奇数名次的人说了真话，该序列不符合，如果偶数名次的人说了假话，也不符合～
|
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 |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cmath> using namespace std; string ranks = "ABCDE"; vector<string> say(5); int cnt; bool check(string s) { int hash[150] = {0}; for (int i = 0; i < 5; i++) hash[s[i]] = i + 1; for (int i = 0; i < 5; i++) { string sayt = say[i]; int len = sayt.length(); if (hash['A' + i] % 2 == 1) { if (sayt[1] == '=' && hash[sayt[0]] == sayt[len - 1] - '0') return false; if (sayt[1] == '!' && hash[sayt[0]] != sayt[len - 1] - '0') return false; if (len == 3 && sayt[1] == '<' && hash[sayt[0]] < sayt[len - 1] - '0') return false; if (len == 3 && sayt[1] == '>' && hash[sayt[0]] > sayt[len - 1] - '0') return false; if (len == 4 && sayt[1] == '>' && hash[sayt[0]] >= sayt[len - 1] - '0') return false; if (len == 4 && sayt[1] == '<' && hash[sayt[0]] <= sayt[len - 1] - '0') return false; } else { if (sayt[1] == '=' && hash[sayt[0]] != sayt[len - 1] - '0') return false; if (sayt[1] == '!' && hash[sayt[0]] == sayt[len - 1] - '0') return false; if (len == 3 && sayt[1] == '<' && hash[sayt[0]] >= sayt[len - 1] - '0') return false; if (len == 3 && sayt[1] == '>' && hash[sayt[0]] <= sayt[len - 1] - '0') return false; if (len == 4 && sayt[1] == '>' && hash[sayt[0]] < sayt[len - 1] - '0') return false; if (len == 4 && sayt[1] == '<' && hash[sayt[0]] > sayt[say[i].length() - 1] - '0') return false; } } cnt++; return true; } int main() { for (int i = 0; i < 5; i++) cin >> say[i]; do { if (check(ranks)) cout << ranks << endl; } while (next_permutation(ranks.begin(), ranks.end())); cout << cnt; return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
