ZJOI 2012 Round 1 Solution

Problem 1: Ai,Ai+1可以由Ai/2,Ai/2+1推出。递归即可。

Problem 2:我们将所有相邻的3角形间连一条边,容易看出答案是最长链长度+1。

Problem 3:

我们反过来计算所有内部为空的矩形个数。

我们一行行扫描,计算底边在当前行的空矩形个数。

令hc为第c列往上,在碰到障碍或底边之前,有几个空格子。

那么h1,h2,…,hm就决定当前的图。

拿个个图画一下,从最底下往上考虑,可以发现这构成了一个树形结构。

注意到将全体h+1很好实现,将一个h改成0,就意味着把树切成了两部分,由于随机数据,树高是logn的。。

复杂度就是nlogn。

10 thoughts on “ZJOI 2012 Round 1 Solution

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>