欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【游族杯】2018华师大邀请赛C面向对象程序设计

程序员文章站 2022-05-27 16:25:15
...

题目:https://acm.ecnu.edu.cn/contest/73/problem/C/
思路:首先可以确定暴力肯定不行
当时想的是纵向不行可以转换角度横向思考。对于每一个函数,我们可以顺次找出可以调用它的类,对于这些类,我们可以建一棵树,然后对于一棵树,就可以考虑到dfs。当时想到这里再继续想做法的时候,觉得虽然知道可以调用某个函数的类,但是对于一个未知的u,要求解的话每次都要跑一下dfs,然后gg。当时考虑最暴力的方法是map直接离线处理。然后并没想到把这两种方法结合起来,用栈保存每个函数所属的类,离线处理得到所有答案。唉。。还是太菜。。就是get不到点上。。
官方题解:离线处理——对每种函数维护一个栈,栈中记录类名。DFS的时候更新栈(进入时压入,退出时弹出)。对于某个节点上所有查询,答案就是对应函数的栈顶元素。
代码过程:看了题解之后,开开心心去写了。。
1、刚开始是对于每个节点,存了(节点u,所有a)的答案,dfs的过程每进一个节点要走一个10^6的循环。。和暴力有什么差。。简直是脑子瓦特了
2、改进之后,用一维数组ans存储答案,map记录了(u,r)的位置,然后wa了。。检查的时候发现如果有重复的对出现,map的值会被覆盖。。在小伙伴的提示下,用vector存了r和pos。over。

写这么多只是为了记录一下心酸的过程。有些时候问题真的不是出现在思路,而是在实现。之前一道dp也是这样,换一种写法会发现总有考虑不到的问题。以后还是要多想一想,要更细致一些。

代码

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef pair<int,int>pa;
vector<stack<int> >s;
vector<vector<int> >edge;
vector<vector<int> >num;
vector<vector<pa> >record;
vector<int>ans;
int maxT=0;

void dfs(int x){
    for(int i=0;i<num[x].size();i++){
        int t=num[x][i];
        s[t].push(x);
    }
    for(int i=0;i<record[x].size();i++){
        int t=record[x][i].first;
        if(t<=maxT){
            if(s[t].size())
                ans[record[x][i].second]=s[t].top();
        }
    }
    for(int i=0;i<edge[x].size();i++){
        int v=edge[x][i];
        dfs(v);
        for(int j=0;j<num[v].size();j++){
            int t=num[v][j];
            s[t].pop();
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    edge.resize(n+1);
    num.resize(n+1);
    int x;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        edge[x].push_back(i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        int t;
        for(int j=0;j<x;j++){
            scanf("%d",&t);
            maxT=max(t,maxT);
            num[i].push_back(t);
        }
    }
    s.resize(maxT+1);
    record.resize(n+1);
    int q,u,r;
    scanf("%d",&q);
    ans.resize(q);
    for(int i=0;i<q;i++){
        scanf("%d%d",&u,&r);
        record[u].push_back(pa(r,i));
    }
    dfs(1);
    for(int i=0;i<q;i++){
        if(!ans[i])
            printf("-1\n");
        else
            printf("%d\n",ans[i]);
    }
    return 0;
}
相关标签: dfs 离线处理