Beta Round #2 (新疆省队互测Week1-Day2)

OI - Official

From tangjz Kinger Tangent


小时

尚未报名

无尽的毁灭 2/26 From
大地的复苏 9/36 From
命运的轮回 5/19 From

新疆省队互测 Week1 Day2

本次由tangjz出题,OI赛制,三道题目

难度比上一次略难,神犇还是无压力……

 

Kinger Tangent: 这场比赛无难度 涉及面广求不黑

tangjz: 还是祝各位AK各类比赛

 

flag:

第二题:数据已更正,不存在a[i] = i。

第三题:数据范围已更正。

欢迎您在赛后提供更加强有力的数据,为保障选手利益,不会重新计算Rating。

 

简要题解:

第一题:暴搜最高60分;100分算法使用O(NlogN)时间复杂度的算法求Voronoi图,并定位每个Vor顶点。

第二题:这是一棵内向树,随便找一条环上的有向边(u,v),先直接断掉这条边,以u为根在反图上进行一次树形dp;然后强制令u限制v,再以u为根在反图上进行一次树形dp,dp过程中不需要考虑v是否被限制,而u必须不被选择。

第三题:简单的数位统计。