2022年十三届B组----试题F：消除游戏

• 题目
• 法一、切片
• 法二、双向链表

题目

法一、切片

s=list(input())
j=0
while j < 2 ** 64:  #题目要求的操作次数
    pos = set()  #集合特性（去重）
    for i in range(1, len(s) - 1):
        if s[i] == s[i - 1] and s[i] != s[i + 1]:
            pos.add(i)#需要删除的下标存到集合
            pos.add(i + 1)
        if s[i] != s[i - 1] and s[i] == s[i + 1]:
            pos.add(i - 1)
            pos.add(i)
    if len(pos) == 0:#循环完如果集合没有数字，表示没有边缘字符
        print("".join(s))#把s转换成字符串打印
        break#跳出循环
    s1 = []#新建一个列表
    for p in range(len(s)):#把不在集合里面的元素添加到新的列表中
        if p not in pos:
            s1.append(s[p])
    s = s1.copy()
    pos.clear()#每次循环完以后清空集合
    if len(s) == 0:
        print("EMPTY")
        break
    j += 1

• 12个测试只能通过7个

法二、双向链表

N=10**6+10
pos=[]   # 存储需要删除的节点位置
l,r=[0]*N,[0]*N  # 节点的左指针和右指针
st=[False]*N  # 节点状态，记录节点是否已删除
s=input()
n=len(s)
s="@"+s+"@"   # 在字符串开头和结尾添加特殊字符 "@"，确保每个字符都有左右相邻字符，来处理边界情况
# 构建双向链表
for i in range(1,n+1):
    l[i]=i-1
    r[i]=i+1
# 查找所有边缘字符
def check(i):
    if s[l[i]]=="@" or s[r[i]]=="@":
        return
    if s[l[i]]==s[i] and s[r[i]]!=s[i]:
        pos.append(r[i])
        pos.append(i)
    if s[l[i]]!=s[i] and s[r[i]]==s[i]:
        pos.append(l[i])
        pos.append(i)

# 删除节点   
def remove(j):
    r[l[j]]=r[j]
    l[r[j]]=l[j]
    # 删除j结点，置为True
    st[j]=True

# 检查相邻重复字符并删除
for i in range(1,n+1):
    check(i)
while pos:
    ne=[]
    for p in pos:  # 如果节点已删除，则跳过
        if st[p]:continue
        remove(p)
        ne.append(l[p])
        ne.append(r[p])
    pos=[] 
    for e in ne:
        if not st[e]:
            check(e)
ans=""
for i in range(1,n+1):
    if not st[i]:# 如果节点未删除，则添加到结果字符串
        ans+=s[i]
if ans:
    print(ans)
else:
    print("EMPTY")