4059: [Cerc2012]Non-boring sequences
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 632 Solved: 227Description
我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。
Input
第一行一个正整数T,表示有T组数据。每组数据第一行一个正整数n,表示序列的长度,1 <= n <= 200000。接下来一行n个不超过10^9的非负整数,表示这个序列。
Output
对于每组数据输出一行,输出"non-boring"表示这个序列不无聊,输出"boring"表示这个序列无聊。
Sample Input
4 5 1 2 3 4 5 5 1 1 1 1 1 5 1 2 3 2 1 5 1 1 2 1 1Sample Output
non-boring boring non-boring boringHINT
Source
【分析】
这题我是不会往扫描线方向想的。感觉很神奇。
首先对于每个a[i]求前一个同色的位置$last$和后一个的位置$next$,显然左端点在[last+1,i]右端点在[i,next-1]的都是可以的。
那么把左端点当成x,右端点当成y,区间就表示成了平面上的一个点,可行区间集就是一个矩形,最后看看n个矩形是否把上三角覆盖。
【这个把这题复杂化了,其实有更简单的方法所以我没打这个哦
很容易想到暴力。
如果序列non-boring,必定有一个数值只出现了一次,找到他的位置i【可能有多个,先随便找一个】,
那么区间跨越i的都可以的嘛,所以只需判断[l,i-1]和[i+1,r]即可。
就把区间分治了。
但是时间复杂度???
网上的神犇们说,从左右两端向中间暴力枚举,用$next$和$last$$O(1)$判断即可。
是nlogn的。
因为:$T(n)=max{T(k)+T(n-k)+min(n,n-k)}=O(nlogn)$
直观证明:
我们考虑每个对时间复杂度有贡献的下标,它一定属于两段中比较小的那一段,于是。。
每次每个下标被算一次,它的所在块就会缩小一倍,那么显然每个下标的贡献就是O(logn),它的总时间复杂度就是O(nlogn)。
ORZORZ。。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Maxn 200010 8 9 struct node{ int x,id;}t[Maxn];10 bool cmp(node x,node y) { return x.x =r) return 1;16 int t=-1;17 for(int i=0;i<=r-l+1;i++)18 {19 if(l+i>r-i) break;20 if(nt[l+i]>r&<[l+i] r&<[r-i] =1;i--) nt[i]=ft[a[i]],ft[a[i]]=i;48 for(int i=1;i<=p;i++) ft[i]=0;49 for(int i=1;i<=n;i++) lt[i]=ft[a[i]],ft[a[i]]=i;50 if(ffind(1,n)) printf("non-boring\n");51 else printf("boring\n");52 }53 return 0;54 }
2017-04-25 08:38:03