#35558: 解答pythonnnn
s11104220@school.saihs.edu.tw
(施同學)
學校
:
臺北市立松山高級工農職業學校
編號 : 221254
來源 : [61.223.232.64]
最後登入時間 ：
2024-05-13 16:04:44
先將輸入解讀 我的方法是用"T"拆分
for i in range(len(s)+1):ans+=abs...
可以直接算出沒有Lx的答案(10%)
我第二個40%程式碼是用l變數紀錄磁軌的位置，ptr+=1移動，stack紀錄位置、L"x"
碰到E回到上一個Lx直到Lx跑完為止
ans+=abs(l-新位置)算出答案
如果直接將T1L2T3ET4T5拆開算也可以，但是遇到T1L999T2ET3時間會爆(40%)
會發現Lx裡面的數字其實不用算那麼多次
只要算出
abs(外圈鏈結內圈)*外圈Lx ，我註解這裡叫他"前"
再算出內圈Lx內的答案 ，我註解這裡叫他"中迴"
碰到E在abs(Lx頭-Lx尾)*此圈Lx ，我註解這裡叫他"iter"
把內圈答案傳給外圈 ，我註解這裡叫他"L(x中迴+iter)"
這裡應該要有一個"後" 但是外圈的"中迴"會順便鏈結起來 不用計算
以下是我三個答案
#40%TLE
'''
from sys import stdin
def main():
s=stdin.readline()[1:].replace("\n","").replace("L","TL").replace("E","TE").split("T")
i=0
stack=[1,0]
l=-1
ans=0
while i<len(s):
if s[i][0]=="L":
stack.append([int(s[i][1:]),i])
elif s[i]=="E":
stack[-1][0]-=1
if(stack[-1][0]>0):i=stack[-1][1]
else:stack.pop()
elif l!=-1:
ans+=abs(int(s[i])-l)
l=int(s[i])
else:
l=int(s[i])
i+=1
print(ans)
main()'''
#80%遞迴過深
'''
from sys import stdin
def fLx(s,ls,sm,ptr):
h,r=-1,-1
ans=0
q=[]
while ptr<ls:
if s[ptr][0]=="L":
q=fLx(s,ls,int(s[ptr][1:]),ptr+1)
if h!=-1:ans+=abs(r-q[0])*sm#前
if h==-1:h=q[0]
r=q[1]
ans+=q[2]*sm#Lx中迴+iter
ptr=q[3]
elif s[ptr]=="E":
ans+=abs(h-r)*(sm-1)
return h,r,ans,ptr
else:
if h==-1:h=int(s[ptr])
if r!=-1:
ans+=abs(r-int(s[ptr]))*sm#中迴
r=int(s[ptr])
ptr+=1
return ans
def main():
s=stdin.readline()[1:].replace("\n","").replace("L","TL").replace("E","TE").split("T")
print(fLx(s,len(s),1,0))
main()
'''
#100% 0.1s 9MB
'''
from sys import stdin
def main():
s=stdin.readline()[1:].replace("\n","").replace("L","TL").replace("E","TE").split("T")
ans=0;ptr=0;ls=len(s)
# [sm,h,r,ans]
st=[[1,-1,-1,0]]
q=[]
while ptr<ls:
if s[ptr][0]=="L":
st.append([int(s[ptr][1:]),-1,-1,0])
elif s[ptr]=="E":
st[-1][3]+=abs(st[-1][1]-st[-1][2])*(st[-1][0]-1)#iter
q=st.pop()
if st[-1][1]!=-1:st[-1][3]+=abs(st[-1][2]-q[1])*st[-1][0]#前
else:st[-1][1]=q[1]
st[-1][2]=q[2]
st[-1][3]+=q[3]*st[-1][0]#L(x中迴+iter)
else:
if st[-1][1]==-1:st[-1][1]=int(s[ptr])
if st[-1][2]!=-1:
st[-1][3]+=abs(int(s[ptr])-st[-1][2])*st[-1][0]#中迴
st[-1][2]=int(s[ptr])
ptr+=1
print(st[-1][3])
main()
'''
ZeroJudge Forum