CCF CSP——元素选择器（201809-3）

因为一个字母浪费了一个多小时的时间。。。。。

思路参考
https://blog.csdn.net/wingrez/article/details/88589753

思路总结
1.用stringstream将各行格式文档的id、标签分开存储；
2.用stringstream将待查询选择器的各个部分，分别存储在vector容器中
3.以vector容器的最后一个元素作为关键字进行初步筛选，选择满足条件的层号
4.从vector容器的倒数第二个元素向前，依次作为关键字进行查询。若全部满足则保留层号；否则将层号置为0。
5.按照要求输出即可

我的代码

#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

const int MAXN = 100 + 10;

struct Line{//记录格式文档每行的信息
    int rank;//级别
    int level;//层数
    string label;//标签
    string id;//id
};

Line line[MAXN];

int main(){
    int n,m;
    cin>>n>>m;//输入格式文档的行数 & 查询的行数
    getchar();//吸收换行符
    string html,css,str;
    for(int i=1;i<=n;i++){
        getline(cin,html);//输入每行的格式文档
        line[i].level = i;//层数编号从1开始
        stringstream ss(html);//将每行的格式文档作为输入流
        ss>>str;
        int cot;
        for(cot=0;cot<str.size()&&str[cot]=='.';cot++);
        //cot指向第一个不等于'.'的值，值为'.'的个数
        line[i].rank = cot / 2;
        //标签不区分大小写，故先将其都转换成大写字母
        transform(str.begin(),str.end(),str.begin(),::toupper);
        line[i].label = str.substr(cot);//获取标签并赋值
        while(ss>>str){//若输入流中仍有数据
            if(str[0]=='#'){//且数据以'#'开头
                line[i].id = str;//将其赋值给该行对应的id值
            }
        }
    }

    for(int i=1;i<=m;i++){
        getline(cin,css);//输入待查询的选择器
        stringstream ss(css);//将其作为输入流
        vector<string> order;//用于记录选择器中的标签、id
        while(ss>>str){
            if(str[0]!='#'){//若为标签，将其统一转换为大写；id不做处理
                transform(str.begin(),str.end(),str.begin(),::toupper);
            }
            order.push_back(str);//压入到order中
        }
        int answer[MAXN],total = 0,real;
        //answer[]用于记录满足条件的各行行号
        //total记录所有拥有该标签或id的总行数
        //real记录满足选择器中所有条件的总行数
        vector<string>::reverse_iterator it = order.rbegin();
        //先以最后一个标签或id作为关键字进行筛选
        for(int j=1;j<=n;j++){
            //若有满足条件的标签或id，则记录下该行的行号
            if(line[j].label == *it || line[j].id == *it){
                answer[total] = j;//line[j].level=j
                total++;
            }
        }
        real = total;
        for(int j = 0;j<total;j++){
            it = order.rbegin() + 1;
            //若选择器有个两个及以上筛选条件，则以倒数第二个标签或id作为关键字
            int current = line[answer[j]].rank;//记录初选的层号
            for(int k=answer[j]-1;k>0&&it!=order.rend();k--){
            //从其上一层开始，逐层检查
                if(current>line[k].rank && (*it==line[k].label || *it==line[k].id)){
                //若为其祖先级别（这里只能为父亲级别），且标签或id有一项满足
                    it++;//将前一个筛选条件作为关键字
                    current = line[k].rank;//记录当前的层号
                }
            }
            if(it!=order.rend()){//若各层遍历完，但条件并没有满足
                real--;//实际的层数减一
                answer[j] = 0;//答案数组该层记为0（层号从1开始）
            }
        }
        cout<<real;
        for(int j=0;j<total;j++){
            if(answer[j]){//输出不为0的层号
                cout<<" "<<answer[j];
            }
        }
        cout<<endl;
    }
    return 0;
}