题目描述题目要求判断是否能够使用资源区中的部分或全部骰子构造一个合法的数学表达式使其结果等于目标数。表达式必须使用一位数即000到999的数字可以使用括号改变运算顺序运算符为、−-−、×\times×。每个骰子上的符号只能使用一次。输入格式输入包含多组测试用例每组两行第一行资源区的骰子符号共131313个字符由数字和运算符组成。第二行目标数一位或两位数字不含前导零。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每组测试用例输出一行solution或no solution。样例输入999999 54 0149- 7xx 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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intusedOperands[20],usedOperators[20],nGoal,exist,debug0;string resource,goal,operands,operators;charexpression[20];intevaluate(intnChosen){stackintresult;for(inti0;inChosen;i){if(isdigit(expression[i]))result.push(expression[i]-0);else{intaresult.top();result.pop();intbresult.top();result.pop();switch(expression[i]){case:result.push(ab);break;case-:result.push(b-a);break;casex:result.push(a*b);break;}}}returnresult.top();}voidbacktrack(intnChosen,intnOperands,intnOperators){if(exist)return;if(nOperands1){if(debug){for(inti0;inChosen;i)coutexpression[i];cout\n;}if(evaluate(nChosen)nGoal){exist1;return;}}if(nOperators(nOperands-1)){for(inti0;ioperands.length();i){if(!usedOperands[i]operands[i]!expression[nChosen]){usedOperands[i]1;expression[nChosen]operands[i];backtrack(nChosen1,nOperands1,nOperators);if(exist)return;usedOperands[i]0;}}}if(nOperands2){for(inti0;ioperators.length();i){if(!usedOperators[i]operators[i]!expression[nChosen]){usedOperators[i]1;expression[nChosen]operators[i];backtrack(nChosen1,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);intcases0;while(cinresourcegoal){cases;nGoalstoi(goal);operands.clear(),operators.clear();sort(resource.begin(),resource.end());for(autoc:resource){if(isdigit(c))operandsc;elseoperatorsc;}exist0;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;}
