LQ5315.张三的社团小游戏
这两天折腾了最久的一道题,而且网上没有AC的题解(貌似数据被改过),暴力杯暴力竟然如此难过
交叉递归,注意题意要求的输出顺序,应先枚举符号,然后枚举数字。
为了枚举数字的输出顺序字典序仍然最小,进行深搜前应该sort(key=str)
按照字符串的规则对数组内数字进行排序。
Python的运行速度实在是太慢了,做了很多尝试和优化,大概有以下几点:
- 出口固定(长度已知,数字$n$个,操作符$n-1$个,使用
range
生成数组后修改元素,比使用append
和pop
要快得多。 - 不要轻易使用
copy
库中的deepcopy
方法,此处是因check
完op
和num
都直接被重置了,没必要在这里带来额外的时间复杂度。 - 对于不能够整除的情况,直接返回
False
,属于一种比较鸡肋的剪枝(不是 - 对于乘法和除法的特殊处理,算完$i-1$和$i$的乘除后,结果放到$i$上,$i-1$设置为0,按照加法规则进行累加就可以了,有效避免对于除以0的特殊处理。
PyPy编译器通过100%,Python编译器只能过70%,懒得再尝试了(失败的暴搜+1
import sys
from sys import exit
sys.setrecursionlimit(10**3) # 扩大栈空间
def check():
global flag, sum
sum = 0
status = 1
opc = op.copy()
numb = num.copy()
for i in range(1, n):
if opc[i-1] == "*":
numb[i] = numb[i-1]*numb[i]
numb[i-1] = 0
elif opc[i-1] == "/":
if numb[i-1] % numb[i] == 0:
numb[i] = numb[i-1]//numb[i]
else:
return False
numb[i-1] = 0
sum = numb[0]
for i in range(1, n):
if opc[i-1] == "-":
status = 2 # 减法
elif opc[i-1] == "+":
status = 1 # 加法
if status == 1:
sum += numb[i]
else:
sum -= numb[i]
if sum == 24:
flag = True
return True
return False
def dfs(depth):
global flag, num, op, sum
if flag == True:
return
if depth == n:
if check():
flag = True
print("YES")
print(f"{num[0]:.0f}", end="")
for i in range(1, n):
print(f"{op[i-1]}{num[i]:.0f}", end="")
print(f"={sum:.0f}", end="")
return
sum = 0
opo = ["*", "+", "-", "/"]
for i in range(0, 4):
op[depth-1] = opo[i]
for j in range(1, n):
if st[j] == True:
continue
st[j] = True
num[depth] = a[j]
dfs(depth+1)
st[j] = False
n = int(input())
a = list(map(int, input().split()))
st = [False for _ in range(n)]
num = [-1 for _ in range(n)]
op = ["" for _ in range(n-1)]
flag = False
sum = 0
a.sort(key=str)
for i in range(0, n):
num[0] = a[i]
st[i] = True
dfs(1)
num = [-1 for _ in range(n)]
op = ["" for _ in range(n-1)]
if flag == True:
exit()
st[i] = False
print("NO")