CCF CSP 201809-3.元素选择器

发表于 | 更新于 | 分类于 | 浏览 次
字数统计: 1.4k

分析：

定义结构体（类）存储每一个元素节点

1
2
3
4
5
typedef struct Node {
	// 当前节点位于文档树中第几层
	int level;
	string label, id;
} Element;

使用C++中的vector<Element>（Java中使用List<Element>）存储整个文档。

在文档中，元素e的父节点就是e前面第一个level小于e的元素。

查询分为以下三种情况：

（1）id选择器。题目告诉我们，文档中不同的元素不会有相同的id属性。

（2）标签选择器。匹配的标签可能有很多个。

（3）后代选择器。题目提示我们：除最后一级外，前面的部分都可以尽量匹配层级小的元素。

因此，我们可以从后代选择器的最后一个选择器selector开始，在文档中寻找匹配的元素。如果能找到这样的元素e，则在e的祖先元素中，寻找与selector的前一个选择器相匹配的元素。当遍历到根结点或者已经找到与后代选择器相匹配的元素时，循环结束。

注意：

1.id属性区分大小写，而标签不区分大小写。

2.后代选择器：A B，其中A和B均为标签选择器或者id选择器，表示选择满足选择器B的所有元素，且满足这些元素有祖先元素满足选择器A。因此，只要有祖先元素满足选择器A即可，父元素并不一定要满足选择器A。

  • C++版
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
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

typedef struct Node {
	// 当前节点位于文档树中第几层
	int level;
	string label, id;
} Element;

// 将字符串转换为小写形式
string to_lower(string tag) {
	for (int i = 0; i < tag.size(); i++) {
		if ('A' <= tag[i] && tag[i] <= 'Z') {
			tag[i] += 32;
		}
	}
	return tag;
}

int main() {
	int n, m;
	cin >> n >> m;
	getchar();

	vector<Element> doc;
	string line;
	int parent = 1;
	while (n--) {
		getline(cin, line);
		Element e;

		// 计算当前节点在文档树中的层级
		int count = 0;
		while (line[count] == '.') {
			count++;
		}
		e.level = count / 2;

		// 处理标签和id
		int index = line.find(" ");
		if (index != string::npos) {
			e.label = to_lower(line.substr(count, index - count));
			e.id = line.substr(index + 1, line.size() - index - 1);
		} else {
			e.label = to_lower(line.substr(count));
			e.id = "";
		}
		doc.push_back(e);
	}

	while (m--) {
		getline(cin, line);
		vector<int> pos;

		// 若为id选择器或者标签选择器
		if (line.find(" ") == string::npos) {
			for (int i = 0; i < doc.size(); i++) {
				if (doc[i].id == line || doc[i].label == to_lower(line)) {
					pos.push_back(i + 1);
				}
			}
		} else {
			stringstream ss;
			ss << line;

			// 存储后代选择器中的所有选择器
			vector<string> selectors;
			while (ss >> line) {
				// 若为标签，则转换为小写形式
				if (line[0] != '#') {
					line = to_lower(line);
				}
				selectors.push_back(line);
			}

			string last = selectors[selectors.size() - 1];
			for (int i = 0; i < doc.size(); i++) {
				// 如果当前元素与后代选择器的最后一个选择器不匹配，则继续循环
				if (last != doc[i].id && last != doc[i].label) {
					continue;
				}

				int index = selectors.size() - 2;
				int level = doc[i].level;
				for (int k = i; k >= 0 && index >= 0; k--) {
					Element e = doc[k];
					string selector = selectors[index];
					// 寻找父节点（level比当前节点小的第一个节点）
					if (e.level < level) {
						level = e.level;
						// 若父节点匹配当前选择器，则继续匹配；否则，继续向上寻找祖先节点
						if (selector == e.id || selector == e.label) {
							index--;
						}
					}
				}
				// 如果完全匹配后代选择器
				if (index < 0) {
					pos.push_back(i + 1);
				}
			}
		}
		cout << pos.size();
		for (int i = 0; i < pos.size(); i++) {
			cout << ' ' << pos[i];
		}
		cout << endl;
	}
	return 0;
}
  • Java版
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class Element {
		int level;
		String label, id;

		public Element(int level, String label, String id) {
			this.level = level;
			this.label = label;
			this.id = id;
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		scan.nextLine();

		List<Element> doc = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			String line = scan.nextLine();
			int level = 0;
			String label, id;

			// 计算当前节点在文档树中的层级
			int count = 0;
			while (line.charAt(count) == '.') {
				count++;
			}
			level = count / 2;
			
			// 处理标签和id
			int index = line.indexOf(" ");
			if (index == -1) {
				label = line.substring(count);
				id = "";
			} else {
				label = line.substring(count, index);
				id = line.substring(index + 1, line.length());
			}
			doc.add(new Element(level, label, id));
		}

		for (int i = 0; i < m; i++) {
			String selector = scan.nextLine();

			List<Integer> list = new ArrayList<>();

			// 若为id选择器或者标签选择器
			if (!selector.contains(" ")) {
				for (int j = 0; j < doc.size(); j++) {
					Element e = doc.get(j);
					if (selector.equalsIgnoreCase(e.label) || selector.equals(e.id)) {
						list.add(j + 1);
					}
				}
			} else {
				String[] selectors = selector.split(" ");
				String last = selectors[selectors.length - 1];

				for (int j = 0; j < doc.size(); j++) {
					// 如果当前元素与后代选择器的最后一个选择器不匹配，则继续循环
					if (!last.equalsIgnoreCase(doc.get(j).label) && !last.equals(doc.get(j).id)) {
						continue;
					}

					int index = selectors.length - 2;
					int level = doc.get(j).level;

					for (int k = j; k >= 0 && index >= 0; k--) {
						Element e = doc.get(k);
						String str = selectors[index];
						// 寻找父节点（level比当前节点小的第一个节点）
						if (e.level < level) {
							level = e.level;
							// 若父节点匹配当前选择器，则继续匹配；否则，向上寻找祖先节点
							if (str.equalsIgnoreCase(e.label) || str.equals(e.id)) {
								index--;
							}
						}
					}
					// 如果完全匹配后代选择器
					if (index < 0) {
						list.add(j + 1);
					}
				}
			}
			System.out.print(list.size());
			for (Integer line : list) {
				System.out.print(" " + line);
			}
			System.out.println();
		}
		scan.close();
	}
}

----------本文结束感谢您的阅读----------
坚持原创技术分享，您的支持将鼓励我继续创作！