201809-3 CCF 元素选择器 满分题解（超详细注释代码） + 解题思路（超详细）

问题描述

解题思路

根据题意可以知道在查询中可以分为两种情况
第一种是查询一个标签选择器或者id选择器（可以称为一级查询）
第二种就是存在大于两级的查询（可以称为多级查询）

显然第一种查询需要存储每一种元素在内容中所有出现的行，对应的数据结构可以是unordered_map< string, vector < int > >

对于第二种多级查询，例如查询所有满足 A B C D的位置
首先将所有D出现的位置找出来，也就是上面那个map中存的vector数组
遍历这个数组，相当于遍历每一条以D结尾的路径
对于每一条以D结尾的路径，从D开始回溯，每次回溯到当前行的父亲行（这里需要一个p数组记录父亲行的位置），并且如果路径中的该行中有元素与查询的最后一个元素匹配（这个匹配需要map来记录每一行有哪些元素，对应的数据结构可以是unordered_map < int, unordered_map < string, int > >），则查询元素弹出
当以D结尾的路径遍历完时，并且查询中的元素也为空，则说明这条路径能够满足查询，则将这个答案保存下来

至于p数组中的值，就是利用一个数组记录每一行之前最近的起始行就可以得到，具体可见代码，不难理解
至于两个map中的值，主要是利用双指针还有substr等函数，具体可见代码，不难理解

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
const int N = 110;

vector <string> text;
int n, m;
int p[N];
unordered_map <string, vector <int>> val; //存储每一个元素对应的行号
vector<vector <string>> query; //存储所有的查询
unordered_map <int, unordered_map<string, int>> value; //存储每一行有哪些元素，相当于一个可哈希的二维数组

//将每一行的父亲行存入p数组，并且去除每一行前面的.
void workparent()
{
    //先将每一行开头的点数存储在p数组中，并去除.
    for (int i = 1; i <= n; i ++)
    {
        string str = text[i];
        int j = 0;
        while (j < str.size() && str[j] == '.') j ++; //j停在第一个不是.的位置
        text[i] = str.substr(j); //去除前面的点
        p[i] = j; //保存第i行内容前面.的个数
    }
    
    //从头遍历p数组，更新p数组，将p数组存储第i行的父亲行，用t数组存储最近的有p[i] - 2个.的位置
    int t[N];
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= n; i ++)
    {
        t[p[i]] = i; //更新最近的一个有p[i]个点的位置
        if (p[i] == 0) continue;
        int f = t[p[i] - 2]; //父亲节点是最近的有p[i] - 2个点的位置
        p[i] = f; //存储第i行元素的父节点行数
    }
}
 
//将每一行询问根据空格分隔存储
void workquery()
{
    for (int i = n + 1; i <= n + m; i ++) //读入的询问行
    {
        string str = text[i];
        vector <string> r;
        for (int j = 0; j < str.size(); j ++)
        {
            int k = j;
            string t;
            while (k < str.size() && str[k] != ' ') t += str[k ++]; //k越界或k是空格
            if (t[0] != '#') transform(t.begin(), t.end(), t.begin(), ::tolower); //可以转包含数字的串!
            r.push_back(t); //将每一个元素存入r
            j = k;
        }
        query.push_back(r);
    }
}

//存储每一行元素的对应行数
//存储每一行对应有哪些元素
void workpos()
{
    for (int i = 1; i <= n; i ++)
    {
        string str = text[i];
        for (int j = 0; j < str.size(); j ++)
        {
            int k = j;
            string t;
            while (k < str.size() && str[k] != ' ') t += str[k ++]; //k越界或k是空格
            if (t[0] != '#') transform(t.begin(), t.end(), t.begin(), ::tolower);
            val[t].push_back(i); //存储t元素的对应行数i
            value[i][t] = 1;//存储i行有元素t
            j = k;
        }
    }
}

int main()
{
    cin >> n >> m;

    getchar();
    text.push_back("*"); //使下标从1开始
    for (int i = 0; i < n + m; i ++) //读入所有内容包括询问
    {
        string str;
        getline(cin, str);
        text.push_back(str); //1 ~n, n + 1 ~n + m
    }

    workparent(); //找到所有行的父亲行
    workpos(); //存储每一行元素对应的行数
    workquery(); //将询问处理并分隔

    //进行询问的查询
    for (int i = 0; i < query.size(); i ++)
    {
        vector <string> q = query[i];
        vector <int> r = val[q.back()]; //r包含最后一个元素出现的所有位置
        if (q.size() == 1) //一代
        {
            cout << r.size(); //是0的话就不会输出!
            for (auto x : r) cout << " " << x;
        }
        else //多代
        {
            vector <int> res;
            for (auto pathend : r) //遍历每一条路
            {
                vector <string> flag = q; //标记数组存储的是一行查询的元素，如果路径上出现数组中的末尾元素，就将末尾元素弹出
                for (int row = pathend; row != 0 && !flag.empty(); row = p[row]) //结束条件，标记数组空了或者路走到了尽头
                {
                    if (value[row][flag.back()]) flag.pop_back();
                }
                if (flag.empty()) res.push_back(pathend); //表明以pathend结尾的路径上能满足该行询问，将这个元素位置加入答案中
            }
            cout << res.size();
            for (auto x : res) cout << " " << x;
        }
        cout << endl;
    }
    return 0;
}