爆炸
查看原帖
爆炸
351392
a1029楼主2021/12/5 19:14

是求24点解的个数。大佬们不需要读题,请求帮忙指出为什么运行错误。(过程打在屏幕上都正确,答案快出来了,却爆炸)

万分感谢,小弟顿首!

#include <bits/stdc++.h>
using namespace std;

int a[15], ans;
char b[14], o[] = {'*', '+', '-', '/'};

string digital(int x) {
	string ret;
	while (x) {
		ret += x % 10 + '0';
		x /= 10;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

struct node {
	bool type;
	double n;
	char c;
};
stack < char > st;
stack < double > sta;
queue < node > q;

int status(char c) {
	if (c == '+' || c == '-') return 1;
	if (c == '*' || c == '/') return 2;
	return 3;
}

int solve(string s) {
	if (s[0] == '-') s.insert(0, "0");
	double x = 0;
	int con = 0;
	for (int i = 0; i < s.size(); ) {
		char c = s[i];
		while (isdigit(c) || c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
			if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(') {
				if (st.empty()) st.push(c);
				else {
					while (st.top() != '(' && status(c) <= status(st.top())) {
						q.push((node){0, 0, st.top()});
						st.pop();
						if (st.empty()) break;
					}
					st.push(c);
				}
			}
			if (c == ')') {
				while (st.top() != '(') {
					q.push((node){0, 0, st.top()});
					st.pop();
				}
				st.pop();
			}
			while (isdigit(c)) {
				con = 1;
				x = x * 10 + c - '0';
				c = s[++i];
			}
			if (con) {
				q.push((node){1, x, ' '});
				con = 0;
				x = 0;
				continue;
			}
			c = s[++i];
		}
		while (!st.empty()) {
			q.push((node){0, 0, st.top()});
			st.pop();
		}
		while (!q.empty()) {
			node t = q.front();
			q.pop(); 
			if (t.type) sta.push(t.n);
			else {
				int a = sta.top(), b;
				sta.pop();
				b = sta.top();
				sta.pop();
				if (t.c == '+') sta.push(a + b);
				if (t.c == '-') sta.push(b - a);
				if (t.c == '*') sta.push(a * b);
				if (t.c == '/') sta.push(b / a);
			}
		}
		int ret = sta.top();
		sta.pop();
		return ret;
	}
}

void dfs(int dep) {
	if (dep >= 4) {
		string A = digital(a[1]), B = digital(a[2]), C = digital(a[3]), D = digital(a[4]);
		string fp1 = A + b[1] + B + b[2] + C + b[3] + D;
		
		
		string fp2 = A + b[1] + '(' + B + b[2] + C + b[3] + D + ')';

		string fp3 = '(' + A + b[1] + B + ')' + b[2] + '(' + C + b[3] + D + ')';
		string fp4 = '(' + A + b[1] + '(' + B + b[2] + C + ')' + ')' + b[3] + D;
		string fp5 = A + b[1] + '(' + B + b[2] + '(' + C + b[3] + D + ')' + ')'; 
		cout << fp1 << "=" << solve(fp1) << endl;
		cout << fp2 << "=" << solve(fp2) << endl;
		cout << fp3 << "=" << solve(fp3) << endl;
		cout << fp4 << "=" << solve(fp4) << endl;
		cout << fp5 << "=" << solve(fp5) << endl;
		puts("-----------------------");
		if (solve(fp1) == 24) ++ans;
		if (solve(fp2) == 24) ++ans;
		if (solve(fp3) == 24) ++ans;
		if (solve(fp4) == 24) ++ans;
		if (solve(fp5) == 24) ++ans;
		return;
	}
	for (int i = 0; i < 4; i++) {
		b[dep] = o[i];
		dfs(dep + 1);
	}
}

int main()
{
	cin >> a[1] >> a[2] >> a[3] >> a[4]; 
	dfs(1);
	cout << ans << endl;
	return 0;
}

Read In:
5 5 5 5
Read In:
4 6 1 1
2021/12/5 19:14
加载中...