Markdown 渲染器

GitHub跳转原题关系图 Canvas 关系图返回列表

按段落和项目列表分块，利用列计数器模拟折行、缩进和空格删除。

OJ: shumeng

题目 ID: CSP202006C

难度:提高+/省选-

标签:字符串模拟解析

日期: 2026-07-31 16:21

形式化题目

按题目规则渲染简化 Markdown 文本：空白行分隔段落和项目列表，段落各行去首尾空格后用一个空格连接；项目以 * 开头，续行以两个空格开头。只输出最终终端占用的行数。

思路

整个模拟拆成两层：先划分输入块，再按列号逐字符渲染。

块划分

空白行：结束当前块，继续扫描；
* 开头的行：开始一个项目，其后以两个空格开头的非空白行都是它的续行；
其它非空白行：组成普通段落。

每个新块在渲染前先与上一个块空一行。

字符输出器

把段落或项目的文本行去首尾空格后，用单个空格连接成一段连续文本。输出器维护当前行已写列数 column 和总行数 row_count：

逐字符写入，每写一个字符 column 加一；
当 column 到达终端宽度 w 时，先删除待写文本开头的连续空格，若仍有字符才另起一行；
普通段落的新行缩进为 0；项目首行与续行都从第 3 列开始，对应 · 或三个空格。

代码

cpp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

// 判断一行是否只由空格组成（空白行分隔段落和项目列表）
bool is_blank(const string &text) {
    for (int i = 0; i < (int)text.size(); i++) {
        if (text[i] != ' ') return false;
    }
    return true;
}

// 判断一行是否是项目首行：以 "* " 开头
bool is_item_start(const string &text) {
    return text.size() >= 2 && text[0] == '*' && text[1] == ' ';
}

// 判断一行是否是项目续行：以两个空格开头且非空白行
bool is_item_continuation(const string &text) {
    return text.size() >= 2 && text[0] == ' ' && text[1] == ' ' && !is_blank(text);
}

// 去掉一行首尾的连续空格
string trim(const string &text) {
    int left = 0, right = (int)text.size() - 1;
    while (left <= right && text[left] == ' ') left++;
    while (left <= right && text[right] == ' ') right--;
    return text.substr(left, right - left + 1);
}

// 把一个块的所有文本行去首尾空格后，用单个空格连接成一段文本
string join_lines(const vector<string> &line) {
    string text;
    for (int i = 0; i < (int)line.size(); i++) {
        string part = trim(line[i]);
        if (part.empty()) continue;
        if (!text.empty()) text += ' ';
        text += part;
    }
    return text;
}

// 终端输出器：维护当前行已写列数和总行数，负责折行与缩进
struct Painter {
    int width, row_count = 0, column = 0;

    // 另起一行，行首缩进 indent 个列
    void start_line(int indent) {
        row_count++;
        column = indent;
    }

    // 每个新块与之前的块之间空一行
    void start_block() {
        if (row_count > 0) row_count++;
    }

    // 逐字符写入文本，写满宽度时先删除待写开头空格，再折行
    void write_text(const string &text, int first_indent, int next_indent) {
        int position = 0;
        start_line(first_indent);
        while (position < (int)text.size()) {
            if (column == width) {
                // 折行前删除待写文本开头的连续空格
                while (position < (int)text.size() && text[position] == ' ') position++;
                if (position == (int)text.size()) break;
                start_line(next_indent);
            }
            column++;
            position++;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Painter painter;
    cin >> painter.width;
    string line;
    getline(cin, line);   // 读掉宽度数字后的换行
    vector<string> source;
    while (getline(cin, line)) source.push_back(line);

    int position = 0;
    while (position < (int)source.size()) {
        if (is_blank(source[position])) {
            position++;
            continue;
        }
        painter.start_block();
        // 普通段落：连续的、非空白、非项目首行的行
        if (!is_item_start(source[position])) {
            vector<string> paragraph;
            while (position < (int)source.size() && !is_blank(source[position])
                    && !is_item_start(source[position])) {
                paragraph.push_back(source[position++]);
            }
            painter.write_text(join_lines(paragraph), 0, 0);
            continue;
        }

        // 项目列表：连续的 "* " 开头行，各自跟随两个空格开头的续行
        while (position < (int)source.size() && is_item_start(source[position])) {
            vector<string> item;
            item.push_back(source[position++].substr(2));   // 去掉行首的 "* "
            while (position < (int)source.size() && is_item_continuation(source[position])) {
                item.push_back(source[position++].substr(2));   // 去掉开头的两个空格
            }
            painter.write_text(join_lines(item), 3, 3);
        }
    }
    cout << painter.row_count << '\n';

    return 0;
}

复杂度

设输入字符数为 $L$ 。解析和渲染都是线性扫描，时间复杂度为 $O(L)$ ，空间复杂度为 $O(L)$ 。

总结

这类格式模拟的难点是严格区分输入结构和输出规则。先确定块边界，再由统一的字符输出器处理宽度、缩进和折行，能把各种边界条件从解析逻辑中剥离出来。

图示解析

text

1
2
3
4
5原始行
|- 空白行：结束当前块
|- * 空格：读取项目列表
`- 其它行：读取普通段落
   `- 连接逻辑文本，按列号逐字符渲染并计数

块划分只解释输入属于什么结构；字符输出器只解释如何占用终端列。把这两层分开后，项目的三列缩进只是输出器的一个参数。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

Markdown 是一种轻量级的标记语言，它可以用较为简单的符号来标记文本中的成分的意义。通过套用适当的样式，即可生成一份美观的文档。Markdown 由于其轻量级的特性，深受喜爱，并在各种方面得到了广泛的运用。本题需要你解析并渲染简化的 Markdown 文档。

题目描述

本题中，你需要按照下述要求，在终端屏幕上渲染简单的 Markdown 文档。终端屏幕，可以被视为宽度为 $w$ 单位，长度为无限长单位的方格，每个方格中可以被填充至多一个字符。可选地，每个方格中的字符可以带有一定的样式。在这个终端屏幕中，可以按照下列方法，渲染 Markdown 文档中的各个元素。

段落

在 Markdown 文档中，换行符将文档分为若干行。仅包含零个或多个空格的行被称为“空白行”。空白行将整个文档分割成了若干段落。例如，下面的示例文档中包含有 5 个空白行，行号分别是 2、6、7、9、10，他们将该文档分成了 3 个段落。为了能够便于你阅读，“˽”符号表示空格。“¬”符号表示换行符。

plain

1
2
3
4
5
6
7
8
9
10CSP¬
¬
CSP˽is¬
a˽real˽realrealrealrealreal˽¬
˽˽˽˽˽competition.¬
¬
˽˽˽¬
Come˽˽˽and˽˽˽join˽˽˽us˽˽˽¬
¬
¬

在渲染一个段落前，应该去掉每行首尾的连续空格。如果一个段落包含有多行文本，那么将各个行用一个空格连接起来，形成一个不含换行符的连续的段落文本。渲染段落时，应当首先与之前的段落或项目列表空出一行的间距，从新的一行开始连续将段落中的文本从左至右渲染在屏幕上。如果段落中的字符超出了终端的宽度，那么则应当从终端的下一行开始继续渲染其余的文本。如果余下的文本恰好是以空格字符开头，那么应该将这些连续的空格字符删除。上述文本按照这样的规则，在一个宽度为 10 的终端中渲染，其结果为：

plain

1
2
3
4
5
6
7
8
9
10
11
12
13             1
   +1---5----0+
1  |CSP       |
2  |          |
3  |CSP is a r|
4  |eal realre|
5  |alrealreal|
6  |real compe|
7  |tition.   |
8  |          |
9  |Come   and|
10 |join   us |
   +----------+

项目列表

“项目”由连续的若干行文本组成，其中第一行必须以星号和空格（*˽）开头，其余的行（如果有）为以两个空格（˽˽）开头的非空白行。“项目列表”由连续的一个或多个项目组成，其中各个项目之间没有空白行或开头不是两个空格的行。如果两个项目列表之间没有空白行或开头不是两个空格的行，那么它们应当被视为一个项目列表。例如，下列文本中，行 1 、行 3-5、行 6-7、行 9 和行 10 组成了 5 个项目，它们分别属于 3 个项目列表，因为它们被空行（行 3）、段落（行 8）分隔开来。

plain

1
2
3
4
5
6
7
8
9
10*˽CSP¬
˽˽˽˽¬
*˽˽˽CSP˽is¬
˽˽*˽a˽real˽˽¬
˽˽˽˽˽competition.¬
*˽¬
˽˽*˽Come!˽˽˽and˽˽˽join.¬
*Tel:¬
*˽12345¬
*˽¬

在渲染一个项目列表时，应当首先与之前的段落或项目列表空出一行的间距，从新的一行开始连续渲染每个项目。在渲染一个项目前，先把这个项目的各个文本行首的两个空格字符或星号空格字符去掉。渲染时，从新的一行开始输出空格、点号、空格（˽·˽）符号，然后按照渲染一个段落的规则，渲染该项目中的各个文本行。但是，在终端上输出一个项目的随后的行时，应当插入三个空格（˽˽˽），以使这些行与第一行对齐。特别地，如果一个项目的首行除行首的星号空格字符外，没有其它的字符，那么应当直接从项目的余下的行开始渲染该项目（例如上述文本第 6 行）；如果仅有一行，那么认为这个项目渲染结束（例如上述文本第 10 行）。上述文本按照该规则，在一个宽度为 10 的终端中渲染，其结果为：

plain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18             1
   +1---5----0+
1  | · CSP    |
2  |          |
3  | · CSP is |
4  |   * a rea|
5  |   l compe|
6  |   tition.|
7  | · * Come!|
8  |   and   j|
9  |   oin.   |
10 |          |
11 |*Tel:     |
12 |          |
13 | · 12345  |
14 | ·        |
   +----------+

这里，原文本第 2 行是空白行，将前后两个项目分成了两个项目列表，因此在输出终端中，二者之间有空行分隔。原文本第 8 行，开头不是星号和空格，因此是一个单独的段落。

输入格式

从标准输入读入数据。

输入第一行包含一个数字 $w$ ，是终端宽度。随后从第二行开始，是被渲染的文本。

输出格式

输出到标准输出。

输出一行，是一个数字，表示渲染所需终端行数。

input1

1
2
3
4
5
6
7
8
9
1010
CSP

CSP is
a real realrealrealrealreal 
     competition.

   
Come   and   join   us

output1

样例 1 解释

该输入是本题第一个例子，渲染共需 10 行。

input2

1
2
3
4
5
6
7
8
9
10
1110
* CSP
    
*   CSP is
  * a real  
     competition.
* 
  * Come!   and   join.
*Tel:
* 12345
*

output2

样例 2 解释

该输入是本题第二个例子，渲染共需 14 行。

子任务

对于 $10\%$ 的测试点，仅包含段落，且每个段落仅包含一行文本，且每行文本长度不超过 $w$ ；

对于 $20\%$ 的测试点，仅包含段落，且每个段落仅包含一行文本；

对于 $40\%$ 的测试点，仅包含段落；

对于 $60\%$ 的测试点，仅包含段落和至多一个项目列表，且输入数据大小在 2.5 MiB 以内；

对于 $80\%$ 的测试点，包含零个或多个段落和项目列表，且 $w \leq 10^3$ ，输入数据大小在 5 MiB 以内；

对于 $100\%$ 的测试点，包含零个或多个段落和项目列表， $4 \leq w \leq 10^4$ ，输入数据中仅包括 ASCII 字符，输入数据大小在 20 MiB 以内。

提示

本题需要你判断读取输入是否到达末尾。在 C 语言中 fgets 函数可以读取一段文本，直到换行符或给定的长度为止；feof 可以检查是否读到了文件末尾。在 C++ 中，std::istream::getline 函数可以读取一段文本，直到换行符或给定的长度为止；std::ios::eof 函数可以检查上一次读取是否因读取到了文件末尾而发生错误。在 Java 中，java.io.BufferedReader.readLine 函数可以一次读取一行文本，并在到达文件末尾的情况下返回 null。在 Python 中，io.TextIOBase.readline 函数可以一次读取一行文本，并在到达文件末尾的情况下返回空字符串。