UOJ Logo root的博客

博客

【讨论帖】剑锋OI#Ⅱ期#秩序团#模拟赛#20180110#005

2018-01-14 13:39:31 By root

楼下……

评论

root
A题:二分答案+判断
root
@yangxiao 请做B题题解
lhy
c: 为了满足题目所给条件 即连接两个点之间的点都要小于它们 需要在bob的树里面截一段 使得对于这一段中每一个点 子节点的值大于父节点 枚举根节点i,联通的向下延伸,如果满足子节点>i就可以继续 否则不取 对于每个枚举的i取树节点的最大值 :)
yangxiao
->B题题解 首先读题,由题中所给的介绍可以看出这些城市及其道路组成了一棵树,且边是有向的,所以存边时要记录a->b边的方向:change=true或false,即到时后由a到b是否要变边。 用f[i]记录i为首都时要变的边数,现在观察之间有边的两点(a,b)之间f[a]与f[b]的关系。假设f[a]已知,边由a->b,那么对于f[b]来说需要做的只是改变这一条边的方向便可以满足条件,而对于a来说这一条边是未改变的,所以f[b]=f[a]+1;反之当边为a<-b,对于b来讲是不需要改变的,但对于a,这条边是改变过的,所以f[b]=f[a]-1。 得出以上规律后,只需知道一个f[i],可以用一个O(n)的搜索快速处理出,便可以扩展到全部结点。之后每个点访问一遍,复杂度同样是O(n),所以总的复杂度也是O(n)级别,只是常数有点大,搜索时传参次数较多,所以不是很快。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。