11
30
2015
1

CERC2012的一道『暴力』题与一个有趣的递归式

 

 [Cerc2012]Non-boring sequences

 

Description

我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。

Input

第一行一个正整数T,表示有T组数据。每组数据第一行一个正整数n,表示序列的长度,1 <= n <= 200000。接下来一行n个不超过10^9的非负整数,表示这个序列。

Output

对于每组数据输出一行,输出"non-boring"表示这个序列不无聊,输出"boring"表示这个序列无聊。

由于是权限题窝就贴下题面吧。。做法可以看hgr同学的博客(http://blog.csdn.net/geotcbrl/article/details/49797889)或者是tjz唐老师的博客。。

然而窝第一眼看到这个做法的时候和hgr一样,认为这个做法是暴力。。唐老师说可以证明,问了唐老师,唐老师表示这个其实是证明

$T(n)=\max\{T(k)+T(n-k)+\min(n,n-k)\}=O(nlogn)$

然后使用归纳法证明。。。

嗯。。的确可以这么做。。但是看上去是不是不太直观啊。。

于是窝想了一个(两个?)直观的证明,是这样的:

我们考虑每个对时间复杂度有贡献的下标,它一定属于两段中比较小的那一段,于是。。每次每个下标被算一次,它的所在块就会缩小一倍,那么显然每个下标的贡献就是$O(logn)$,它的总时间复杂度就是$O(nlogn)$

 

说到底,我们不断拆分这个过程,分开后就不会再合并,而且每次拆开的复杂度就是拆成的两个序列中较小的一个,很自然地想到把这个过程倒过来,那么这就是一个启发式合并的过程,显然时间复杂度就是$O(nlogn)$啦

 

感觉这个可以叫『启发式拆分』?233 总之要注意这样的做法不是暴力,相反复杂度还很优秀。。

Category: oi题解 | Tags: | Read Count: 1273

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com