Questions

ques.md

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; }

发表评论