60pts求助
  • 板块P1236 算24点
  • 楼主Fwio_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/29 16:53
  • 上次更新2023/11/2 17:18:15
查看原帖
60pts求助
965238
Fwio_楼主2023/9/29 16:53
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<unordered_map>
using namespace std;
vector<int> vec;
vector<int> op;
unordered_map<char , int> priority{{'+' , 1} , {'-' , 1} , {'*' , 2} , {'/' , 2}};
int F(int x){
	if(x == 1) return '+';
	else if(x == 2) return '-';
	else if(x == 3) return '*';
	else return '/';
}
int Eval(vector<int> vec , vector<int> Op){
	string str;
	for(int i = 0;i < vec.size();i++){
		str.push_back(vec[i] ^ 48);
		if(i < vec.size() - 1) str.push_back(F(Op[i]));
	}
	stack<int> num;
	stack<char> op;
	for(int i = 0;i < str.size();i++){
		if(str[i] >= '0' && str[i] <= '9') num.push(str[i] ^ 48);
		else{
			while(!op.empty() && priority[op.top()] >= priority[str[i]]){
				int y = num.top(); num.pop();
				int x = num.top(); num.pop();
				char z = op.top(); op.pop();
				if(z == '+') num.push(x + y);
				else if(z == '-') num.push(x - y);
				else if(z == '*') num.push(x * y);
				else num.push(x / y);
			}
			op.push(str[i]);
		}
	}
	while(!op.empty()){
		int y = num.top(); num.pop();
		int x = num.top(); num.pop();
		char z = op.top(); op.pop();
		if(z == '+') num.push(x + y);
		else if(z == '-') num.push(x - y);
		else if(z == '*') num.push(x * y);
		else num.push(x / y);
	}
	return num.top();
}
void print(vector<int> vec , vector<int> Op){
	string str;
	for(int i = 0;i < vec.size();i++){
		str.push_back(vec[i] ^ 48);
		if(i < vec.size() - 1) str.push_back(F(Op[i]));
	}
	stack<int> num;
	stack<char> op;
	for(int i = 0;i < str.size();i++){
		if(str[i] >= '0' && str[i] <= '9') num.push(str[i] ^ 48);
		else{
			while(!op.empty() && priority[op.top()] >= priority[str[i]]){
				int y = num.top(); num.pop();
				int x = num.top(); num.pop();
				char z = op.top(); op.pop();
				cout << x << z << y << "=";
				if(z == '+') num.push(x + y) , cout << x + y << endl;
				else if(z == '-') num.push(x - y) , cout << x - y << endl;
				else if(z == '*') num.push(x * y) , cout << x * y << endl;
				else num.push(x / y) , cout << x / y << endl;
			}
			op.push(str[i]);
		}
	}
	while(!op.empty()){
		int y = num.top(); num.pop();
		int x = num.top(); num.pop();
		char z = op.top(); op.pop();
		int a = max(x , y) , b = min(x , y);
		x = a , y = b;
		cout << x << z << y << "=";
		if(z == '+') num.push(x + y) , cout << x + y << endl;
		else if(z == '-') num.push(x - y) , cout << x - y << endl;
		else if(z == '*') num.push(x * y) , cout << x * y << endl;
		else num.push(x / y) , cout << x / y << endl;
	}
}
void dfs(vector<int> vec){
	if(op.size() == 3){
		if(Eval(vec , op) == 24){
			print(vec , op);
			exit(0);
		}
		return ;
	}
	for(int i = 1;i <= 4;i++){
		op.push_back(i);
		dfs(vec);
		op.pop_back();
	}
}
int path[15] , vis[15];
void _search(int u){
	if(u == 5){
		vector<int> cnt;
		for(int i = 1;i <= 4;i++) cnt.push_back(vec[path[i]]);
//		for(auto i : cnt) cout << i << " ";
//		cout << endl;
		dfs(cnt);
		return ;
	}
	for(int i = 0;i <= 3;i++){
		if(!vis[i]){
			vis[i] = 1;
			path[u] = i;
			_search(u + 1);
			vis[i] = 0;
		}
	}
}
int main(){
	for(int i = 1;i <= 4;i++){
		int x;
		scanf("%d" , &x);
		vec.push_back(x);
	}
	_search(1);
	cout << "No answer!" << endl;
	return 0;
}
2023/9/29 16:53
加载中...