AtCoder Beginner Contest 411 补题

AtCoder Beginner Contest 411

Conflict 2

本题中需要不断替换字符串，但又要确保字符串不能是引用类型防止字符被修改被覆盖，因此需要不断拷贝字符串。这个过程一定会超时，因此考虑使用链表，用指针指向真正的数据，每次修改时只需移动指针。

具体过程如下：

• 操作1：创建一个节点，该节点的头指针指向服务器节点
• 操作2：创建一个新节点，该节点头指针指向原先的节点，尾节点指向新的字符串
• 操作3：服务器节点设置为对应的pc节点

n,q=RR()
class Node:
    def __init__(self,p=None,nx=None):
        self.pre=p
        self.nx=nx  
# 维护每台电脑对应的节点
p=[None]*n
# 服务器节点
s=None 
for _ in range(q):
    tmp=RLS()
    if tmp[0]=='1':
        idx=int(tmp[1])-1
        # 创建新的节点，头指针指向服务器节点
        p[idx]=Node(s)
    elif tmp[0]=='2':
        idx=int(tmp[1])-1
        # 创建新节点，拼接两个值
        p[idx]=Node(('' if not p[idx] else p[idx]),tmp[-1])
    else:
        idx=int(tmp[1])-1
        # 修改服务器所对的节点
        s=p[idx]

if not s:print('')
else:
    # 遍历链表，拼接字符串
    ans=deque()
    while True:
        if s.nx:ans.appendleft(s.nx)
        if isinstance(s.pre,Node):
            s=s.pre
        else:
            if s.pre:ans.appendleft(s.pre)
            break
    print(''.join(ans))