快速建站网站,佛山营销网站,wordpress邮箱设置,吉林系统建站怎么用照例先贴题面#xff08;汪汪汪#xff09; 2500: 幸福的道路 Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 368 Solved: 145[Submit][Status][Discuss]Description 小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一… 照例先贴题面汪汪汪 2500: 幸福的道路 Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 368 Solved: 145[Submit][Status][Discuss] Description 小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光. 他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图. 他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条). 他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)? 现在他们把这个艰巨的任务交给你了! Input 第一行包含两个整数N, M(M10^9). 第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di. Output 最长的连续锻炼天数 Sample Input 3 2 1 1 1 3 Sample Output 3 数据范围 50%的数据N1000 80%的数据N100 000 100%的数据N1000 000 对于这道题来说我们可以考虑预处理出每个结点的最长路径长然后乱搞 对于预处理我在考场上写了个对于每个结点DFS一遍求最长然后$std::set$维护最大最小值总时间复杂度瓶颈为预处理$O(n^2)$ 实际上我们可以先求这个树的直径结点然后从分别从两个直径结点进行DFS并取最大值来预处理出最长路径长。直径为树中最长的一条路径。这一过程需要固定的4遍DFS所以时间复杂度$O(n)$ 考场上鬼使神差地脑抽认为求直径会有反例 然后就是求最长连续区间的问题我的策略是建立左右两个哨兵采用一直让右哨兵前进并更新最大值直至最大最小值超过限制条件超限之后采用不断删除左哨兵的值并前进直至符合条件的贪心策略。因为$std::set$的插入与查询是$O(logn)$每个点肯定要插入/删除一次所以贪心过程时间复杂度$O(nlogn)$总时间复杂度$O(nlogn)$ 这里其实还可以使用单调队列但是因为单调队列要固定区间长度所以只能采取二分长度策略总时间复杂度也是$O(nlogn)$。 然后袋马时间 GitHub 1 #include set2 #include cstdio3 #include algorithm4 5 const int MAXE2000010;6 const int MAXV1000010;7 8 struct Edge{9 int from;
10 int to;
11 int dis;
12 Edge* next;
13 };
14 Edge E[MAXE];
15 Edge* head[MAXV];
16 Edge* topE;
17
18 int n;
19 int m;
20 int lg1;
21 int lg2;
22 int dis[MAXV];
23
24 void Initialize();
25 std::pairint,int DFS(int,int,int);
26 void DFSA(int,int,int);
27 void Insert(int,int,int);
28 int Sweep();
29
30 int main(){
31 Initialize();
32 lg1DFS(1,0,0).second;
33 lg2DFS(lg1,0,0).second;
34 DFSA(lg1,0,0);
35 DFSA(lg2,0,0);
36 printf(%d\n,Sweep());
37 // printf(%d %d\n,lg1,lg2);
38 return 0;
39 }
40
41 std::pairint,int DFS(int root,int prt,int dis){
42 std::pairint,int ans(dis,root);
43 for(Edge* ihead[root];i!NULL;ii-next){
44 if(i-toprt)
45 continue;
46 ansstd::max(ans,DFS(i-to,root,disi-dis));
47 }
48 return ans;
49 }
50
51 void DFSA(int root,int prt,int dis){
52 ::dis[root]std::max(::dis[root],dis);
53 for(Edge* ihead[root];i!NULL;ii-next){
54 if(i-toprt)
55 continue;
56 DFSA(i-to,root,disi-dis);
57 }
58 }
59
60 int Sweep(){
61 int l1,r1,ans0;
62 // std::priority_queueint,std::vectorint,std::lessint qmax;
63 // std::priority_queueint,std::vectorint,std::greaterint qmin;
64 std::multisetint s;
65 while(rn){
66 // printf(%d\n,r);
67 s.insert(dis[r]);
68 while(*(--s.end())-*s.begin()m){
69 s.erase(s.find(dis[l]));
70 l;
71 }
72 ansstd::max(ans,int(s.size()));
73 r;
74 }
75 return ans;
76 }
77
78 void Initialize(){
79 int a,b;
80 scanf(%d%d,n,m);
81 for(int i2;in;i){
82 scanf(%d%d,a,b);
83 Insert(a,i,b);
84 Insert(i,a,b);
85 }
86 }
87
88 inline void Insert(int from,int to,int dis){
89 top-toto;
90 top-disdis;
91 top-fromfrom;
92 top-nexthead[from];
93 head[from]top;
94 top;
95 } Backup 以及图包时间 转载于:https://www.cnblogs.com/rvalue/p/7191518.html
