思路
其实题目很简单,就是很麻烦...
要构建一个树形结构,使用结构体对每个节点进行存储。只有直系的父辈才算祖先(伯父不算祖先),在后代选择器中。
node:
struct node {
vector<int> anc;//祖先
string lable;
string id;
int level;//第多少层孩子...
bool operator<(const node&p)const {
return level < p.level;
}
}node[105];
使用vector数组存储祖先在node数组中的索引,level表示当前节点是树的多少层(从0开始)。
使用一个ance数组记录当前的直系父辈(只需要读取每个节点的时候对当前层的父辈进行更新即可),然后寻找父辈时在ance中寻找。
由于label大小写不敏感,在存储和查找时,一律将大写变成小写。
在进行后代选择器操作的时候,将操作中的操作数存入结构体数组 ff 中(该结构体存储,以及type区分是label还是id),然后在node数组里寻找最后代匹配的节点。在匹配上的节点中,将所有父辈压入栈,从子辈向父辈进行检索。
代码
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
string lable[105];
string id[105];
int ance[40];
struct node {
vector<int> anc;//祖先
string lable;
string id;
int level;//第多少层孩子...
bool operator<(const node&p)const {
return level < p.level;
}
}node[105];
struct str{
string s;
int type;
};
string trans(string s)
{
int n = s.length();
for (int i = 0; i < n; i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] += 32;
}
return s;
}
int main()
{
int m, n;
cin >> m >> n;
string s;
cin.ignore();
memset(ance, -1, sizeof ance);
for (int i = 0; i < m; i++)
{
getline(cin, s);
int num = 0;
if (s.find('.') != string::npos)
num = s.find_last_of('.') - s.find_first_of('.') + 1;
node[i].level = num / 2;
ance[node[i].level] = i;
if (s.find('#') != string::npos)//存在id
{
node[i].id = s.substr(s.find('#') + 1);
node[i].lable = trans(s.substr(num, s.find('#') - num - 1));
//cout << node[i].id << " " << node[i].lable << endl;
}
else
node[i].lable = trans(s.substr(num));
//cout << node[i].lable << endl;
for (int j = 0; j < node[i].level; j++)//寻找祖先
node[i].anc.push_back(ance[j]);
}
while (n--)
{
string op;
getline(cin, op);
if (op.find('#') == string::npos && op.find(' ') == string::npos)//标签选择器
{
op = trans(op);
int num = 0;
vector<int> pos;
for (int j = 0; j < m; j++)
{
if (op == node[j].lable)
{
pos.push_back(j);
num++;
}
}
cout << num << " ";
for (vector<int>::iterator it = pos.begin(); it != pos.end(); it++)
cout << *it + 1 << " ";
cout << endl;
}
else if (op.find(' ') == string::npos)//id选择器
{
op = op.substr(1);
int num = 0;
vector<int> pos;
for (int j = 0; j < m; j++)
{
if (op == node[j].id)
{
pos.push_back(j);
num++;
}
}
cout << num << " ";
for (vector<int>::iterator it = pos.begin(); it != pos.end(); it++)
cout << *it + 1<< " ";
cout << endl;
}
else
{
int num = 0;
vector<int> pos;
int f[40];
struct str ff[40];
int k = 0;
int now = 0;
while (op.find(' ',now) != string::npos) {
int p = op.find(' ', now);
now = p + 1;
f[k++] = p;
}
int begin = 0;
int kk = 0;
for (int j = 0; j < k; j++)
{
string sss = op.substr(begin, f[j] - begin);
if (sss.find('#') != string::npos) {
ff[kk].type = 2;
ff[kk].s = sss.substr(1);
}
else {
ff[kk].type = 1;
ff[kk].s = trans(sss);
}
kk++;
begin = f[j] + 1;
}
string sss = op.substr(begin);
if (sss.find('#') != string::npos) {
ff[kk].type = 2;
ff[kk].s = sss.substr(1);
}
else {
ff[kk].type = 1;
ff[kk].s = trans(sss);
}
int u = kk;
for (int j = 0; j < m; j++)
{
int vv = u;
if ((ff[vv].type = 1 && ff[vv].s == node[j].lable) || (ff[vv].type = 2 && ff[vv].s == node[j].id))
{
vv--;
stack<int> ac;
for (vector<int>::iterator it = node[j].anc.begin(); it!= node[j].anc.end(); it++)
ac.push(*it);
bool ok = false;
while (!ac.empty())
{
string ss;
if (ff[vv].type == 1) ss = node[ac.top()].lable;
else ss = node[ac.top()].id;
ac.pop();
if (ss == ff[vv].s) vv--;
if (vv == -1)
{
ok = true;
break;
}
}
if (ok)
{
num++;
pos.push_back(j);
}
}
}
cout << num << " ";
for (vector<int>::iterator it = pos.begin(); it != pos.end(); it++)
cout << *it + 1<< " ";
cout << endl;
}
}
std::system("Pause");
}
/*
11 5
htMl
..head
....title
..body
....h1
....p #subtitle
....div #main
......H2
......p #none
......div
........p #two
p
#subtitle
h3
div p
#main div p
*/
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)