about 2 years ago

前言

这场我竟然考出了个250...难道说这是个flag

A

题目大意:给定一个无向连通图,有个点,条边,每条边有一个边权,设表示的最短路。每个时刻每条边的长度都会加一,也就是说在第个时刻,每条边的长度为初始长度加上,现在要你求第个到第个时刻的之和对取模。
数据范围:
分析:考虑因为随着时间的增加,边数少的路径必然会更占优势,因此我们求出代表从经过条边的最短路径,然后对于每个点算出其贡献即可。算贡献的话维护一个凸包即可,时间复杂度

B

题目大意:给定个数,每次你可以选择两个数,将其中一个数变成,另一个数变成,请最大化所有数的平方和。
数据范围:
分析:一个贪心题,我们发现两个操作相当于移动二进制下的位置,显然将二进制下每一个都移到最前面去最优。时间复杂度,(然而我考场上写的奇怪的水过去了。。。)

C

题目大意:有一棵树,树上每个点初始都有一个数字,你可以随机一个点开始,每次等概率随机选择一个新点并且沿着树上的路径移动过去,最后反转这个新点的数字,也就是,注意只翻转这个新点的数字而不是路径上所有所有点的数字,且最开始的点不翻转,如果某个时刻,整棵树上的所有数字均为,那么结束,现在问你在结束之前期望总共要移动多少的距离。答案模,分数取逆元计算即可。
数据范围:
分析:

← TC SRM685 FoxAirline2 2016湖南省选经历 →
 
comments powered by Disqus