摘要:这两天考试的小结

07212020

A

题意

一棵有权单向树,有一些节点可以直接跳到深度小于等于它的点上,费用为深度的差值*k,求每个点到根的最短距离.

分析

考的时候读错题,1个小时想了2个解法都因为我以为是无向边被自己hack…

然后打了一个$O(n^2)$的连边拿了40.

单向的就很水了,bfs遍历,根据深度和距离记录一个最优值所在的点,下面的可以上跳的点就跳到最优的点上,然后自己也就成为了下一个最优点,每层之间跳不花费代价所以要转移一下.

遍历的时候用当前距离加上边权向下更新下面的距离就可以了.

B

题意

给一些数轴上的点,每个点有速度,可以拿走k个点,求这些点相碰的最短时间.

分析

二分出相碰的时间暴力算一下有多少个要相遇和k比对一下就90pts了.

因为要相遇的就拿去一个是最优的.

然后考虑优化一下暴力的过程,先按原来每个点的位置排序得到,然后算出经过一段时间后到达的位置,发现相遇就是出现一对逆序对.

因为值域是实数所以离散一下放进树状数组就能做了.

07222020

A

题意

给一个长度为2n的实数序列,q组询问给出长度为偶数的区间,在区间中两两选择一个取上整一个取下整,求修改后的区间和与原先的区间和最小的差值.

分析

考场上发现了一个性质,两个都是小数的化交换取上下整没有影响,于是打了个$O(nq)$的拿了50分,有个优化最后20分钟没调出来所以t了.

然后是正解,先考虑全部取上整算出一个差值,然后取下整来向下减,取上整改成取下整只用减个1.

然后考虑取多少个下整,最多就只能取区间长度的一半个,减去后如果小于0的说明没法全取,否则全部取最优.

如果没法全取,减去区间中整数的数量得到把去上整的上界摆满后有几个必须取下整,减出来小于0的话说明上整的排满的话取下整的任意拿都是最优的,因为再多放只会把数字减得更低导致差值变大,否则考虑与整数两边交换一下,取上下整的小数平分,可以发现最后答案是小数位或1-小数位.