元素选择器

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

构建每个元素的父指针，候选元素沿祖先链从后向前贪心匹配后代选择器。

OJ: shumeng

题目 ID: CSP201809C

难度:普及+/提高-

标签:树字符串模拟栈

日期: 2026-07-31 16:21

形式化题目

给定一棵由 $n$ 行文本描述的树（.. 缩进表示层级，行号即节点编号），每个节点有标签（大小写不敏感）与可选的 id 属性（大小写敏感）。给出 $m$ 个选择器，每个选择器由若干段组成：一段是标签（如 p）或 id（如 #main），多段之间用空格分隔表示后代关系。对每个选择器，按行号从小到大输出所有被选中的节点行号。

思路

朴素做法

为每个元素显式收集从根到它的祖先链，再从根向下顺序匹配选择器前面的各段，最后检查元素自身是否匹配最后一段。逻辑直观但每次都要重建一条链。

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/**
 * 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:41
 */
// brute.cpp：小数据暴力解，为每个元素显式收集祖先链后，按选择器从根向下匹配。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
string tag[MAXN], id[MAXN];
int parent[MAXN];

string to_lower_string(string value) {
    for (int i = 0; i < (int)value.size(); i++) {
        value[i] = (char)tolower((unsigned char)value[i]);
    }
    return value;
}

bool match_part(int node, const string &part) {
    if (part[0] == '#') {
        return id[node] == part.substr(1);
    }
    return tag[node] == part;
}

// 把当前元素的祖先链（根到它）显式收集出来，再从根开始顺序匹配选择器各段。
bool match_selector(int node, const vector<string> &parts) {
    vector<int> chain;
    for (int current = node; current != -1; current = parent[current]) {
        chain.push_back(current);
    }
    reverse(chain.begin(), chain.end());

    // 从根向下尽量匹配前面的各段，最后一段要求当前节点自己匹配。
    int need = 0;
    for (int i = 0; i < (int)chain.size() - 1 && need + 1 < (int)parts.size(); i++) {
        if (match_part(chain[i], parts[need])) {
            need++;
        }
    }
    return need + 1 == (int)parts.size() && match_part(node, parts.back());
}

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

    cin >> n >> m;
    string line;
    getline(cin, line);

    int last_at_depth[MAXN];
    fill(last_at_depth, last_at_depth + MAXN, -1);
    for (int i = 1; i <= n; i++) {
        getline(cin, line);
        int depth = 0;
        while (line[2 * depth] == '.') {
            depth++;
        }
        int start = 2 * depth;
        int space = (int)line.find(' ', start);
        if (space == -1) {
            tag[i] = to_lower_string(line.substr(start));
        } else {
            tag[i] = to_lower_string(line.substr(start, space - start));
            id[i] = line.substr(space + 2);
        }
        parent[i] = depth == 0 ? -1 : last_at_depth[depth - 1];
        last_at_depth[depth] = i;
    }

    for (int query = 1; query <= m; query++) {
        getline(cin, line);
        stringstream input(line);
        vector<string> parts;
        string part;
        while (input >> part) {
            if (part[0] != '#') {
                part = to_lower_string(part);
            }
            parts.push_back(part);
        }
        vector<int> answer;
        for (int node = 1; node <= n; node++) {
            if (match_selector(node, parts)) {
                answer.push_back(node);
            }
        }
        cout << answer.size();
        for (int i = 0; i < (int)answer.size(); i++) {
            cout << ' ' << answer[i];
        }
        cout << '\n';
    }

    return 0;
}

构建父指针

读入文档时维护每个深度最后出现的元素。当前行深度为 $d$ ，它的父亲就是深度 $d-1$ 的最后元素，由此得到每个元素的 parent 指针。标签与标签选择器全部转为小写；id 保留原样以满足大小写敏感规则。

沿祖先链从后向前贪心匹配

对选择器 A B C，枚举每个元素作为候选 C。候选先匹配 C，然后沿父指针向上找最近的 B，再继续向上找 A。祖先链是一条线：若最近可匹配的祖先都无法接上更早的部分，更远的祖先也不会更有利，所以从右到左贪心匹配是正确的。

代码

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/**
 * 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:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
string tag[MAXN], id[MAXN]; // 每个元素的小写标签与 id 属性
int parent[MAXN];           // 每个元素的父元素行号，根元素为 -1

// 标签统一转小写，id 保持原样。
string to_lower_string(string value) {
    for (int i = 0; i < (int)value.size(); i++) {
        value[i] = (char)tolower((unsigned char)value[i]);
    }
    return value;
}

// 判断节点 node 是否匹配选择器的一段：'#' 开头是 id 选择器，否则是标签选择器。
bool match_part(int node, const string &part) {
    if (part[0] == '#') {
        return id[node] == part.substr(1);
    }
    return tag[node] == part;
}

// 判断节点 node 是否被整个后代选择器选中，从最后一段向根贪心匹配。
bool match_selector(int node, const vector<string> &parts) {
    int last = (int)parts.size() - 1;
    if (!match_part(node, parts[last])) {
        return false;
    }

    node = parent[node];
    for (int index = last - 1; index >= 0; index--) {
        // 沿祖先链向上找最近一段能匹配的祖先。
        while (node != -1 && !match_part(node, parts[index])) {
            node = parent[node];
        }
        if (node == -1) {
            return false;
        }
        node = parent[node];
    }
    return true;
}

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

    cin >> n >> m;
    string line;
    getline(cin, line);

    int last_at_depth[MAXN]; // 每个缩进深度最后出现的元素行号
    fill(last_at_depth, last_at_depth + MAXN, -1);

    // 读入文档：缩进层级决定父子关系。
    for (int i = 1; i <= n; i++) {
        getline(cin, line);
        int depth = 0;
        while (line[2 * depth] == '.') {
            depth++;
        }
        int start = 2 * depth;
        int space = (int)line.find(' ', start);
        if (space == -1) {
            tag[i] = to_lower_string(line.substr(start));
        } else {
            tag[i] = to_lower_string(line.substr(start, space - start));
            id[i] = line.substr(space + 2);
        }
        parent[i] = depth == 0 ? -1 : last_at_depth[depth - 1];
        last_at_depth[depth] = i;
    }

    for (int query = 1; query <= m; query++) {
        getline(cin, line);
        stringstream input(line);
        vector<string> parts;
        string part;
        while (input >> part) {
            if (part[0] != '#') {
                part = to_lower_string(part);
            }
            parts.push_back(part);
        }

        // 枚举每个元素作为匹配的最后一段。
        vector<int> answer;
        for (int node = 1; node <= n; node++) {
            if (match_selector(node, parts)) {
                answer.push_back(node);
            }
        }
        cout << answer.size();
        for (int i = 0; i < (int)answer.size(); i++) {
            cout << ' ' << answer[i];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

设选择器段数为 $k$ 、树高为 $H$ 。每个查询枚举 $n$ 个候选元素并在祖先链上扫描，时间复杂度 $O(n(H+k))$ ，空间复杂度 $O(n)$ 。本题 $n \le 100$ ，足够直接。

总结

后代选择器不要求相邻父子关系，只要求祖先关系。把缩进文档转成父指针后，查询就变成在一条祖先链上匹配有序子序列；标签和 id 的大小写规则必须分别处理。

时间限制： 1.0 秒

空间限制： 256 MB

题目背景

层叠样式表（Cascading Style Sheets，简写 CSS）是一种用来为结构化文档（如 HTML 文档）添加样式（字体、间距和颜色等）的计算机语言。

例如，对于以下的 HTML 文档：

html

1
2
3
4
5
6
7
8
9
10<html>
  <head>
    <title>Sample</title>
  </head>
  <body>
    <h1>Hello</h1>
    <p id="subtitle">Greetings</div>
    <p>Hello, world!</p>
  </body>
</html>

配合以下 CSS 片段可以为其中的标题和段落设置相应的格式：

css

1
2h1 { font-weight: bold; }
#subtitle { font-size: 12px; }

这段 CSS 片段为前面 HTML 文档添加了样式，使得标题 Hello（第 6 行 <h1> 和 </h1> 标签之间的内容）具有粗体，使得段落 Greetings（第 7 行 <p id="subtitle"> 和 <\p> 标签之间的内容）具有 12 个像素的字体大小。

这里，CSS 片段第 1 行中出现的 h1 是一个选择器，它选中了 HTML 文档第 6 行的 h1 元素。CSS 片段第 2 行中出现的 #subtitle 也是一个选择器，选中了 HTML 文档第 7 行 id 属性为 subtitle 的 p 元素。注意它并没有选中 HTML 文档第 8 行不带属性的 p 元素。

题目描述

本题要实现一个简化版的元素选择器。给出一个结构化文档，和若干个选择器，对每个选择器找出文档中所对应选中的元素。

结构化文档

结构化文档由元素组成，一个元素可以包含若干个子元素（可以没有）。一个文档有一个根元素，在整体上形成树的结构。以下是本题结构化文档的一个例子：

plain

1
2
3
4
5
6
7
8
9
10
11html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #one
......div
........p #two

文档中每行表示一个元素，元素的标签由一个或者多个字母或数字组成。标签大小写不敏感，例如 div、Div、DIV 都是同一类标签。
元素可以附加一个 id 属性，属性值也是由一个或者多个字母或数字组成，之前有一个井号 #。id 属性大小写敏感，例如 a 和 A 是两个不同的 id。如果元素有 id 属性，标签和属性之间用一个空格字符分隔。
标签之前的缩进表示元素之间的包含关系：一个元素 $E$ 所在行之后连续的缩进更深的行代表的元素是元素 $E$ 的后代元素，其中缩进恰好深一层的是元素 $E$ 的子元素。为了便于观察，每一级缩进用两个小数点符号 .. 表示。

选择器

本题中会出现的选择器有三种，分别为：

标签选择器：用标签来表示。例如 p 表示选择标签为 p 的所有元素。
id 选择器：用 id 属性来表示。例如 #main 表示选择 id 属性为 main 的所有元素。题目保证文档中不同的元素不会有相同的 id 属性。
后代选择器：复合表达式，格式为 A B，其中 A 和 B 均为标签选择器或 id 选择器，中间用一个空格字符分隔，表示选择满足选择器 B 的所有元素，且满足这些元素有祖先元素满足选择器 A。例如，选择器 div p 在上面的文档中会选中最后一行的元素 p，但不会选中 id 属性为 subtitle 的那个元素 p。注意，后代选择器可以有更多的组成部分构成，div p 是一个两级的后代选择器，而 div div p 则是一个三级的后代选择器。

输入格式

从标准输入读入数据。

输入第一行是两个正整数 $n$ 和 $m$ ，分别表示结构化文档的行数，和待查询的选择器的个数，中间用一个空格字符分隔。

第 $2$ 行至第 $n + 1$ 行逐行给出结构化文档的内容。

第 $n + 2$ 行至第 $n + m + 1$ 行每行给出一个待查询的选择器。记第 $n + 1 + i$ 行的 CSS 选择器为 $s_i$ ， $1\leq i \leq m$ 。

保证输入的结构化文档和待查询的选择器都是合法的。

输出格式

输出到标准输出。

输出共 $m$ 行，每行有若干个整数。

第 $i$ 行表示选择器 $s_i$ 选中的结果 $(1\leq i \leq m)$ 。其中第一个整数 $r_i$ 表示 $s_i$ 选中的元素个数。随后 $r_i$ 个整数，分别表示选中元素在结构化文档中出现的行号（行号从 $1$ 开始编号）。

行号按从小到大排序，相邻整数之间用一个空格字符分隔。

注意：本题中选择不具有继承性，与一般的 CSS 规则不同。即：如果父元素被选择，但子元素未被选择，则只输出父元素的行号。

input1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1711 5
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #one
......div
........p #two
p
#subtitle
h3
div p
div div p

output1

样例 1 解释

对于样例中查询的 5 个选择器:

p 选中所有的元素 p;
#subtitle 选中第 6 行 id 属性为 subtitle 的元素 p;
由于没有标签为 h3 的元素，因此 h3 没有选中任何元素;
第 9 行和第 11 行的 p 元素都有祖先是 div 元素，而第 6 行的 p 元素没有祖先是 div 元素;
div div p 要求选中的 p 元素有两级祖先都是 div 元素，只有第 11 行的 p 元素满足这个条件。

子任务

$1\le n\le 100$
$1\le m\le 10$
结构化文档和待查询的选择器每行长度不超过 80 个字符(不包括换行符)。保证输入的结构化文档和待查询的选择器都是合法的。

测试点编号	结构化文档级数	id 属性	待查询选择器的类型
$1$	$=1$	无	标签
$2$	$=2$	无	标签
$3$	$=2$	有	标签、id
$4$	$=2$	无	标签、后代（两级，不含 id）
$5$	$>2$	无	标签
$6$	$>2$	有	标签、id
$7$	$>2$	无	标签、后代（两级，不含 id）
$8$	$>2$	有	标签、id、后代（两级）
$9$	$>2$	无	标签、后代（多级，不含 id）
$10$	$>2$	有	标签、id、后代（多级）

与官方数据不同，本评测链接中全文无缩进的结构化文档级数视为 $0$ 。

提示

多级的后代选择器在匹配时，可以采用贪心的策略：除最后一级外，前面的部分都可以尽量匹配层级小的元素。