题解：B4173 [BCSP-X 2024 6 月小学高年级组] 先序遍历

Ag2WO4 · 2025-03-07 04:16:06 · 题解

Python 的致命卡常题。其实无非就是贪心两种情况：将靠前的大节点扔到比它小的节点后面、更大的节点前面；将后面的小节点提到靠前的左儿子位置。

就这点题把记忆化搜索（子树大小）、前缀和优化（找后缀最小值）、特殊值字典（快速定位需要迁移的最小值）、手推 O(1) 公式、代码块拷贝、读写优化（其实没优化写操作）全用上来了，喜提 649ms 的好成绩。

import sys;sys.setrecursionlimit(1<<30)
def g(i):
    if i:h.append(i);g(a[i][0]);g(a[i][1])
def u(i):
    if 0<i<=n:global x;x[i]=1+u(a[i][0])+u(a[i][1]);return x[i]
    return 0
for _ in range(int(sys.stdin.readline())):
    n=int(sys.stdin.readline());a=[(0,0)]+[tuple(map(int,sys.stdin.readline().split()))for i in range(n)];h=[];g(1);h.append(n+1);z=1;q=[n+1];r={};x=[0]*(n+1);u(1)
    for i in range(n):
        if h[n+~i]<q[-1]:q.append(h[n+~i]);r[h[n+~i]]=n+~i
        else:q.append(q[-1])
    for i in range(n-1):
        if a[h[i]][0]>a[h[i]][1]>0:
            for j in range(i+x[h[i+1]]+1,n):
                if 0==a[h[j]][0]and h[i+1]<h[j+1]:print(*h[:i+1]+h[i+x[h[i+1]]+1:j+1]+h[i+1:i+x[h[i+1]]+1]+h[j+1:-1]);z=0;break
            break
        elif 0==a[h[i]][0]and h[i+1]>q[n+~i]:
            if h[i+x[h[i+1]]+1]>q[n+~i]:print(*h[:i+1]+h[r[q[n+~i]]:r[q[n+~i]]+x[h[r[q[n+~i]]]]]+h[i+1:r[q[n+~i]]]+h[r[q[n+~i]]+x[h[r[q[n+~i]]]]:-1]);z=0;break
            else:
                for j in range(i+x[h[i+1]]+1,n):
                    if 0==a[h[j]][0]and h[i+1]<h[j+1]:print(*h[:i+1]+h[i+x[h[i+1]]+1:j+1]+h[i+1:i+x[h[i+1]]+1]+h[j+1:-1]);z=0;break
                break
        elif 0==a[h[i]][1]and h[i+1]>h[i+x[h[i+1]]+1]:
            for j in range(i+x[h[i+1]]+1,n):
                if 0==a[h[j]][0]and h[i+1]<h[j+1]:print(*h[:i+1]+h[i+x[h[i+1]]+1:j+1]+h[i+1:i+x[h[i+1]]+1]+h[j+1:-1]);z=0;break
            break
    if z:print(*h[:-1])