2021.01.20【NOIP提高B组】总结

TOP

• • • • T1 天天爱跑步
      • T2 换教室
      • T3 蚯蚓
      • 完成情况

这是一个好东西->作者主页

T1 天天爱跑步

题目大意：给你一棵树，以及几对点对，让你从起点到终点， 1 1 1秒跑完1 1 1 1条边。每个点有监察员，他们会在恰好 w i w_{i} wi​的时间点观察。求每个监察员会看到多少个人。

思路： L C A LCA LCA+桶+差分

T2 换教室

题目大意：牛牛要上课，他可以考虑换课。求路程期望值最小。

思路：

1. 打表 76 76 76分
2. 设 f i , j , 0 / 1 f_{i,j,0/1} fi,j,0/1​表示到了第 i i i节课，换了 j j j节课，现在换还是不换，期望值最小值， 100 100 100分

T3 蚯蚓

题目大意：有一些蚯蚓，你会每次把最大的砍成两半，而其他的蚯蚓会增加一些长度。求每一次砍时被砍蚯蚓之前的长度，以及 m m m时间后所有蚯蚓的长度。

思路：

1. 用一个堆维护，暴力更新每条蚯蚓的长度， 45 45 45~ 55 55 55分
2. 首先将原数组排序，然后用三个优先队列维护，第二个放砍掉的大的部分，第三个放砍掉的小的部分，每次取三个队头中最大的，将其加上 ( i − 1 ) ∗ q (i-1)*q (i−1)∗q，放的时候减去 i ∗ q i*q i∗q就行了。注意初始化为超小的值。 100 100 100分

完成情况

• T1
• T2
• T3