目录
展开
6 数字分段 TODO
这个二分法是用什么二分的?是前缀和?可是不是要分成很多段嘛?分成三段的画,怎么二分呢?
4 链表优化 40 TLE TODO
我直接用的 stl 里面的 vector,我想不到有什么优化的方法。找的过程如果用 hashtable,可以缩短到 O(1) 时间找到,但是在插入的时候,hashtable 就要花费 O(n) 的时间来修改,我现在这样是花费多个 O(logn),改 hash 难道不是得不偿失吗?
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int main(){
int n,m,lr,v;
vector<int>team(1,1);
scanf("%d",&n);
for(int i = 1;i<n;i++){
scanf("%d %d",&v,&lr);
team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);
}
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d",&v);
vector<int>::iterator res = find(team.begin( ), team.end( ), v);
if (res != team.end())
team.erase(res);
}
for(int i = 0;i<team.size();i++){
printf("%d",team[i]);
if(i != team.size()-1)printf(" ");
else printf("\n");
}
return 0;
}