Znzryb's Blog
0%

2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——E. Visualize This

Posted on

题目大意

题目归纳

给定一个数组大小 nn (1≤n≤1041 \le n \le 10^4)，需要构建并按特定格式可视化一个线段树。

线段树构建规则

  • 根节点：对应半开区间 [0,n)[0, n)。

  • 分裂规则：对于非叶子节点 [L,R)[L, R)，其中点为 M=⌊(L+R)/2⌋M = \lfloor (L+R)/2 \rfloor。左子节点为 [L,M)[L, M)，右子节点为 [M,R)[M, R)。

  • 叶子节点：对应区间长度为 1 的节点 [i,i+1)[i, i+1)。

可视化输出规则

  • 分层输出：树的根在第一行，子节点在下一行，以此类推。

  • 节点格式：显示为 [L;R)。

  • 分隔竖线：如果节点 [L,R)[L, R) 不是叶子，必须在其分号 ; 的正下方（即同一列），从该节点的下一行开始直到整个图形的最后一行，绘制竖线 |。这表示左右子树的物理分隔。

  • 排版约束：

    • 同一行内的元素（节点文本或竖线）之间至少保留 1 个空格。
    • 在满足对齐条件的前提下，空格数量应尽可能少。
    • 整个图形靠左对齐（即至少有一行的行首没有空格）。
    • 行末不得有多余空格。

样例展示与解释

样例 1 (n=3n=3)

1
2
3
    [0;3)
[0;1) |     [1;3)
      | [1;2) | [2;3)

解释：

  • 第 1 行：根节点 [0,3)[0, 3)。其中点为 1，分号 ; 所在列决定了后续行的主分隔线位置。

  • 第 2 行：

    • 左子节点 [0,1)[0, 1)。
    • 中间是根节点 [0,3)[0, 3) 延伸下来的竖线 |。
    • 右子节点 [1,3)[1, 3)。

  • 第 3 行：

    • 左侧空位（因为 [0,1)[0, 1) 是叶子）。
    • 根节点的竖线 | 继续延伸。
    • [1,3)[1, 3) 分裂为 [1,2)[1, 2) 和 [2,3)[2, 3)，中间由 [1,3)[1, 3) 的分号 ; 延伸出的竖线 | 分隔。

  • 对齐：所有竖线 | 都严格位于其父节点 ; 的正下方，且元素间距最小化。

样例 2 (n=7n=7)

1
2
3
4
                    [0;7)
    [0;3)             |             [3;7)
[0;1) |     [1;3)     |     [3;5)     |     [5;7)
      | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)

解释：

  • 展示了更深层的结构。每一层新产生的分支节点都会在其 ; 下方产生一条新的竖线，一直延伸到底部。

  • 例如，根节点 [0,7)[0, 7) 的竖线贯穿了第 2、3、4 行。

  • 第 2 行的节点 [0,3)[0, 3) 和 [3,7)[3, 7) 的竖线分别贯穿了第 3、4 行。

思路讲解

这道题目主要就是考验你的一个实现的这个能力。比较建议的实现方法呢，就是这个宽度的计算呢，先使用一个函数进行总的宽度的计算。然后需要注意啊，这道题目不允许出现后导空格，就是它不会自动忽略后导空格。所以你需要在输出的时候把所有的后导空格给 pop back 给 pop 掉。

https://codeforces.com/gym/106169/submission/363482617 因为后导空格 WA 的一发。

然后还有一个点呢，就是这道题目它使用的是左臂右开，0 base 的，那么你最好也仿照它使用左臂右开0 base 的，不要把它，不要用1 base 的做这道题目，1 base 的做这道题目。是会有问题的，因为因为这个嗯，因为一加一个数，然后再 向下整除二，和0加一个数再向下整除二，它其实这个区间是会有不同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void visualize() {
    widths.resize(4 * N + 2);
    cal_visual_w(1, 1);
    grid.resize(mx_layer + 2, string(widths[1], ' '));
    visualize(1, 0, 1);
    for (int i = 1; i <= mx_layer; ++i) {
        while (!grid[i].empty() && grid[i].back()==' ') {
            grid[i].pop_back();
        }
        cout << grid[i] << "\n";
    }
}

void cal_visual_w(ll u, ll layer) {
    mx_layer = max(mx_layer, layer);
    if (infos[u].l == infos[u].r-1) {
        widths[u] = infos[u].to_string().size();
        return;
    }
    cal_visual_w(u << 1, layer + 1);
    widths[u] = widths[u << 1] + 3;
    cal_visual_w(u << 1 | 1, layer + 1);
    widths[u] += widths[u << 1 | 1];
}

// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
    if (infos[u].l == infos[u].r-1) {
        string label = infos[u].to_string();
        for (ll i = 0; i < label.size(); ++i) {
            grid[layer][sc + i] = label[i];
        }
        return;
    }
    visualize(u << 1, sc, layer + 1);
    string label = infos[u].to_string();
    ll pos = label.find(';');
    ll labStart = sc + widths[u << 1] + 1 - pos;
    for (int i=1;i<=mx_layer;++i) {
        if (layer+i>mx_layer) break;
        grid[layer + i][sc + widths[u << 1] + 1] = '|';
    }
    // grid[layer + 1][sc + widths[u << 1] + 1] = '|';
    // if (layer+2 <= mx_layer) {
    //     grid[layer+2][sc + widths[u << 1] + 1]='|';
    // }
    for (ll i = 0; i < label.size(); ++i) {
        grid[layer][labStart + i] = label[i];
    }
    visualize(u << 1 | 1, sc + widths[u << 1] + 3, layer + 1);
}

AC代码

AC
https://codeforces.com/gym/106169/submission/363483057