【游族杯】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;
}