模拟4

image.png
image.png
image.png
image.png

思路：

看上去是html，其实挺好理解的。而且n的范围很小，直接考虑暴力就vans了。
先在node里面存储结构化的文档（标签 id和层数），这个过程最难的就是处理字符串，我用了sstream里面的一些方法。
然后查询，按空格把字符串分开，放在vector v里。然后将v中的所有标签（不以#开头）转换为小写。再从后往前遍历结构化文档，找到匹配最后一个查询的元素，然后寻找其祖先，如果祖先全部匹配，则该元素符合条件，加入到vector ans中。

最后输出答案。
代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<string.h>
#include<sstream>
using namespace std;
vector<string> zuxian;//保存祖先
vector<string> chaxun;//保存查询

struct Node {
    string table;
    string id;
    int level;
}e[105];
vector<int>ans;
void toLower(string &str) 
{
    for (int i = 0; i < str.size(); i++) 
    {
        if (isalpha(str[i])) str[i] = tolower(str[i]);
    }
}

void split(string &str, int x) 
{
    int flag = 0, s1 = 0, s2 = 0, sj = 0;
    string table, id;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '.')sj++;
        if (str[i] != '.'&&flag == 0) { flag = 1; s1 = i; }
        if (str[i] == ' '&&flag == 1) { s2 = i + 1; flag = 2; break; }
    }
    if (flag != 2) {
        table = str.substr(s1);
        toLower(table);
        e[x].table = table;
        e[x].level = sj / 2;
    }
    else if (flag == 2) {
        table = str.substr(s1, s2 - s1 - 1);
        toLower(table);
        id = str.substr(s2);
        e[x].table = table;
        e[x].id = id;
        e[x].level = sj / 2;
    }
}
bool ifok(int x) 
{
    int t = e[x].level, qq = chaxun.size() - 2;
    for (int j = x - 1; j >= 0; j--) 
    {
        if (e[j].level == t - 1) {
            if (chaxun[qq][0] != '#'&&chaxun[qq] == e[j].table) { qq--; }
            else if (chaxun[qq][0] == '#'&&chaxun[qq] == e[j].id) { qq--; }
            t = e[j].level;
            if (qq < 0)return 1;
        }
    }
    return 0;
}
int main() {
    int n, m;
    string line;
    cin >> n >> m;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        split(line, i);
    }
    for (int i = 0; i < m; i++) {
        getline(cin, line);
        stringstream ss; ss << line;
        string t;
        while (ss >> t) {
            if (t[0] != '#')toLower(t);
            chaxun.push_back(t);
        }
        int qsize = chaxun.size();
        for (int j = 0; j < n; j++) 
        {
            if (chaxun[qsize - 1][0] == '#'&&chaxun[qsize - 1] == e[j].id
                || chaxun[qsize - 1][0] != '#'&&chaxun[qsize - 1] == e[j].table) 
            {
                if (qsize == 1)ans.push_back(j + 1);
                else if (ifok(j))ans.push_back(j + 1);
            }
        }
        cout << ans.size();
        for (int i = 0; i < ans.size(); i++) 
        {
            cout << " " << ans[i];
        }
        cout << endl;
        zuxian.clear();
        ans.clear();
        chaxun.clear();
    }
    return 0;
}