首页 > 代码库 > UVa 1608,Non-boring sequences

UVa 1608,Non-boring sequences

好诡异的一个题啊

紫书上关于从左边找还是从两边往中间找的讨论没有看懂,怎么一下就找到唯一的元素了(⊙_⊙?)

方法就是用的书上讲的方法,类似于uva 11572,不过这个题需要预处理存下两边的最近的相同数的位置

for (int i=1;i<=n;i++) {            prev[i]=r[a[i]];            next[prev[i]]=i;            r[a[i]]=i;}//记录元素a[i]上次出现的位置,因为是从左向右遍历,所以上次出现的位置正好是prev[i]要求的         //prev[i],与 i位置的元素  相同的左边最近的元素的位置        //next[i] 同理 
View Code

然后递归检查是否符合题意就可以了。。。

从左边开始找

int dfs(int l,int r){    if (l>=r) return 1;    int p;    for (p=l;p<=r;p++)        if (next[p]>r&&prev[p]<l) break;    if (p>r) return 0;    return dfs(l,p-1)&&dfs(p+1,r);} //TLE的dfs,从左往右找的
View Code

TLE,然后改成从两边向中间开始找

int dfs(int l, int r) {    if(l >= r)    return 1;    for(int i = 0; i <= (r-l+1)/2; i++) {        if(next[l+i] > r && prev[l+i] < l)            return dfs(l, l+i-1) && dfs(l+i+1, r);        if(next[r-i] > r && prev[r-i] < l)            return dfs(l, r-i-1) && dfs(r-i+1, r);    }    return 0;} 
View Code

但是还是TLE,这下我就蛋疼了,想半天想不出来还能优化的地方

结果参考网上大神,对比了一下,发现他是用的map存的,避免了使用memset,但是换成了map.clear()(map.clear非常快么= =)

下面那条只是把map改成数组,然后只用了一句memset,看时间增加量

AC代码

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>#define maxn 200000+5using namespace std;int prev[maxn],next[maxn];int a[maxn];map <int,int>r;int n;/*int dfs(int l,int r){    if (l>=r) return 1;    int p;    for (p=l;p<=r;p++)        if (next[p]>r&&prev[p]<l) break;    if (p>r) return 0;    return dfs(l,p-1)&&dfs(p+1,r);} *///TLE的dfs,从左往右找的int dfs(int l, int r) {    if(l >= r)    return 1;    for(int i = 0; i <= (r-l+1)/2; i++) {        if(next[l+i] > r && prev[l+i] < l)            return dfs(l, l+i-1) && dfs(l+i+1, r);        if(next[r-i] > r && prev[r-i] < l)            return dfs(l, r-i-1) && dfs(r-i+1, r);    }    return 0;} //二分的思想,从两边往中间找 int main(){    int testcase;    scanf("%d",&testcase);    while (testcase--){        //memset(prev,0,sizeof(prev));        //memset(next,0,sizeof(next));        //memset(a,0,sizeof(a));        //memset(r,0,sizeof(r));         r.clear();        scanf("%d",&n);        for (int i=1;i<=n;i++) {scanf("%d",&a[i]);prev[i]=0;next[i]=n+1;}        for (int i=1;i<=n;i++) {            prev[i]=r[a[i]];            next[prev[i]]=i;            r[a[i]]=i;}//记录元素a[i]上次出现的位置,因为是从左向右遍历,所以上次出现的位置正好是prev[i]要求的         //prev[i],与 i位置的元素  相同的左边最近的元素的位置        //next[i] 同理          puts(dfs(1, n) ? "non-boring" : "boring");    }}
View Code

时间复杂度是o(nlogn)

以后对于大数据量的数组,还是尽量不要用memset这条语句了,虽然是线性的......

ps.本题代码有参考网上某大神的代码。我一开始写的代码比较丑,尤其是预处理那段,贴出来也没人看得懂= =,就不贴了。

UVa 1608,Non-boring sequences