我试图解决代码力的"String Score"问题

Question

我试图解决一个关于codeforces的问题，这是它的链接:link

给定一个数字聚合体(二进制数)和一个大小为聚合体(二进制数)的字符串(二进制数)𝑆只有大写字符{V,W,X,Y,Z}。

• V:加5分
• W:加2分
• X:从分数中删除下一个连续字符。
• Y:将下一个连续字符移动到字符串的末尾。
• Z:如果下一个连续字符是V，则将总分除以5;如果是W，则将总分除以2。然后移除字符串中的下一个连续字符当且仅当字符为V或w

注意:如果字符串以X或Y或Z结尾，则忽略它们的操作。分数从左到右计算，从0开始。

我试过这个代码，但不幸的是，我得到的时间限制超过了测试11代码:

N = int(input())
S = list(input())
C = 0
for i in range(N):
if i == len(S)-1 and (S[len(S)-1] == "X" or S[len(S)-1] == "Y" or S[len(S)-1] == "Z"):
break
if i >= len(S):
break
if S[i] == "V" and S[i-1] == "Z":
C //= 5
elif S[i] == "V" and (S[i-1] != "X" and S[i-1] != "Z"):
C += 5
if S[i] == "W" and S[i-1] == "Z":
C //= 2
elif S[i] == "W" and (S[i-1] != "X" and S[i-1] != "Z"):
C += 2
if S[i] == "Y":
S.append(S[i+1])
del S[i+1]
print(C)

你能帮我吗?

Answer 1

这确实是作弊，但我不知道如何在不显示代码的情况下描述优化。

您可以通过枚举字符串来加速循环，而不是尝试索引。而不是试图在适当的地方修改列表，只需跟踪添加的字母并稍后重新处理它们。不要试图往前看，而是记住最后一个字母是什么，并用它来影响当前的字符。例如:

def compute(S):
C = 0
while S:
last = None
more = []
for c in S:
# Handle special actions from the last X, Y, or Z.
if last == 'X':
pass
elif last == 'Y':
more.append( c )
elif last == 'Z' and c == 'V':
C //= 5
elif last == 'Z' and c == 'W':
C //= 2
elif c == 'V':
C += 5
elif c == 'W':
C += 2
last = c
S = more
return C
print(compute('VYWZW'))
print(compute('WZYVXW'))

Answer 2

我也仍在学习，但想在这里提供一个可能的递归解决方案作为替代方案。我不确定如何测试性能，但它似乎得到了上面测试用例的正确输出。

编辑:修复了字符串以Y, z结尾时索引超出边界的问题

'''
V - Add 5 Points
W - Add 2 Points
X - Remove next character from score
Y - Move next character to end of string
Z - Look at next character. If V, divide score by 5. If W, divide score by 2. If V or W, remove character
'''
def calculate(S, Score=0):
if type(S) == str:
S = list(S)
if len(S) == 0:
return Score
if S[0] == "V":
Score += 5
return calculate(S[1:], Score)
if S[0] == "W":
Score += 2
return calculate(S[1:], Score)
if S[0] == "X":
return calculate(S[2:], Score)
if S[0] == "Y":
try:
next_letter = S[1]
S = S[2:]
S.append(next_letter)
return calculate(S, Score)
except IndexError:
return calculate(S[1:], Score)
if S[0] == "Z":
try:
if S[1] == "V":
Score //= 5
return calculate(S[2:], Score)
if S[1] == "W":
Score //= 2
return calculate(S[2:], Score)
if S[1] not in ["V","W"]:
return calculate(S[1:], Score)
except IndexError:
return calculate(S[1:], Score)
print(calculate('VYWZW'))  # 4
print(calculate('WZYVXW'))  # 7