201809-3元素选择器

题目链接

题目描述：

样例输入：

11 5
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #none
......div
........p #two
p
#subtitle
h3
div p
div div p 

样例输出：

3 6 9 11
1 6
0
2 9 11
1 11

题目分析：

首先这道题是道模拟，题目很长，关键点有：

• 文档内容有标签，id属性以及缩进，标签大小写不敏感；id属性以#区分，大小写敏感；每两个..代表一级缩进。
• 所以用一个结构体数组来存储文档每行内容，结构体有标签lable，id属性id，以及缩进d。再者，因为每行文档内容包含空格，所以用getline读入一整行，然后再划分出lable，id，d各部分内容（此处需要用到字符串复制函数substr，同时，因为lable大小写不敏感，所以需要将lable全部转换为小写或大写，此处采用的是前者，全部转换为小写，需要用到的字符串转换小写函数为tolower）字符串函数讲解
• 选择器有三种类型，标签选择器，id选择器以及后代选择器。后代选择器A B表示满足选择器B的所有元素，且满足这些元素有祖先满足选择器A。
• 同样，因为每行选择器内容包含空格，所以用getline读入一整行，然后再根据空格划分各部分内容（此处需要用到字符串分隔函数strtok，需要注意的是strtok函数的参数是char*类型，而输入的是string类型，所以需要在应用strtok函数之前，语句加上strcpy(str,b.c_str());）同样，因为lable大小写不敏感，用字符串转换小写函数tolower将lable全部转换为小写。
• 标签选择器和id属性选择器都可以直接将选择器内容与文档内容逐一比较得出答案，难点在于后代选择器，根据后代选择器的定义，从选择器的末端出现，先判断找出满足末端的所有元素，然后进一步找出这些元素的祖先（祖先的判定条件为d<a[i].d)，一层一层往上递进。每一层只要有一个祖先满足即可。最后如果对于元素选择器的所有内容都满足，那么这个元素是符合题意的，ans++。（根据提示，采用贪心算法，找到一个匹配层级数最小的即可）
• 因为在寻找祖先的时候，是要一层一层往上的，所以需要更新现代元素，所以函数match采用的是&，对应存储单元地址）

代码：

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=110; 
struct word
{
	string lable;//标签 
	string id;//id 
	int d;//缩进 
}a[maxn];
vector<string> q;
vector<int> r;
int match(int &index,string s,int &d)//查找祖先 
{
	for(int i=index;i>0;i--)
	{
		if(a[i].d<d)//缩进小于 是祖先 
		{
			index=i;
			d=a[i].d;
			if(a[i].lable==s||a[i].id==s)//存在祖先元素满足S
			{
				//cout<<"i:*****"<<i<<endl;
				return 1;
			} 
		}
	}
	return 0;
} 
int main()
{
	int n,m;//行数和待查找选择器数 
	cin>>n>>m;	
	string s;//元素 
	string b;//选择器 
	cin.get();//读取换行符 
	for(int i=1;i<=n;i++)
	{
		getline(cin,s);
		//cout<<s<<endl;
		int cnt1=-1;//标签开始位置 
		int cnt2=-1;//属性开始位置 
		for(int j=0;j<s.size();j++)
		{	
			if(s[j]=='.')
			{
				a[i].d++;
			}
			else if(s[j]!='#'&&cnt1==-1)
			{
				cnt1=j;
			}
			else if(s[j]=='#')
			{
				cnt2=j;
			} 
		}
		a[i].d=a[i].d/2;//两个..为一层缩进 
		if(cnt2!=-1)//有id属性 
		{
			a[i].lable=s.substr(cnt1,cnt2-cnt1-1);
			for(int j=0;j<a[i].lable.size();j++)
			{
				a[i].lable[j]=tolower(a[i].lable[j]);
			}
			a[i].id=s.substr(cnt2);
		}
		else//没有id属性 
		{
			a[i].lable=s.substr(cnt1);
			for(int j=0;j<a[i].lable.size();j++)
			{
				a[i].lable[j]=tolower(a[i].lable[j]);
			}
			a[i].id="";
		}
		//cout<<a[i].lable<<" "<<a[i].id<<" "<<a[i].d<<endl;
	}
	
	//cin.get();
	for(int i=1;i<=m;i++)
	{
		q.clear();
		r.clear();
		getline(cin,b);
		char *pch;
		char str[128];
		strcpy(str,b.c_str());
		pch=strtok(str," ");
		while(pch!=NULL)
		{
			//cout<<pch<<endl;
			if(pch[0]!='#')
			{
				for(int j=0;j<strlen(pch);j++)
				{
					pch[j]=tolower(pch[j]);
				}
			}
			
			q.push_back(pch);
			pch=strtok(NULL," ");
		}
		int len=q.size();
		for(int j=n;j>0;j--)
		{
			if(a[j].lable==q[len-1] || a[j].id==q[len-1])//后代匹配 
			{
				int k;
				bool flag=true;
				int d=a[j].d;int in=j;
				for(k=len-2;k>=0;k--)
				{
					if(!match(in,q[k],d))
					{
						flag=false;
						break;
					}
				}
				if(flag)//符合 
				{
					r.push_back(j);
					//cout<<j<<endl;
				}
			}
		}
		int length=r.size();
		cout<<length<<" ";	
		for(int j=length-1;j>=0;j--)
		{
			if(j>0)
			{
				cout<<r[j]<<" ";
			}
			else
			{
				cout<<r[j];
			}	
		}
		cout<<endl;	
	}	
	return 0;
} 

/*

11 5
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #none
......div
........p #two
p
#subtitle
h3
div p
div div p 

3 6 9 11
1 6
0
2 9 11
1 11
*/