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); //将每一个元素存入rj = 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元素的对应行数ivalue[i][t] = 1;//存储i行有元素tj = 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;
}