201809-3_元素选择器(90分)

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<string,string> Pair;   //不可放在using namespace std之前!!!

const int maxn = 2000 + 4;
int n, m;

string css[maxn];
Pair element[maxn];
vector<int>children[maxn];


//递归创建以第line行为根的子树
void build(int line, int cnt_point)
{
    for(int i = line + 1; i < n; i++){
        if(css[i][cnt_point] != '.') return;
        if(css[i][cnt_point+2] == '.') continue;
        children[line].push_back(i);
        if(i + 1 < n && css[i+1][cnt_point+2] == '.')
            build(i, cnt_point+2);
    }
}

void myTransform(string& s)
{
    transform(s.begin(), s.end(), s.begin(), ::tolower);
}

void getElement(int i)
{
    int p = 0, n = css[i].size();
    while(css[i][p] == '.')
        p++;
    int p1 = p;
    while(p < n && css[i][p] != ' ')
        p++;
    element[i].first = css[i].substr(p1, p - p1);
    myTransform(element[i].first);
    if(p != n){ //即有id
        element[i].second = css[i].substr(p + 1, n - p - 1);
    }
}

vector<int>ans;
//p as root     tags[cur]
void dfs(vector<string>&tags, int cur, int p)
{
    string tag = tags[cur];
    if(tag == element[p].first || tag == element[p].second){
        if(cur == tags.size() - 1){
            ans.push_back(p);
            for(int q = 0; q < children[p].size(); q++)
                dfs(tags, cur, children[p][q]);
        }else{
            for(int q = 0; q < children[p].size(); q++)
                dfs(tags, cur + 1, children[p][q]);
        }
    }else{
        for(int q = 0; q < children[p].size(); q++)
            dfs(tags, cur, children[p][q]);
    }
}

void solve(vector<string>&tags)
{
    ans.clear();
    dfs(tags, 0, 0);
    cout << ans.size();
    for(int i : ans)
        cout << ' ' << i + 1;
    cout << endl;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    while(cin >> n >> m){
        getchar();  //n m两个整数后的换行
        _for(i,0,n){
            getline(cin, css[i]);
            getElement(i);
        }
        _for(i,0,n)
            children[i].clear();
        build(0, 0);

        while(m--){
            string cmd;
            getline(cin, cmd);
            stringstream ss(cmd);
            vector<string>tags;
            while(ss >> cmd){
                if(cmd[0] != '#')
                    myTransform(cmd);
                tags.push_back(cmd);
            }
            solve(tags);
        }
    }
    return 0;
}
/*
11 5
html
..head
....title
..body
....h1
....p #subtitle
....dIv #main
......h2
......P #one
......div
........p #two
p
#subtitle
h3
div p
DIV DIV p

*/

  

本题难点有二:

1. 递归建树。(与子树二叉树篇的那道看图建树类似,后者是按以行为主导)

  a. 明确树的数据结构。树的数据结构可以用指针或者数组,这里直接采用数组css存储各结点值的信息,children存储每个结点的直接后代的的位置。其中,结点编号直接用行号。

  a. 明确递归函数当前的任务。这里是:递归创建以第line行为根的子树。因此,在书写递归函数时,只一心按照任务来就行。

    思路:

        从上到下遍历。

        当前结点的三种情况:

          1. 为line的直接子结点,直接push。如果该子节点还有子树,以该结点进入递归。

          2. 否则:

            1.为line的兄弟结点,return

            2.为line的间接后代,cotinue

 

2. 深度优先遍历之先序遍历。(原题所给的提示很重要,贪心策略:除了最后一级外,前面的部分都可以尽量匹配层级小的元素)

  明确递归函数当前的任务,进而确定传参。

  此处的任务是:当前的根是p, 下一个搜索对象是tags[cur]。

  思路:

    1.如果p是tags[cur],找到一解,加入答案集合。

      1.如果tags[cur]为最后一级的元素。则继续向下搜索,还是搜索tags[cur]

      2.否则,继续向下搜索,搜索的是tags[cur+1]

    2. 否则,继续向下。

 

最后需要注意,标签的大小写不敏感。

ps: ccf的输入似乎是每组数据运行一次程序,而不是一次程序输入多组...

上一篇:Mac os壁纸提取


下一篇:ccf考试201809_2之买菜