UVa 12010 Boring Homework

题目描述给定一个由111到NNN的排列组成的插入序列按照二叉搜索树BST\texttt{BST}BST的插入规则依次构建一棵树然后根据特定的绘图规则输出该树的字符画。绘图规则如下111. 单个节点的图形为字符o。222. 若某子树非空在其根节点的正上方画一个|再在该|的正上方画一个。最后在所在行用最少数量的-可以为000个将表示左、右子树的与表示父节点的o连接起来。333. 左子树必须画在父节点左侧右子树画在父节点右侧。444. 根节点所在列不能出现左或右子树的任何字符。555. 左子树与右子树的图形不能共享任何列。输入格式第一行包含一个整数TTTT≤2500T \le 2500T≤2500表示测试用例数。接下来TTT行每行先给出一个正整数NNNN80N 80N80随后给出NNN个整数它们是111到NNN的一个排列表示BST\texttt{BST}BST的插入顺序。输出格式对于每个测试用例第一行输出Case #x:xxx从111开始。随后若干行输出按规则绘制的图形每行末尾不得有多余空格但行首的前导空格需要保留。样例输入3 3 3 1 2 6 4 5 6 1 3 2 5 3 4 5 2 1输出Case #1: -o | o | o Case #2: --o | | o- o | | o o | o Case #3: o | | o o | | o o题目分析本题的核心是将一棵BST\texttt{BST}BST转化为满足特定布局的字符画。限制N80N 80N80使得我们可以使用二维字符数组存储图形但关键在于正确确定每个节点的行、列位置并精确绘制连接符号。行坐标的确定根据规则222父节点o所在行与子树的所在行相同而子树的根节点o位于该行下方两行。因此深度为ddd的节点根深度为000所在行号为2d2d2d。整棵树的最大行号为2×maxDepth2 \times \textit{maxDepth}2×maxDepth总行数为2×maxDepth12 \times \textit{maxDepth} 12×maxDepth1。列坐标的确定规则444和555要求根列不被子树占用且左右子树的列区间互不重叠。若对BST\texttt{BST}BST进行中序遍历左 – 根 – 右访问到的节点顺序恰好是键值升序依次赋予列号0,1,…,N−10, 1, \dots, N-10,1,…,N−1则左子树所有节点的列号均小于根节点右子树所有节点均大于根节点且左右子树列区间完全分离。这完美满足规则要求因此列号由中序遍历唯一确定。连接线的绘制规则222要求用最少的-将父节点的o与左、右子树的连接起来。具体操作对于每个有孩子左或右的节点在其所在行2×depth2 \times \textit{depth}2×depth从左孩子列若无左孩子则为该节点列到右孩子列若无右孩子则为该节点列之间填充-但要保留已有的o、、|等字符。由于列号已经保证左孩子列 ≤ 右孩子列填充区间恰好是最短连接路径。字符放置顺序先放置所有节点的o再放置非根节点的|和最后填充横线。注意|必须在o的正上方两行即2d−12d-12d−1行在2d−22d-22d−2行横线在2d2d2d行。这样分层放置可以避免覆盖。解题思路第一步构建BST\texttt{BST}BST按给定序列依次插入节点。由于节点值恰好是111到NNN我们可以直接将值减111作为数组下标避免哈希映射。每个节点存储其值、左孩子索引、右孩子索引、深度插入时计算以及后续分配的列号。第二步计算深度和最大深度在插入过程中记录每个节点的深度并更新全局最大深度。深度为000的根节点在第000行深度为ddd的节点在第2d2d2d行因此总行数为2×maxDepth12 \times \textit{maxDepth} 12×maxDepth1。第三步中序遍历分配列号从根节点开始递归中序遍历每访问一个节点将当前列号赋给该节点然后列号自增111。中序遍历得到的列号顺序即为键值升序保证左右子树列区间分离。第四步初始化二维字符网格行数为2×maxDepth12 \times \textit{maxDepth} 12×maxDepth1列数为NNN因为每个节点独享一列。所有格子初始化为空格。第五步放置节点符号遍历所有节点在位置(2×depth,col)(2 \times \textit{depth}, \textit{col})(2×depth,col)放置字符o。第六步放置|和对于每个深度大于000的节点在其正上方一行2×depth−12 \times \textit{depth} - 12×depth−1放置|再上方一行2×depth−22 \times \textit{depth} - 22×depth−2放置。这些符号仅出现在该节点所在列且位于父节点o所在行的上方两行。第七步填充横线-对每个有左或右孩子的节点确定其所在行r2×depthr 2 \times \textit{depth}r2×depth左端点列leftCol\textit{leftCol}leftCol为左孩子列若左孩子存在否则为该节点列右端点列rightCol\textit{rightCol}rightCol为右孩子列若右孩子存在否则为该节点列。由于列号满足左孩子列 ≤ 右孩子列直接循环从左到右若当前位置为空格则填充-。这保证了用最少的-连接父节点与子树的。第八步输出逐行扫描网格对每一行找到最后一个非空格字符的列号last\textit{last}last然后输出从第000列到last\textit{last}last列的所有字符包括前导空格这样就去除了尾部空格。若整行均为空格理论上不会发生则输出空行。正确性证明列号分配中序遍历保证了列号的单调性与左右子树分离满足规则333、444、555。行号分配深度映射到行号使父子节点垂直对齐满足规则222中|和的位置要求。横线填充填充区间覆盖了父节点列与所有子树所在的列且只填充空格不会覆盖已有符号因此满足“最少数量的-”且连接正确。输出格式只保留每行有效尾部无多余空格。复杂度分析构建BST\texttt{BST}BST每个节点插入时从根向下查找最坏O(N2)O(N^2)O(N2)退化为链但N80N 80N80可以接受。若使用平衡树可优化但无需。中序遍历O(N)O(N)O(N)。填充网格O(N×cols)O(N \times \textit{cols})O(N×cols)其中colsN\textit{cols} NcolsN因为遍历每个节点填充其横线区间区间长度不超过NNN故最坏O(N2)O(N^2)O(N2)但N80N 80N80。输出O(rows×cols)O(N2)O(\textit{rows} \times \textit{cols}) O(N^2)O(rows×cols)O(N2)。整体复杂度O(N2)O(N^2)O(N2)空间复杂度O(N2)O(N^2)O(N2)完全满足题目限制。代码实现// Boring Homework// UVa ID: 12010// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.020s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structNode{intval,left,right,depth,col;Node():val(0),left(-1),right(-1),depth(0),col(-1){}};voidinsertNode(vectorNodetree,introot,intval,intdepth){if(root-1){rootval-1;tree[root].valval;tree[root].depthdepth;return;}if(valtree[root].val){if(tree[root].left-1){tree[root].leftval-1;tree[val-1].valval;tree[val-1].depthdepth1;}elseinsertNode(tree,tree[root].left,val,depth1);}else{if(tree[root].right-1){tree[root].rightval-1;tree[val-1].valval;tree[val-1].depthdepth1;}elseinsertNode(tree,tree[root].right,val,depth1);}}voidinorderAssignCol(vectorNodetree,intcur,intidx){if(cur-1)return;inorderAssignCol(tree,tree[cur].left,idx);tree[cur].colidx;inorderAssignCol(tree,tree[cur].right,idx);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;for(intcaseNo1;caseNoT;caseNo){intN;cinN;vectorintseq(N);for(inti0;iN;i)cinseq[i];vectorNodetree(N);introot-1;for(inti0;iN;i)insertNode(tree,root,seq[i],0);intmaxDepth0;for(inti0;iN;i)if(tree[i].depthmaxDepth)maxDepthtree[i].depth;intcolIdx0;inorderAssignCol(tree,root,colIdx);introws2*maxDepth1;intcolsN;vectorvectorchargrid(rows,vectorchar(cols, ));// 放置节点 ofor(inti0;iN;i){intr2*tree[i].depth;intctree[i].col;grid[r][c]o;}// 放置 | 和 非根节点for(inti0;iN;i){if(tree[i].depth0){intr2*tree[i].depth;intctree[i].col;grid[r-1][c]|;grid[r-2][c];}}// 画横线 -对有孩子的节点for(inti0;iN;i){intlctree[i].left,rctree[i].right;if(lc-1rc-1)continue;intr2*tree[i].depth;intleftCol(lc!-1)?tree[lc].col:tree[i].col;intrightCol(rc!-1)?tree[rc].col:tree[i].col;if(leftColrightCol)swap(leftCol,rightCol);for(intcleftCol;crightCol;c)if(grid[r][c] )grid[r][c]-;}// 输出图形保留前导空格去除尾部空格coutCase #caseNo:\n;for(intr0;rrows;r){intlast-1;for(intc0;ccols;c)if(grid[r][c]! )lastc;if(last-1){cout\n;continue;}for(intc0;clast;c)coutgrid[r][c];cout\n;}}return0;}总结本题的关键在于将二叉树的结构转化为有规律的二维坐标映射。通过中序遍历确定列号深度决定行号巧妙地同时满足了左右子树分离和垂直对齐的要求。绘图过程中分步放置不同符号并注意保留已有字符保证了图形的正确性。该解法利用了NNN较小的特点直接使用O(N2)O(N^2)O(N2)的二维数组思路清晰且易于实现。若NNN增大可考虑压缩存储或动态扩展但本题限制下当前方案已足够。技巧总结中序遍历天然满足BST\texttt{BST}BST的列分离性质。深度与行号的222倍关系实现了父与子的垂直关联。填充横线时只填充空格避免覆盖其他符号确保连接线不会破坏已有结构。