AtCoder Beginner Contest 421 vp

AtCoder Beginner Contest 421

RLE Moving

本题需要通过双指针来保证每个操作中处理的步数是一致的，对于是否会有重叠位置，需要分类讨论——在同一位置时，出发方向相同则接下来的步数都是重叠的；某个方向的位置相同时，另一个方向是同向，二者之间的距离是奇数且小于步数，那么就可以相遇一次；反之，需要满足两个位置是在正方形的两个顶点，且距离小于步数，那么也会相遇一次。

x1,y1,x2,y2=RR()
n,m,l=RR()

a=[]
b=[]

for _ in range(m):
    tmp=RLS()
    a.append([tmp[0],int(tmp[1])])
for _ in range(l):
    tmp=RLS()
    b.append([tmp[0],int(tmp[1])])

i,j=0,0
total=ans=0

vec={'L','R'}
hor={'U','D'}

dirs={'D':(1,0),'U':(-1,0),'L':(0,-1),'R':(0,1)}

while total<n:

    d1,d2=a[i][0],b[j][0]
    # 双指针判断步数
    if a[i][1]==b[j][1]:
        step=a[i][1]
        a[i][1]=b[j][1]=0
        i+=1
        j+=1
    elif a[i][1]<b[j][1]:
        step=a[i][1]
        b[j][1]-=a[i][1]
        i+=1
    else:
        step=b[j][1]
        a[i][1]-=b[j][1]
        j+=1
    # 同一位置
    if x1==x2 and y1==y2 and d1==d2:ans+=step
    # 这里距离不减一就判断是否是偶数，abs(y1-y2)<=2*step要尽可能避免除法，本体数据范围较大，若用ceil((abs(y1-y2)-1)/2)会出现问题
    elif x1==x2 and abs(y1-y2)&1==0 and abs(y1-y2)<=2*step:
        if y1<y2 and d1=='R' and d2=='L':
            ans+=1
        elif y1>y2 and d1=='L' and d2=='R':
            ans+=1
    elif y1==y2 and abs(x1-x2)&1==0 and abs(x1-x2)<=2*step:
        if x1>x2 and d1=='U' and d2=='D':
            ans+=1
        elif x1<x2 and d1=='D' and d2=='U':
            ans+=1
    # 正方形的两个角
    elif ((d1 in hor and d2 in vec) or (d1 in vec and d2 in hor)) and abs(x1-x2)==abs(y1-y2) and abs(x1-x2)<=step:
        f=False
        if y1>y2:
            x1,x2=x2,x1
            y1,y2=y2,y1
            d1,d2=d2,d1
            f=True
        if x1>x2:
            if (d1=='R' and d2=='D') or (d1=='U' and d2=='L'):
                ans+=1
        else:
            if (d1=='R' and d2=='U') or (d1=='D' and d2=='L') :
                ans+=1 
        if f:
            x1,x2=x2,x1
            y1,y2=y2,y1
            d1,d2=d2,d1
    # 更新位置
    total+=step
    dx,dy=dirs[d1]
    x1+=dx*step
    y1+=dy*step

    dx,dy=dirs[d2]
    x2+=dx*step
    y2+=dy*step

print(ans)