uva 1608 不无聊的序列(附带常用算法设计和优化策略总结)

时间:2022-11-07 22:09:06

uva 1608 不无聊的序列(附带常用算法设计和优化策略总结)

紫书上有这样一道题:

如果一个序列的任意连续子序列中都至少有一个只出现一次的元素,则称这个序列时不无聊的。输入一个n个元素的序列,判断它是不是无聊的序列。n<=200000。

首先,在整个序列中找到只出现一次的元素ai。如果不能找到,那它就是无聊的。不然,就可以退出当前循环,递归判断[1, i-1]和[i+1, n]是不是无聊的序列。然而怎么找ai很重要。如果从一头开始找,那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找,那么最差情况就变成了ai在中间,时间复杂度是O(nlogn)!这是因为在中间的找起来慢,分起来快,而在两端的找起来快,分起来慢。有些时候用好中途相遇法还是很重要的!

下面是紫书上讲的常用算法设计策略和优化策略(注意这里是设计策略而不是算法):

构造法(构造解),

中途相遇法(通常比多个相遇法还要优秀),

问题分解(将两个不相关的问题剥离开来分别求解),

等价转换(化繁为简),

假设法(利用对称性避免讨论),

使用数据结构(在不改变主算法的情况下加速算法),

数形结合(通常与滑动窗口相联系),

二分答案(将求最优值转化为判定最优值,也算在策略内),

扫描法(带有顺序的枚举法,通常维护一些重要的量),

枚举基准(寻找基于当前基准的最优值,再取所有基准的最值),

滑动窗口(维护单调性,高效去除冗余状态)等等。