UVa 549 Evaluating an Equations Board
题目描述
题目要求判断是否能够使用资源区中的部分或全部骰子，构造一个合法的数学表达式，使其结果等于目标数。表达式必须使用一位数（即000到999的数字），可以使用括号改变运算顺序，运算符为+++、−-−、×\times×。每个骰子上的符号只能使用一次。
输入格式
输入包含多组测试用例，每组两行：
- 第一行：资源区的骰子符号（共131313个字符，由数字和运算符组成）。
- 第二行：目标数（一位或两位数字，不含前导零）。
输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每组测试用例，输出一行solution或no solution。
样例
输入
999999+++++ 54 0149++- 7+xx 56 0149++- 7+-- 56输出
solution no solution题目分析
本题的核心是搜索所有可能的表达式，判断是否存在一个等于目标数的表达式。
搜索策略
- 将资源区的骰子分为数字和运算符两类。
- 表达式是数字和运算符交替的序列，且以数字开头和结尾。运算符数量比数字数量少111。
- 枚举所有可能的数字序列和运算符序列的组合，检查计算值是否等于目标数。
- 由于数字和运算符数量有限，可以使用回溯法生成所有可能的表达式。
表达式求值
由于表达式不含括号，但题目说明可以使用括号，实际上运算符优先级需要处理。然而，在回溯法中，可以通过递归生成表达式树或使用逆波兰表达式（RPN\texttt{RPN}RPN）求值。参考代码使用栈模拟后缀表达式求值，但生成的是中缀表达式？实际上，表达式字符数组按顺序存放数字和运算符，然后使用栈计算时，未考虑运算符优先级，隐含了从左到右的顺序。这意味着它假设表达式是严格从左到右计算（即无优先级）。但题目允许使用括号改变顺序，因此需要更复杂的生成方式。
简化处理
参考代码通过枚举所有可能的数字和运算符排列，并假设表达式按顺序从左到右计算。这实际上对应于所有运算符优先级相同的情况，但题目允许括号，因此这种搜索可能遗漏解。然而，由于数字和运算符数量较少，且目标数不大，这种简化在本题中可能是可接受的。
复杂度分析
数字最多131313个，运算符最多666个，枚举所有排列可行。
代码实现
// Evaluating an Equations Board// UVa ID: 549// Verdict: Accepted// Submission Date: 2017-08-04// UVa Run Time: 0.010s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intusedOperands[20],usedOperators[20],nGoal,exist,debug=0;string resource,goal,operands,operators;charexpression[20];intevaluate(intnChosen){stack<int>result;for(inti=0;i<nChosen;i++){if(isdigit(expression[i]))result.push(expression[i]-'0');else{inta=result.top();result.pop();intb=result.top();result.pop();switch(expression[i]){case'+':result.push(a+b);break;case'-':result.push(b-a);break;case'x':result.push(a*b);break;}}}returnresult.top();}voidbacktrack(intnChosen,intnOperands,intnOperators){if(exist)return;if(nOperands==1){if(debug){for(inti=0;i<nChosen;i++)cout<<expression[i];cout<<'\n';}if(evaluate(nChosen)==nGoal){exist=1;return;}}if(nOperators>=(nOperands-1)){for(inti=0;i<operands.length();i++){if(!usedOperands[i]&&operands[i]!=expression[nChosen]){usedOperands[i]=1;expression[nChosen]=operands[i];backtrack(nChosen+1,nOperands+1,nOperators);if(exist)return;usedOperands[i]=0;}}}if(nOperands>=2){for(inti=0;i<operators.length();i++){if(!usedOperators[i]&&operators[i]!=expression[nChosen]){usedOperators[i]=1;expression[nChosen]=operators[i];backtrack(nChosen+1,nOperands-1,nOperators-1);if(exist)return;usedOperators[i]=0;}}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;while(cin>>resource>>goal){cases++;nGoal=stoi(goal);operands.clear(),operators.clear();sort(resource.begin(),resource.end());for(autoc:resource){if(isdigit(c))operands+=c;elseoperators+=c;}exist=0;memset(usedOperands,0,sizeof(usedOperands));memset(usedOperators,0,sizeof(usedOperators));memset(expression,0,sizeof(expression));backtrack(0,0,operators.size());cout<<(exist?"solution":"no solution")<<'\n';}return0;}