题目原文
题目背景
题目描述
输入输出
样例解释
解题思路
建立结构体存储每个元素的标签、id、层级和父元素指针。其中父元素指针用于在后代选择器中判断父元素是否符合要求。
首先将元素文档中的信息读入，并根据前面‘.’的数量判断该元素的层级，点的数量除以2即该元素层级（其实可以不除，因为只用到了层级的大小关系），再根据层级以及元素栈找到元素的父元素。
之后读入一行并根据空格分割，将分割出的属性放在sel数组中；如果只有一个属性那么判断完那一个属性后就完毕；如果有多个属性，判断最后一个属性是否与当前元素属性一致，如果一致就继续去判断父节点的属性，直到没有父节点或者属性都匹配完，如果属性都匹配完那么这个元素就是要找的元素。
需要注意的是，在id属性中是需要区分大小写的，而在标签属性中不需要区分大小写，所以在判断时候应该分开处理。
因为在判断的时候选择器中一样带有#标志，所以可以将id属性的#算入id属性中。
实现代码
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int maxn = 101;
struct node {
int level; //层级
string name; //标签属性
string id; //id属性
node* parent; //父标签
void val(string id, string lab, int level) {
this->name = id;
this->id = lab;
this->level = level;
this->parent = NULL;
}
} ele[maxn];
void divide(const string& line, vector<string>& sel)
{//将读入的一行line分割为每段元素，放入sel中
sel.clear();
string token="";
for (int i = 0; i < line.size(); i++)
{
if (line[i] == ' ')
{
sel.push_back(token);
token="";
}
else token += line[i];
}
sel.push_back(token);
}
bool check(node* t, const string& s)
{
if (s[0] == '#') return s == t->id;
if (s.size() != t->name.size()) return false;
for (int i = 0; i < s.size(); i++)
{
if (tolower(s[i]) != tolower(t->name[i])) return false;
}
return true;
}
int main()
{
int n, m;
cin >> n >> m;
getchar();
stack<node*> parents;//使用栈结构记录元素，用于计算层级以及父元素
//读入元素文档
for (int i = 1; i <= n; i++)
{
string line;
getline(cin, line);
int level = 0;
while (line[level] == '.') level++;//统计前面‘.’的数量计算层级
string name = "", id = "";
int k;
for (k = level; k < line.size(); k++)
{
if (line[k] == ' ')//空格以前为标签属性
break;
name += line[k];
}
for (k; k < line.size(); k++) {
if (line[k] == '#')//取除#以前内容（下次循环从#开始，井号还在）
break;
}
for (k; k < line.size(); k++) {
id += line[k];
}
level /= 2;//每层两个‘.’（不除也无所谓）
ele[i].val(name, id, level);
if (!parents.empty())//找父元素
{
node* p = parents.top();
while (p->level >= level)//将层级高的出栈
{
parents.pop();
p = parents.top();
}//找到第一个层级更低的，即为其父元素
ele[i].parent = p;
}
parents.push(&ele[i]);
}
//读入选择器
vector<int> ans;
vector<string> sel;
while (m--)
{
string line;
getline(cin, line);
divide(line, sel);//将一行中的选择器分割
ans.clear();
for (int i = 1; i <= n; i++)
{
//cout << ii << ele[ii].name << ele[ii].id << endl;
int cnt = sel.size() - 1;//从选择器最后一个属性开始比较
if (check(&ele[i], sel[cnt]))//因为id属性带#，而标签属性不带#，可以直接分别比较sel[cnt]==ele[i].name || sel[cnt] == ele[i].id
{//如果选择器中最后一个属性符合，依次比较父元素和前面的属性
node* p = ele[i].parent;
cnt--;
while (p!=NULL && cnt >= 0)
{
if (check(p, sel[cnt]))//sel[cnt] == p->name || sel[cnt] == p->id
cnt--;//如果仍然符合继续比较前一个属性
p = p->parent;
}
if (cnt == -1) //cnt=-1表示比较完了所有属性（sel数组中从0~size-1存的）
ans.push_back(i);//放入答案中
}
}
cout<< ans.size();
for (int i = 0; i < ans.size(); i++)
cout<<" "<<ans[i];
cout << endl;
}
return 0;
}
/*
11 100
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #none
......div
........p #two
p
#subtitle
h3
div p
div p p
*/
小结
写题时需要先通读题目，理解大概的解题思路，确定结构体中的变量，不然在后面会发现很多变量没有定义，导致来回改动代码；
另外在题目很长的时候需要注意很多题目中的细节，比如后代选择器可以有多个属性而不是两个，id属性大小写敏感而标签属性大小写不敏感。
