不会

智能的27中尉三角名不唐

2026-02-22 13:28:31

发布于：内蒙古

22阅读

0回复

0点赞

求大佬解一下

有帮助，赞一个

去预览

0/2000

全部评论 2

超级路卡利欧

n = int(input())
p = list(map(int, input().split()))
suf_min = [0] * (n + 1)
suf_min[n] = float('inf')
for i in range(n - 1, -1, -1):
    suf_min[i] = min(p[i], suf_min[i + 1])

color = [-1] * n 
G = [[] for _ in range(n)]

for i in range(n):
    for j in range(i + 1, n):
        if p[i] < p[j] and suf_min[j + 1] < p[i]:
        
            G[i].append(j)
            G[j].append(i)
def dfs(u, c):
    color[u] = c
    for v in G[u]:
        if color[v] == -1:
            if not dfs(v, c ^ 1):
                return False
        elif color[v] == c:
            return False
    return True

for i in range(n):
    if color[i] == -1:
        if not dfs(i, 0):
            print(0)
            exit()
stack1 = []
stack2 = []
ans = []
cur = 1  

for i in range(n):
    while True:
        if stack1 and stack1[-1] == cur:
            ans.append('b')
            stack1.pop()
            cur += 1
        elif stack2 and stack2[-1] == cur:
            ans.append('d')
            stack2.pop()
            cur += 1
        else:
            break
    
    if color[i] == 0:
        while stack1 and p[i] > stack1[-1]:
            if stack2 and stack2[-1] == cur:
                ans.append('d')
                stack2.pop()
                cur += 1
            else:
                break
        ans.append('a')
        stack1.append(p[i])
    else:
        while stack2 and p[i] > stack2[-1]:
            if stack1 and stack1[-1] == cur:
                ans.append('b')
                stack1.pop()
                cur += 1
            else:
                break
        ans.append('c')
        stack2.append(p[i])
while cur <= n:
    if stack1 and stack1[-1] == cur:
        ans.append('b')
        stack1.pop()
        cur += 1
    elif stack2 and stack2[-1] == cur:
        ans.append('d')
        stack2.pop()
        cur += 1
    else:
        break

print(' '.join(ans))

4天前来自浙江

Eucatastrophe‌废号
看题解

2026-02-23 来自浙江
0