201809-3 元素选择器
题目
思路
多级查询需要用到树形结构,详见代码。
AC代码如下
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
struct node{
vector<int> child;
string name,id;
int level;
}nd[105];
int n,m;
void get_text(int i){
string line;
getline(cin,line);
int s=0;
int t=line.find("..",s);
nd[i].level=1;
while(t!=string::npos){
nd[i].level++;
s=t+2;
t=line.find("..",s);
}
t=line.find(" ",s);
if(t!=string::npos){
nd[i].id=line.substr(t+1,line.size()-t-1);
nd[i].name=line.substr(s,t-s);
}
else nd[i].name=line.substr(s,line.size()-s);
transform(nd[i].name.begin(),nd[i].name.end(),nd[i].name.begin(),::tolower);
for(int j=i-1;j>=1;j--){
if(nd[j].level<nd[i].level){
nd[j].child.push_back(i);
break;
}
}
}
bool Matched(string str,int x){
if(str[0]=='#'&&str==nd[x].id) return true;
if(str==nd[x].name) return true;
return false;
}
void search(set<int> &f,string str,int x){
for(int i=0;i<nd[x].child.size();i++){
int u=nd[x].child[i];
if(Matched(str,u)) f.insert(u);
search(f,str,u);
}
}
void solve(){
string str;
getline(cin,str);
int s=0;
int t=str.find(" ",s);
set<int> f[80];
int i=0;
f[0].insert(0);
nd[0].child.push_back(1);
while(t!=string::npos){
string temp=str.substr(s,t-s);
if(temp[0]!='#')
transform(temp.begin(),temp.end(),temp.begin(),::tolower);
for(set<int>::iterator it=f[i].begin();it!=f[i].end();it++)
search(f[i+1],temp,*it);
i++;
s=t+1;
t=str.find(" ",s);
}
string temp=str.substr(s,str.size()-s);
if(temp[0]!='#')
transform(temp.begin(),temp.end(),temp.begin(),::tolower);
for(set<int>::iterator it=f[i].begin();it!=f[i].end();it++)
search(f[i+1],temp,*it);
i++;
cout<<f[i].size();
for(set<int>::iterator it=f[i].begin();it!=f[i].end();it++)
cout<<" "<<*it;
cout<<endl;
}
int main(){
cin>>n>>m;
cin.get();
for(int i=1;i<=n;i++) get_text(i);
for(int i=0;i<m;i++) solve();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)