11
30
2015
4

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: 2462
orzwhx 说:
2019年8月06日 15:36

@wjz: whxtql

cleaning services 说:
2021年8月27日 22:55

What kind of cleaning business will you create? Is your business a general house keeping one or will it have some expertise in such cleaning as green cleaning, end-of-tenure cleaning, open home cleaning, after-gathering cleaning,

live in maids dubai 说:
2021年8月31日 21:17

it is advisable to remember of which cleaning companies will not be maid products and services. They will not likely jump in place and complete your pots and pans and walk your pet dog and acquire your grubby socks. You should do all in this beforehand. They will handle everything more. If you would like your new carpet cleaned and in addition they offer of which service, they're going to do the item. If you would like your bottom mopped in addition to cleaned, they're going to do the item. But it's your choice to be sure that it has reached least a small amount swept in place. If that you are older with age, you really should enlist assistance from a neighbor or other people that people trust to assist you to tidy up end in. However, leave others to this cleaning company-they're there that can help.


登录 *


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