自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:30:51，当前版本为作者最后更新于2017-08-30 18:18:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为字典序是这样的(,),*,+,-,/,1,2,3,4,5,6,7,8,9(从小到大)

所以括号有(((a_b)_c)_d)||((a_b)_(c_d))||(a_(b_(c_d)))这样的3种顺序 当然题目还有一些其他细节

1.运算中不能出现0和负数

e.g. 3 4 5 6=>

(((3-4)+4)*6) WA

(((3+5)-4)*6) AC

2.运算中必须保证只有整除

e.g. 1 2 4 6 =>

(((1/2)+4)*6) WA

(((2-1)+4)*6) AC

3.按照*,+,-,/的顺序枚举运算符

所以我们按顺序枚举 3 个运算符,枚举数的摆放位置,并且枚举优先运算的顺序,然后计算值即可,复杂度o(4!*3^3)

有一种方法是直接全排序 然后3^3枚举 然后找到就退出

但是实际上是会wa的

e.g.2 4 6 8=>

(((2*6)+4)+8) WA

(((2*6)*8)/4) AC

因为(2 6 4 8)<(2 6 8 4)所以按照全排列找到退出就会WA

所以我们考虑把所有解都记录下来 然后sort一下就ok了(或者堆)(用sprintf可以节省很多赋值的代码)复杂度o(648*log648)

ps:代码非常好写