今天在公众号上看到某刑侦科虐哭无数人的烧脑神题,感觉挺好玩的,直接编写了程序来求解,问题和求解如下
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <unordered_map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <memory>
using namespace std;
class Problem{
private:
int m_id;
char m_answer;
public:
Problem(const int id, const char answer='A') : m_id(id), m_answer(answer){}
int id() const { return m_id; }
char answer() const { return m_answer; }
void set_answer(const char answer){ m_answer = answer; }
};
class ProblemCheck{
public:
virtual bool check(const Problem & problem, const vector<Problem> & problems) = 0;
};
class Check_one : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
return true;
}
};
class Check_two : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, char> answer;
answer['A'] = 'C'; answer['B'] = 'D';
answer['C'] = 'A'; answer['D'] = 'B';
return answer[problem.answer()] == problems[4].answer();
}
};
class Check_three : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_set<char> record;
unordered_map<char, int> id;
id['A'] = 2; id['B'] = 5;
id['C'] = 1; id['D'] = 3;
for(char ch : {'A', 'B', 'C', 'D'}){
if (ch != problem.answer()){
record.insert( problems[ id[ch] ].answer() );
}
}
return record.find(problem.answer()) == record.end();
}
};
class Check_four : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, bool> judge_answer;
judge_answer['A'] = problems[0].answer() == problems[4].answer();
judge_answer['B'] = problems[1].answer() == problems[6].answer();
judge_answer['C'] = problems[0].answer() == problems[8].answer();
judge_answer['D'] = problems[5].answer() == problems[9].answer();
return judge_answer[problem.answer()];
}
};
class Check_five : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, int> equal_problem;
equal_problem['A'] = 7; equal_problem['B'] = 3;
equal_problem['C'] = 8; equal_problem['D'] = 6;
return problem.answer() == problems[equal_problem[problem.answer()]].answer();
}
};
class Check_six : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
char tmp_ans = problems[7].answer();
unordered_map<char, bool> judge_answer;
judge_answer['A'] = problems[1].answer() == tmp_ans and problems[3].answer() == tmp_ans;
judge_answer['B'] = problems[0].answer() == tmp_ans and problems[5].answer() == tmp_ans;
judge_answer['C'] = problems[2].answer() == tmp_ans and problems[9].answer() == tmp_ans;
judge_answer['D'] = problems[4].answer() == tmp_ans and problems[8].answer() == tmp_ans;
return judge_answer[problem.answer()];
}
};
class Check_seven : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, int> ans_cal;
unordered_map<char, char> answer;
answer['A'] = 'C'; answer['B'] = 'B';
answer['C'] = 'A'; answer['D'] = 'D';
for(auto & pro : problems){
++ans_cal[pro.answer()];
}
char tmp_ans = 'A';
for(auto ptr = ans_cal.begin(); ptr != ans_cal.end(); ++ptr){
if (ptr->first != tmp_ans and ptr->second < ans_cal[tmp_ans]){
tmp_ans = ptr->first;
}
}
return tmp_ans == answer[problem.answer()];
}
};
class Check_eight : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, int> select_problem;
select_problem['A'] = 6; select_problem['B'] = 4;
select_problem['C'] = 1; select_problem['D'] = 9;
char tmp_ans = problems[0].answer();
char cur_ans = problems[select_problem[problem.answer()]].answer();
return cur_ans != tmp_ans and cur_ans != tmp_ans-1 and cur_ans != tmp_ans+1;
}
};
class Check_nine : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, int> select_problem;
select_problem['A'] = 5; select_problem['B'] = 9;
select_problem['C'] = 1; select_problem['D'] = 8;
bool flag = problems[0].answer() == problems[5].answer();
return !flag == (problems[4].answer() == problems[select_problem[problem.answer()]].answer());
}
};
class Check_ten : public ProblemCheck{
public:
bool check(const Problem & problem, const vector<Problem> & problems){
assert(problems.size() == 10);
unordered_map<char, int> cal_ans;
unordered_map<char, int> select_answer;
select_answer['A'] = 3; select_answer['B'] = 2;
select_answer['C'] = 4; select_answer['D'] = 1;
for(auto & pro : problems){
++cal_ans[pro.answer()];
}
int min_cal = 666;
int max_cal = 0;
for(auto ptr = cal_ans.begin(); ptr != cal_ans.end(); ++ptr){
min_cal = ptr->second < min_cal ? ptr->second : min_cal;
max_cal = ptr->second > max_cal ? ptr->second : max_cal;
}
return select_answer[problem.answer()] == (max_cal - min_cal);
}
};
class Solution{
private:
static const int SIZE = 10;
vector<Problem> m_problems;
vector<vector<Problem>> m_answers;
unordered_map<int, shared_ptr<ProblemCheck> > m_problem_check;
bool check(const shared_ptr<ProblemCheck> problem_check, const int cur_id) const {
return problem_check->check(m_problems[cur_id-1], m_problems);
}
void DFS(const int cur_index){
if (cur_index == 10){
for(int i = 0; i < SIZE; ++i){
if(!check(m_problem_check[m_problems[i].id()], m_problems[i].id())){
return;
}
}
m_answers.push_back(m_problems);
return;
}
for(char ch : {'A', 'B', 'C', 'D'}){
m_problems[cur_index].set_answer(ch);
DFS(cur_index+1);
}
}
public:
Solution(){
shared_ptr<ProblemCheck> ptr;
for(int i = 0; i < SIZE; ++i){
m_problems.push_back(Problem(i+1));
switch(i){
case 0: ptr = make_shared<Check_one>(); break;
case 1: ptr = make_shared<Check_two>(); break;
case 2: ptr = make_shared<Check_three>(); break;
case 3: ptr = make_shared<Check_four>(); break;
case 4: ptr = make_shared<Check_five>(); break;
case 5: ptr = make_shared<Check_six>(); break;
case 6: ptr = make_shared<Check_seven>(); break;
case 7: ptr = make_shared<Check_eight>(); break;
case 8: ptr = make_shared<Check_nine>(); break;
case 9: ptr = make_shared<Check_ten>(); break;
default:
assert(i < SIZE);
}
m_problem_check[i+1] = ptr;
}
}
void solve(){
DFS(0);
cout << "共有" << m_answers.size() << "组答案" << endl;
int cal = 1;
for(const auto & vec_answers : m_answers){
cout << "第" << cal << "组答案如下" << endl;
for(const auto & problem : vec_answers){
cout << "第" << problem.id() << "道题的答案为:" << problem.answer() << endl;
}
++cal;
}
}
};
int main(){
Solution sol;
sol.solve();
return 0;
}
求解如下
Comments