Boruvka

2020-牛客多校-5

 2020.07.27 22:03  2023.09.01 18:14  ACM  构造  LCM  LIS  Boruvka  异或MST  生成函数 󰈭 1760字

坑 I 数学构造题想这类题的时候不能太过于从有限的角度去考虑无穷的角度，如果用有限的面积拓展到无限的面积，那么最多大概也就1/2, 5/9的情况，这不是最优的。应该用无限的观点去尝试构造，考虑一个金块最多可以贡献出4个信标，一个炼丹炉最多也可以贡献4个信标，并且认为这一个金块和一个炼丹炉都能在平均的意义下满足4个信标的放置条件，那么最好的情况就是4/6 = 2/3。 ...