精准扶贫网站建设的意义,网站设计小技巧,广东衍发建设管理有限公司公司网站,wordpress导航兰问题描述 解题思路
根据题意可以知道在查询中可以分为两种情况 第一种是查询一个标签选择器或者id选择器#xff08;可以称为一级查询#xff09; 第二种就是存在大于两级的查询#xff08;可以称为多级查询#xff09;
显然第一种查询需要存储每一种元素在内容中所有出现…问题描述 解题思路
根据题意可以知道在查询中可以分为两种情况 第一种是查询一个标签选择器或者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_mapusing namespace std;
const int N 110;vector string text;
int n, m;
int p[N];
unordered_map string, vector int val; //存储每一个元素对应的行号
vectorvector string query; //存储所有的查询
unordered_map int, unordered_mapstring, 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;
}
