CCF201809-3 元素选择器

解题思路：大模拟，与往年相比这道题难度有所下降，比较好懂，但要注意一个细节就是一个元素的祖先是紧接着其上的缩进小于等于其缩进的那些元素（连续的区域）中的缩进小于其缩进的元素（没有等于的元素，等于的元素只是起一种连接作用），具体看程序

提交后得100分的C++程序：

#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<ctype.h>
#include<string>

using namespace std;

const int N=105;

struct Node{
	string lable,id;
	int line,d;//行号和缩进 
}a[N];

vector<string>demand;
map<string,int>an,query;//an表示各个祖先含有的标签，id属性等，query表示要查询的 

string mystrlwr(string s)
{
	for(int i=0;i<s.length();i++)
	  s[i]=tolower(s[i]);
	return s;
}

//以空格进行分割 
void split(char *s,vector<string>&v)
{
	v.clear();
	char *p=strtok(s," ");
	while(p){
		v.push_back(p);
		p=strtok(NULL," "); 
	}
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++){
		string s;
		getline(cin,s);
		//统计缩进
		int cnt=0;
		for(int j=0;j<s.length()&&s[j]=='.';j++,cnt++);
		//获取标签
		int len=0,pos=-1;//如果有#，pos就记录#的下标 
		for(int j=cnt;j<s.length();j++,len++)
		  if(s[j]==' '){
		  	if(j+1<s.length()&&s[j+1]=='#')
		  	  pos=j+1;
		  	break;
		  }
		a[i].d=cnt;
		a[i].line=i; 
		a[i].lable=s.substr(cnt,len);
		//由于标签的匹配大小写不敏感，因此化为小写 
		a[i].lable=mystrlwr(a[i].lable);
		if(pos==-1)//如果没有id属性，就让id="" 
		  a[i].id="";
		else
		  a[i].id=s.substr(pos);
	}
	while(m--){
		char d[100];
		gets(d); 
		split(d,demand);
		vector<int>ans;
		if(demand.size()==1){
			string q=demand[0];
			if(q[0]!='#')//查询标签大小写不敏感
			  q=mystrlwr(q);//化为小写  
			//进行匹配
			for(int i=1;i<=n;i++)
			  if(q==a[i].lable||q==a[i].id)
			    ans.push_back(a[i].line); 
		}
		else{
			query.clear();
			for(int i=0;i<demand.size()-1;i++){
				//统计各种标签，id属性的个数 
				if(demand[i][0]!='#')//如果是标签就化成小写 
				  demand[i]=mystrlwr(demand[i]);
				query[demand[i]]++;
			} 			
                        string q=demand.back();
			if(q[0]!='#')//查询标签大小写不敏感
			  q=mystrlwr(q);//化为小写  
			//进行匹配
			for(int i=1;i<=n;i++)
			  if(q==a[i].lable||q==a[i].id){
			  	//获取a的祖先结点的标签和id属性
				  an.clear();
				  for(int j=i-1;j>0&&a[j].d<=a[i].d;j--){
                                        if(a[j].d==a[i].d)continue;//关键：细节
				  	an[a[j].lable]++;
				  	if(a[j].id!="")
				  	  an[a[j].id]++;
				  }
				//判断是否符合条件
				bool flag=true;
				for(map<string,int>::iterator it=query.begin();it!=query.end();it++)
				  if(an.count(it->first)==0||an[it->first]<it->second){
				  	flag=false;
				  	break;
				  }
				if(flag)
				  ans.push_back(a[i].line); 
			  }
		}
		printf("%d",ans.size());
		for(int i=0;i<ans.size();i++)
		  printf(" %d",ans[i]);
		printf("\n");
	}
	return 0;
}